이 포스트에서는 프로그래밍 문제 풀이 사이트 백준 Online Judge의 Solved.ac 기준 난이도 Silver II에 해당하는 문제들인 1912번 : 연속합, 11729번 : 하노이 탑 이동 순서, 11724번 : 연결 요소의 개수를 풀이해보도록 하겠습니다.
1912번 : 연속합
임의의 수열이 주어질 때, 연속된 몇 개의 수를 선택해서 얻을 수 있는 가장 큰 합을 구하는 문제입니다.
간단히만 생각해봐도 Brute-force 알고리즘으로 구하려면 n개의 정수가 있는 수열에서 얻어질 수 있는 부분 수열은 nC2이므로 O(n^2)이 될 것입니다.
따라서 시간 초과를 얻지 않으려면 새로운 알고리즘을 떠올려 풀어야 합니다.
일반적으로 이런 상황에서는 DP를 사용하므로, 다이나믹 프로그래밍을 이용하여 풀이하도록 하겠습니다.
#include<stdio.h>
int main() {
int n, arr[100005] = {0, }, dp[100005] = {0, }, max = 0;
scanf("%d", &n);
for(int i=0; i<n; i++) scanf("%d", &arr[i]);
dp[0] = max = arr[0];
for(int i=1; i<n; i++) {
if(dp[i-1] + arr[i] > arr[i]) dp[i] = dp[i-1] + arr[i];
else dp[i] = arr[i];
if(dp[i] > max) max = dp[i];
}
printf("%d", max);
}
이 문제는 알고리즘을 떠올리기만 하면 쉽게 풀 수 있는데 알고리즘을 떠올리기가 어려울 수 있었던 것 같습니다.
굳이 시작 부분을 여러 군데로 잡지 않고 앞에서부터 연산을 해나가는 방법으로도 쉽게 답을 구할 수 있습니다.
먼저 앞에서부터 i번째 원소까지의 합과 i번째 원소의 크기를 비교하여, 더 큰 쪽을 취해 dp 배열에 저장합니다.
이것은 i번째 원소의 크기가 이전부터의 합보다 크면, 앞의 원소들을 가져갈 필요가 없다는 뜻입니다.
이제 dp 배열들의 값들 중 최댓값을 취하면 답이 됩니다.
11729번 : 하노이 탑 이동 순서
하노이의 탑 규칙에 따라 원판의 갯수가 주어지면, 최소 이동 횟수와 그 경로를 출력하는 문제입니다.
알고리즘이 되게 신박하고 모르면 떠올리기 힘들지만 유명한 문제라서 저는 이미 알고 있기에 그냥 정석대로 풀이해보겠습니다.
#include<stdio.h>
void hanoi(int N, int start, int end, int remain) {
if(N == 1) {
printf("%d %d\n", start, end);
return;
}
hanoi(N-1, start, remain, end);
printf("%d %d\n", start, end);
hanoi(N-1, remain, end, start);
}
int main() {
int N, K = 1;
scanf("%d", &N);
for(int i=1; i<=N; i++) K *= 2;
printf("%d\n", --K);
hanoi(N, 1, 3, 2);
}
하노이의 탑을 작은 N으로 직접 해보면 규칙성을 알 수 있습니다.
옮기는 횟수가 N이 증가함에 따라 1, 3, 7, ...으로 2배 + 1만큼 증가하게 되는데, 이것은 N-1짜리 덩어리를 목적지가 아닌 그 옆 기둥에 옮김 → 가장 큰 N번째 원판을 목적지에 옮김 → 아까 옮긴 N-1짜리 덩어리를 목적지에 옮김의 과정을 거치기 때문입니다. (1배수만큼 소모 → 가장 큰 원판 옮길 때 1회 → 다시 1배수만큼 소모)
이것은 잘 생각해보면 원판이 1개 늘어날 때마다 2배수 + 1만큼 횟수가 규칙대로 늘어난다는 뜻이므로, 재귀함수로 해결할 수 있음을 의미합니다.
따라서 원판을 옮기는 함수를 재귀함수로 만든 뒤 다음과 같이 재귀적으로 실행할 수 있도록 함수를 구현합니다.
1. N-1짜리 원판 덩어리를 end(목적지)가 아닌 그 옆 기둥(remain)으로 옮김
2. N번쨰 짜리 원판을 end(목적지)로 옮김, 이 때 N=1이 아니므로 출력을 해주어야 함 (start와 end)
3. N-1짜리 원판 덩어리를 remain에서 end로 옮김
이 세 단계대로 구현한 것이 위의 hanoi 함수가 되므로, 이를 참고해서 보시면 어렵지 않게 이해할 것입니다.
11724번 : 연결 요소의 개수
양방향성 그래프에서 연결 요소의 개수를 출력하는 문제입니다. (여기서 연결 요소란, 간선으로 연결된 덩어리를 말합니다.)
시간 제한도 3초이고 정점의 수도 1000개 이하로 크지 않으므로, 단순히 탐색만 수행하면 무난하게 풀 수 있는 문제로 보입니다.
#include<stdio.h>
int graph[1005][1005] = {0, }, visit[1005] = {0, }, N, M, count = 0;
void DFS(int V) {
visit[V] = 1;
for(int i=1; i<=N; i++) if(graph[V][i] && !visit[i]) DFS(i);
}
int main() {
int x, y;
scanf("%d %d", &N, &M);
for(int i=1; i<=M; i++) {
scanf("%d %d", &x, &y);
graph[x][y] = 1;
graph[y][x] = 1;
}
for(int i=1; i<=N; i++) if(!visit[i]) DFS(i), count++;
printf("%d", count);
}
언제나 그랬듯 BFS보다는 DFS가 구현하기 쉽고 코드가 간략하기 때문에 DFS를 구현하였습니다.
우선 입력 단계에서 그래프를 모두 연결시켜주고, DFS에 모든 정점을 입력하여 체크되지 않은 것이 있는지 확인합니다.
DFS 함수는 재귀적으로 구현하여 이웃한 노드가 있다면 방문하여 visit을 체크하고, 또 다시 연결된 간선이 있는지 확인하는 과정을 반복하여 거치게 됩니다.
DFS 탐색이 한 번 끝나게 되면 count를 1 증가시켜 덩어리의 수가 1개 증가했음을 기록합니다.