문제 요약
N개의 수가 주어지고, M개의 질의가 주어진다.
각 질의는 (i, j) 형태로 주어지며 i번째 수부터 j번째 수까지의 합을 출력해야 한다.
제한:
- 1 ≤ N ≤ 100,000\
- 1 ≤ M ≤ 100,000
즉, 구간 합을 최대 100,000번 계산해야 한다.
처음 풀이 (시간 초과)
처음에는 질의가 들어올 때마다 sum()을 이용해 구간 합을 직접 계산했다.
n, m = map(int, input().split())
nums = list(map(int, input().split()))
for _ in range(m):
i, j = map(int, input().split())
print(sum(nums[i-1:j]))
왜 시간 초과가 발생했을까?
sum(nums[i-1:j])는 내부적으로 구간 길이만큼 반복하면서 더하는 연산이다.
최악의 경우:
- 구간 길이 ≈ 100,000
- 질의 개수 ≈ 100,000
즉 시간 복잡도가 대략
O(N × M)
≈ 100,000 × 100,000
≈ 10^10
이 정도 연산은 1초 안에 절대 수행할 수 없다.
아이디어: 누적합(Prefix Sum)
구간 합 문제의 전형적인 해결 방법은 누적합 배열을 만드는 것이다.
누적합 정의
prefix[k] = 1번째 수부터 k번째 수까지의 합
예를 들어
nums = [5,4,3,2,1]
누적합 배열은
prefix = [0,5,9,12,14,15]
처럼 만들 수 있다.
구간 합을 빠르게 구하는 방법
i ~ j 구간 합은
prefix[j] - prefix[i-1]
로 바로 계산할 수 있다.
이렇게 하면:
- 누적합 계산:
O(N) - 각 질의 처리:
O(1)
전체 시간 복잡도
O(N + M)
이 되어 문제의 제한을 충분히 통과할 수 있다.
내가 처음 시도했던 누적합 코드 (그래도 시간 초과)
처음에는 누적합 배열을 만들면서도 sum()을 사용했다.
sums.append(sum(nums[:x+1]))
이 방식은 누적합을 만드는 과정 자체가 O(N²) 이 되어버린다.
즉,
sum(nums[:1])
sum(nums[:2])
sum(nums[:3])
...
sum(nums[:N])
처럼 매번 처음부터 다시 더하기 때문에 여전히 느리다.
핵심 포인트
누적합은 이전 누적합을 이용해서 O(1)로 갱신해야 한다.
prefix[i] = prefix[i-1] + nums[i]
이 방식이면 누적합 배열을 O(N)에 만들 수 있다.
내 코드
n, m = map(int, input().split())
nums = list(map(int, input().split()))
sums = [0]
for x in range(n):
sums.append(sums[x] + nums[x])
for _ in range(m):
i, j = map(int, input().split())
print(sums[j] - sums[i-1])
이번 문제로 배운 점
- 구간 합 문제에서는 누적합(prefix sum) 패턴이 매우 자주 등장한다.
sum()자체가 느린 함수라기보다 반복적으로 호출하는 구조가 문제였다.- 누적합 배열을 만들 때도 이전 값을 이용해 O(1)로 갱신해야 한다.
- 구간 합 문제는 보통
<!-- -->
prefix[j] - prefix[i-1]
공식을 떠올리면 해결되는 경우가 많다.