백준 1912: 연속합
https://www.acmicpc.net/problem/1912
문제 설명
N개의 정수로 이루어진 수열이 주어졌을 때, 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 최대값을 구하는 문제다.단, 수는 한 개 이상 선택해야 한다.
1차 시도 (실패)
이 문제를 마주했을 때, 가장 먼저 생각난 건 누적합을 활용한 방식이었다.
모든 수열을 순회하면서
sum[앞의값] - sum[뒤의값]
으로 계산할 수 있으니,
- 누적합 배열을 만들고
- 각 위치마다 그 전까지의 최소 누적합을 빼면 최대 구간합이 되지 않을까? 라고 생각했다.
- 나보다 앞선 누적합 중 가장 작은 값을 찾으려면, 누적합 배열을 인덱스와 함께 정렬해서 탐색하면 될 것 같았다.
이렇게 작성한 코드는 다음과 같았다:
for (int i = 0; i < N; i++) {
int max = sum[i];
for (int j = i + 1; j < N; j++) {
int tmp = sum[j] - sum[i];
if (tmp > max) {
max = tmp;
}
}
ans = Math.max(max, ans);
}이중 반복문을 통해 각 구간합을 계산하고, 최댓값을 갱신하는 구조다.
결과는 시간 초과가 발생했다.
생각해보니 이중 for문 구조는 O(N²) 의 시간복잡도였고,입력값이 최대 100,000이기 때문에 이 방식은 실질적으로 불가능했다.
나는 처음에 "정렬 없이 그냥 순회하면서 빼는 거니까 O(N log N) 아닌가?"라고 착각했지만,실제로는 모든 (i, j) 쌍에 대해 sum[j] - sum[i]를 계산하기 때문에 완전한 이중 순회로 O(N²)이다.정렬을 포함했더라도 O(N log N)이 아닌, 여전히 느린 구조였을 것이다.
2차 시도
결국 다시 인터넷을 뒤져보며 동적 계획법을 활용해야함을 깨달았다.
이 알고리즘은 현재 위치에서
- 지금까지의 누적 최대값에 현재 수를 더하는 것과
- 현재 수 하나만 사용하는 것
중에서 더 큰 값을 고른다.
즉, 아래와 같은 점화식이다:
dp[i] = max(arr[i], dp[i-1] + arr[i])
for (int i = 0; i < N; i++) {
int max = sum[i];
for (int j = i + 1; j < N; j++) {
int tmp = sum[j] - sum[i];
if (tmp > max) {
max = tmp;
}
}
ans = Math.max(max, ans);
}이 코드는 O(N) 으로 매우 빠르며, 메모리도 효율적이다.
회고
- 처음 시도한 방식처럼, 누적합과 정렬을 이용해 푸는 방식도 사용되긴 한다.
예를 들어 "구간합이 K 이상인 최소 길이 구간" 같은 문제에서는 유용하다.
하지만 이 문제처럼 단순한 연속 구간합의 최대값을 구하는 문제에는 오히려 복잡하고 비효율적이다. - 이 문제는 전형적인 동적프로그래밍으로 푸는 문제였다. 그런데 풀이법이 잘 생각나지 않았다.
- 동적프로그래밍 문제를 많이 풀어봤다 생각했는데, 더 다양하게 풀어봐야겠다.