각 수에대한 모든 최대공약수의 합을 구하는 문제입니다. 최대공약수를 구하는 함수입니다. int gcd(int a, int b) { if (b == 0) { return a; } else { return gcd(b, a % b); } } 각 수에 대해 최대공약수를 구하는 함수에 대입하여 추출된 수들을 전부 더해줘서 출력해주었습니다. #include #include #include #include #include using namespace std; int gcd(int a, int b) { if (b == 0) { return a; } else { return gcd(b, a % b); } } int main(int argc, char *argv[]) { int ts; int n; int num; long..

그래프의 정점을 최소 가중치로 모두 이어주는 문제입니다. 최소 스패닝 트리는 프림 알고리즘과, 크루스칼 알고리즘으로 풀수있습니다. 크루스칼 알고리즘을 통해서 풀어보았습니다. 가중치가 작은 간선부터 연결해주며, 연결된 정점들은 부모를 동일시 시켜줍니다. 부모가 같을경우 간선을 연결하면 싸이클이 생기므로, 부모가 같지 않을때만 가중치를 기준으로 연결해주면 됩니다. #include #include #include #include #include #include using namespace std; int main(int argc, char *argv[]) { int p, c; int V, E; int A, B, C; int parent[10010]; long long weightSum = 0; priority..

알파벳으로 된 2차원배열에서 이동할 수 있는 최댓값을 구하는 문제입니다. 각 위치마다 알파벳이 있는데 이미 A라는 알파벳인 위치를 지나쳤다면, 다음에는 A라는 위치는 지나갈 수 없습니다. DFS를 통해서 풀었고 visit배열을 통하여 알파벳을 지나쳤는지 체크해주었습니다. 그리고 DFS를 통해서 가장 큰 이동횟수가 나왔때마다 갱신해주었으며, 재귀가 끝났을 때 계산된 가장 큰 이동횟수를 출력해주었습니다. #include #include #include #include using namespace std; int R, C; int result = 0; int moveX[4] = { 0, 1, 0, -1 }; int moveY[4] = { 1, 0, -1, 0 }; int visit[26]; char map[3..

4개의 점들을 이어서 하나의 도형을 만듭니다. 여러가지 도형을 만들 수 있는데 2차원 배열에 그 도형을 넣었을때 값이 가장 큰 값을 출력하는 문젭니다. 만들 수 있는 도형을 모두 함수에 넣어놓고 각 위치에 대해서 도형이 있을 때의 최댓값을 갱신해줍니다. 함수가 끝나면 최댓값을 출력해줍니다. #include #include #include using namespace std; const int MAX = 510; int N, M; int map[MAX][MAX]; int visit[MAX][MAX]; int result = 0; void check(int num) { result = max(result, num); } void shape(int a, int b) { int sum = 0; if (a + 1

부분수열의 합이 S가 되는 경우의 개수를 찾는 문제입니다. 재귀함수를 통해서 인덱스 1~N까지 차례대로 현재 인덱스의 수를 더하는 경우와 현재 인덱스의 수를 패스하는 경우에 대해서 계산을 하며, 만약 S가 되면 카운트를 해줍니다. #include using namespace std; int N, S; int arr[30]; int result = 0; void solve(int index, int sum) { sum += arr[index]; if (index >= N) { return; } if (sum == S) { result++; } solve(index + 1, sum - arr[index]); solve(index + 1, sum); } int main(int argc, char *argv[]..

방향그래프에서 시작점에서 다른 모든 정점으로의 최단 경로를 구하는 문제입니다. 우선순위 큐를 이용해서 시작점부터 연결된 선들에 대해 가중치가 낮은 선들을 먼저 탐색합니다. 그리고 각 정점에 대한 거리를 갱신해줍니다. 이를 반복하여 우선순위 큐에 값이 없을때 까지 실행하며, 최종적으로 저장되어있는 각 정점에 대한 거리를 출력해줍니다. #include #include #include #include using namespace std; const int INF = 987654321; int vertex, edge; int start; int u, v, w; vector map[20010]; priority_queue pq; vector solve() { int location; int weig..

단어를 뒤집어서 출력하는 문제입니다. 줄단위로 받기위해서 getline을 사용하였으며, 시작점을 지정해놓고 공백이거나 끝일때 시작점부터 공백전까지 substr로 잘라줍니다. 그리고 reverse를 통해서 뒤집어서 출력해주었습니다. #include #include #include #include using namespace std; int main(int argc, char *argv[]) { int n= 10; int start, end; string s; string temp; cin >> n; getline(cin, s); while (n--) { end = 0; start = 0; getline(cin, s); for (int i = 0; i

수열이 주어지고 차례대로 계산될 때 가지고 있는 연산자의 순서를 바꿔서 최솟값과 최댓값을 찾는 문제입니다. 브루트포스 방식을 사용해서 모든 경우의 수를 탐색해보았습니다. #include #include #include #include using namespace std; int n; int num; int maxNum = -987654321; int minNum = 987654321; int ope[4]; vector v; void solve(int i, int result, int sum, int sub, int mul, int div) { if (i == n) { maxNum = max(maxNum, result); minNum = min(minNum, result); return; } int x =..