안녕하세요, 여러분! 오늘은 백준 온라인 저지의 11659번 문제 “구간 합 구하기 4”에 대해 알아보겠습니다. 이 문제는 누적 합(Prefix Sum)이라는 알고리즘의 기초를 배우기에 아주 좋은 문제예요. 처음 들어보시는 분들도 걱정 마세요. 차근차근 설명해 드리겠습니다.
먼저, 문제를 간단히 살펴볼까요? 이 문제는 N개의 정수로 이루어진 수열이 주어졌을 때, 특정 구간의 합을 구하는 문제입니다. 예를 들어, [5, 4, 3, 2, 1]이라는 수열이 있고, 2번째 수부터 4번째 수까지의 합을 구하라고 하면 4 + 3 + 2 = 9가 되는 거죠.
처음 이 문제를 보면, 단순히 해당 구간의 숫자들을 더하면 되겠다고 생각할 수 있어요. 하지만 이 방법은 구간의 길이가 길어질수록, 그리고 구간 합을 구하는 횟수가 많아질수록 시간이 오래 걸리게 됩니다. 그래서 우리는 ‘누적 합’이라는 기법을 사용할 거예요.
누적 합이 뭘까요? 쉽게 말해, 배열의 각 위치까지의 합을 미리 계산해 놓는 방법입니다. 예를 들어, [5, 4, 3, 2, 1]이라는 수열이 있다면, 누적 합 배열은 [5, 9, 12, 14, 15]가 됩니다. 이렇게 하면 어떤 구간의 합이든 빠르게 구할 수 있어요.
자, 이제 코드를 작성해볼까요?
import sys
input = sys.stdin.readline
N, M = map(int, input().split())
numbers = list(map(int, input().split()))
# 누적 합 배열 생성
prefix_sum = [0] * (N + 1)
for i in range(1, N + 1):
prefix_sum[i] = prefix_sum[i-1] + numbers[i-1]
# 구간 합 계산
for _ in range(M):
i, j = map(int, input().split())
print(prefix_sum[j] - prefix_sum[i-1])
이 코드를 하나씩 살펴볼까요?
먼저 입력을 빠르게 받기 위해
sys.stdin.readline()을 사용합니다.N(수열의 길이)과M(구간 합을 구해야 하는 횟수)을 입력받습니다.numbers리스트에 주어진 수열을 저장합니다.prefix_sum리스트를 만들어 누적 합을 저장합니다. 이때 인덱스를 1부터 시작하게 하여 계산을 편리하게 합니다.반복문을 통해 누적 합을 계산합니다.
prefix_sum[i]는i번째 수까지의 누적 합이 됩니다.마지막으로, 주어진 구간의 합을 계산합니다.
i부터j까지의 합은prefix_sum[j] - prefix_sum[i-1]로 구할 수 있습니다.
여기서 핵심은 누적 합 배열을 미리 계산해 놓는다는 점입니다. 이렇게 하면 어떤 구간의 합이든 단 한 번의 뺄셈으로 구할 수 있어요. 예를 들어, 2번째 수부터 4번째 수까지의 합을 구하려면 prefix_sum[4] - prefix_sum[1]을 계산하면 됩니다.
이 방법의 장점은 무엇일까요? 바로 시간 복잡도예요. 누적 합을 계산하는 데는 O(N)의 시간이 걸리지만, 이후 각 구간 합을 구하는 데는 O(1)의 시간만 걸립니다. 따라서 전체 시간 복잡도는 O(N + M)이 되어, 구간 합을 여러 번 구해야 할 때 매우 효율적입니다.
이 문제를 통해 우리는 ‘선처리 후활용’이라는 프로그래밍의 중요한 개념을 배울 수 있어요. 미리 계산해 놓은 결과를 잘 활용하면, 나중에 훨씬 더 빠르게 원하는 결과를 얻을 수 있다는 거죠.
실제로 이런 누적 합 기법은 다양한 곳에서 활용됩니다. 예를 들어, 2차원 배열에서의 부분 합을 구할 때도 비슷한 방식을 사용할 수 있고, 시계열 데이터를 분석할 때도 유용하게 쓰인답니다.
여러분, 오늘 배운 누적 합 알고리즘 어떠셨나요? 처음에는 조금 낯설 수 있지만, 이해하고 나면 아주 강력한 도구가 된답니다. 앞으로 비슷한 문제를 만났을 때, 이 방법을 떠올려 보세요. 그리고 혹시 다른 문제에도 이 개념을 적용할 수 있을지 고민해 보는 것도 좋은 연습이 될 거예요.