문제 설명
주어진 정수 배열 A와 여러 쌍의 정수 L, R이 주어졌을 때, 각 쌍에 대해 L번 인덱스부터 R번 인덱스의 구간 합을 구하는 프로그램을 작성하시오.
예를 들어, A = [1, 2, 3, 4, 5]이고 구간 쌍이 (1, 3), (0, 2), (2, 4)라고 하면,
결과는 각각 9, 6, 12가 되어야 합니다.
입력 형식
- 첫 줄에 정수 N (1 ≤ N ≤ 100,000): 배열 A의 크기
- 둘째 줄에는 N개의 정수 A[i] (1 ≤ A[i] ≤ 10,000)가 주어진다.
- 셋째 줄에 정수 M (1 ≤ M ≤ 100,000): 구간 쌍의 개수
- 이어서 M줄에 걸쳐 구간 쌍 L, R (0 ≤ L <= R < N)가 주어진다.
출력 형식
- 각 구간의 합을 M줄에 걸쳐 출력한다.
문제 해결 전략
이 문제를 해결하기 위해서는 단순히 반복문을 사용하는 것도 가능하지만,
최악의 경우 N과 M이 최대 100,000이므로 O(N * M)의 시간 복잡도를 가진 연산은 불가능하다.
따라서 O(N + M)의 시간 복잡도를 가지는 방법이 필요하다.
이를 위해 전처리 과정으로 누적 합 배열을 만들어 주면 유용하다.
누적 합 배열을 이용하면 각 구간의 합을 빠르게 구할 수 있다.
누적 합 배열 설명
먼저 배열 A의 누적 합을 계산하여 prefix_sum 배열을 생성한다.
prefix_sum[i]는 A[0]부터 A[i]까지의 합을 저장한다.
그러면 L번 인덱스부터 R번 인덱스의 합은 다음과 같이 계산할 수 있다:
sum(L, R) = prefix_sum[R] – prefix_sum[L – 1], L > 0
sum(0, R) = prefix_sum[R], L = 0
코드 구현
def compute_prefix_sum(A):
prefix_sum = [0] * len(A)
prefix_sum[0] = A[0]
for i in range(1, len(A)):
prefix_sum[i] = prefix_sum[i - 1] + A[i]
return prefix_sum
def range_sum(prefix_sum, L, R):
if L == 0:
return prefix_sum[R]
else:
return prefix_sum[R] - prefix_sum[L - 1]
def main():
N = int(input())
A = list(map(int, input().split()))
M = int(input())
prefix_sum = compute_prefix_sum(A)
results = []
for _ in range(M):
L, R = map(int, input().split())
results.append(range_sum(prefix_sum, L, R))
for result in results:
print(result)
if __name__ == "__main__":
main()
코드 설명
1. compute_prefix_sum 함수는 입력받은 배열 A의 누적 합을 계산하여
prefix_sum 배열을 반환합니다. 초기값을 설정하고, 각 인덱스의 값은 이전 값과 현재 값을 더하여 계산합니다.
2. range_sum 함수는 주어진 L과 R에 대해 누적 합 배열을 사용하여
구간의 합을 빠르게 계산합니다. L이 0이면 prefix_sum[R]을 반환하고, 그렇지 않으면
prefix_sum[R]에서 prefix_sum[L-1]을 빼서 결과를 계산합니다.
3. main 함수에서는 입력을 처리하고, 각 구간 쌍에 대해 range_sum 함수를 호출하여
결과를 출력합니다.
시간 복잡도 분석
– 누적 합 배열을 계산하는 데 O(N)의 시간이 걸립니다.
– 각 M개의 쿼리에 대해 O(1)의 시간이 소요됩니다.
따라서 전체적으로 O(N + M)의 시간 복잡도를 가집니다.
결론
이번 강좌에서는 구간 합 구하기에 대한 효율적인 접근 방법을 다루었습니다.
누적 합을 활용하면 시간 복잡도를 줄일 수 있어 큰 입력에도 빠르게 처리할 수 있습니다.
이러한 기법은 다양한 알고리즘 문제에서 유용하므로 꼭 숙지해두시기 바랍니다.
추가 연습 문제
- 1. 예제의 배열 A를 바꿔가며 구간 합을 구해보시오.
- 2. 다른 알고리즘 (세그먼트 트리 또는 펜윅 트리)을 이용하여 구간 합을 구하는 방법을 연구해보시오.
- 3. 배열의 특정 인덱스의 값을 갱신하고 전체 구간 합을 다시 계산하는 문제를 연습해보시오.
참고 문헌
– 클리츠 알고리즘 문제집
– 온라인 코딩 테스트 관련 자료
– LeetCode, HackerRank의 구간 합 문제