1. 문제 정의
코딩테스트에서 자주 출제되는 구간 합 문제는 주어진 배열의 특정 구간에 있는 원소들의 합을 효율적으로 구하는 문제입니다. 이번 포스팅에서는 ‘구간 합 구하기 1’ 문제를 다루어 보겠습니다.
문제 설명
정수 N과 M이 주어지고, N개의 정수로 이루어진 배열이 주어집니다. 다음으로 M개의 쿼리가 주어지며, 각 쿼리는 두 개의 정수 S와 E로 이루어져 있습니다. S부터 E까지의 합을 구하는 문제를 해결하시오. 단, S와 E는 1부터 N까지의 범위를 갖습니다.
2. 입력 및 출력 형식
입력
- 첫 번째 줄에 N과 M이 공백으로 구분되어 주어진다. (1 ≤ N, M ≤ 100,000)
- 두 번째 줄에 N개의 정수가 공백으로 구분되어 주어진다. (각 정수는 1 이상 100,000 이하)
- 세 번째 줄부터 M개의 줄에 걸쳐 쿼리 두 개가 주어진다. (S, E)
출력
- M개의 줄에 걸쳐 각 쿼리에 대한 답을 출력한다.
3. 예제 입력 및 출력
예제 입력
5 3
1 2 3 4 5
1 3
2 4
3 5
예제 출력
6
9
12
4. 문제 접근 방법
구간 합을 구하기 위해서는 가장 먼저 단순한 방법으로 풀 수 있습니다. 하지만 N과 M의 최대값이 100,000이므로 O(N * M)의 시간복잡도로는 불가능합니다. 따라서, 우리는 구간 합을 구할 수 있는 효율적인 방법을 찾아야 합니다.
4.1. 단순한 접근 방식
가장 간단한 방법은 S부터 E까지 반복하여 합을 구하는 것입니다. 하지만 이 방법은 O(N * M)의 복잡도를 가집니다.
4.2. 누적 합 배열 활용하기
효율적인 접근법 중 하나는 누적 합(Cumulative Sum) 배열을 사용하는 것입니다. 누적 합 배열을 먼저 생성하여, 각 쿼리에 대해 S와 E의 값을 이용해 곧바로 답을 구합니다.
누적 합 배열을 정의하면, 배열의 i번째 원소는 1부터 i까지의 합을 나타냅니다. 즉, 누적 합 배열의 i번째 값은 다음과 같이 계산됩니다:
sum[i] = sum[i - 1] + array[i - 1]
쿼리를 처리할 때는 다음과 같은 공식을 사용할 수 있습니다:
result = sum[E] - sum[S - 1]
5. 알고리즘 구현
위에서 설명한 누적 합 배열을 사용하여 알고리즘을 구현해 보겠습니다.
5.1. 파이썬 코드
def solve(N, M, array, queries):
# 누적 합 배열 생성
sum_array = [0] * (N + 1)
# 누적 합 계산
for i in range(1, N + 1):
sum_array[i] = sum_array[i - 1] + array[i - 1]
result = []
# 쿼리 처리
for S, E in queries:
query_sum = sum_array[E] - sum_array[S - 1]
result.append(query_sum)
return result
# 입력 예시
N, M = 5, 3
array = [1, 2, 3, 4, 5]
queries = [(1, 3), (2, 4), (3, 5)]
# 결과 출력
output = solve(N, M, array, queries)
for res in output:
print(res)
6. 코드 설명
위의 코드는 다음과 같은 순서로 동작합니다:
- 먼저 누적 합 배열을 초기화합니다. 누적 합 배열의 크기는 N + 1로 설정하여 1부터 N까지의 합을 쉽게 구할 수 있게 합니다.
- 그 다음, 배열의 각 요소를 순회하며 누적 합을 계산합니다.
- 쿼리를 순회하면서, 주어진 S와 E에 대한 합을 누적 합 배열을 이용해 빠르게 계산합니다.
- 계산된 결과는 리스트에 저장되어, 최종적으로 출력됩니다.
7. 시간 복잡도 분석
위 알고리즘의 시간 복잡도는 다음과 같습니다:
- 누적 합 배열을 생성하는 데 O(N)
- M개의 쿼리를 처리하는 데 O(M)
결과적으로 전체 시간 복잡도는 O(N + M)으로, 효율적으로 문제를 해결할 수 있습니다.
8. 공간 복잡도 분석
공간 복잡도는 누적 합 배열을 저장하기 위한 O(N)입니다. 추가적인 변수는 상수 공간을 사용하므로 전체 공간 복잡도는 O(N)입니다.
9. 결론
이번 포스팅에서는 구간 합 구하기 문제를 다루어 보았습니다. 누적 합 배열을 활용하여 효율적으로 문제를 해결하는 방법에 대해 알아보았고, 파이썬 코드 예제를 통해 이해를 돕고자 하였습니다. 다양한 문제에서 구간 합을 필요로 할 때 이 방법을 적용할 수 있으며, 이를 바탕으로 더욱 복잡한 문제들을 해결하는 데 도움이 되길 바랍니다.
10. 추가 연습문제
이제 여러분 스스로 연습문제를 풀어보세요. 아래는 몇 가지 추가 연습문제입니다.
- 1부터 100까지의 수에서 구간 합을 구하는 프로그램을 작성하시오.
- 각 요소가 변할 때마다 해당 구간의 합을 구할 수 있는 프로그램을 구현하시오.
- 2차원 배열에서 특정 영역의 합을 구하는 프로그램을 작성하시오.
11. 질문 및 피드백
이 글에서 다룬 내용에 대해 궁금한 점이나 피드백이 있다면 댓글로 남겨주세요. 함께 문제를 해결해보아요!