안녕하세요! 파이썬 코딩 테스트 강좌에 오신 것을 환영합니다. 이번 강좌에서는
“구간 합 구하기 2” 문제를 다룰 것입니다. 알고리즘 문제를 해결하는 데 있어
구간 합을 효율적으로 계산하는 방법은 매우 중요합니다.
아래에서 문제 설명과 해결 과정을 단계별로 살펴보겠습니다.
문제 설명
주어진 N개의 정수 A[1], A[2], …, A[N]이 주어졌을 때,
Q개의 질의가 주어집니다. 각 질의는 두 정수 L과 R로 구성되며,
A[L]부터 A[R]까지의 합을 구하는 것입니다.
문제는 다음과 같습니다:
입력 형식:
첫 번째 줄에 정수 N(1 ≤ N ≤ 100,000)과 Q(1 ≤ Q ≤ 100,000)가 주어진다.
두 번째 줄에 N개의 정수를 공백으로 구분하여 입력받는다. |A[i]| ≤ 1,000,000
Q개의 질의는 다음과 같이 주어진다: 각 질의는 두 정수 L과 R (1 ≤ L ≤ R ≤ N)
로 구성된다.
출력 형식:
각 질의에 대한 A[L]부터 A[R]까지의 합을 출력한다.
문제를 효율적으로 푸는 방법
이러한 문제를 해결하기 위해서는 매 질의마다 구간의 합을 직접 계산하는 것이
아니라, 누적 합 (Prefix Sum)을 사용하는 것이 효율적입니다.
누적 합은 기본적으로 특정 구간의 합을 상수 시간 O(1) 안에 구할 수 있게 해줍니다.
누적 합 (Prefix Sum) 계산하기
누적 합을 구하는 방법은 다음과 같습니다:
- 누적 합 배열 S를 생성합니다. 여기서 S[i]는 A[1]부터 A[i]까지의 합을 의미합니다.
- S[0] = 0으로 초기화합니다. (편의상 0을 두어서 S[i]에서 S[L-1]을 빼는 방식으로 계산합니다.)
- 그 다음 S[i]를 다음과 같이 계산합니다: S[i] = S[i-1] + A[i]
이를 통해 S[R] – S[L-1]로 한 번의 뺄셈 연산으로 구간 합을 구할 수 있습니다.
문제 풀이 코드
def calculate_prefix_sum(arr):
n = len(arr)
prefix_sum = [0] * (n + 1)
for i in range(1, n + 1):
prefix_sum[i] = prefix_sum[i - 1] + arr[i - 1]
return prefix_sum
def range_sum(prefix_sum, L, R):
return prefix_sum[R] - prefix_sum[L - 1]
N, Q = map(int, input().split())
A = list(map(int, input().split()))
prefix_sum = calculate_prefix_sum(A)
for _ in range(Q):
L, R = map(int, input().split())
print(range_sum(prefix_sum, L, R))
위의 코드는 다음과 같은 과정을 수행합니다:
- 먼저, 주어진 배열 A의 길이 N에 대한 누적 합 배열을 계산하는 함수를 호출합니다.
- 각 질의에 대해 L과 R을 입력받고, 해당 구간의 합을 출력합니다.
시간 복잡도 분석
이 문제의 시간 복잡도를 분석해보면 다음과 같습니다:
- 누적 합 배열을 계산하는 데 O(N)의 시간이 소요됩니다.
- 각 질의에 대한 구간 합을 계산하는 데 O(1)의 시간이 소요됩니다.
- 따라서 전체 시간 복잡도는 O(N + Q)가 됩니다.
결론
구간 합 문제는 코딩 테스트에서 자주 출제되는 문제 중 하나입니다.
누적 합을 활용하면 문제를 효율적으로 해결할 수 있는 좋은 방법입니다.
이번 강좌에서 다룬 내용을 바탕으로 다양한 변형 문제들을 풀어보는 것도 좋습니다.
추가 질문이나 다른 알고리즘 문제에 대해 더 알고 싶다면 언제든지 댓글을 남겨주세요!