안녕하세요, 여러분! 오늘은 파이썬으로 하는 코딩테스트에서 자주 등장하는 구간 합 문제를 다루어 보겠습니다. 구간 합 문제는 특정 구간의 합을 빠르게 계산하는 방법을 묻는 문제로, 많은 알고리즘 문제의 기초가 되는 중요한 개념입니다. 다양한 접근 방식을 통해 이 문제를 해결하는 방법을 알아보겠습니다.
문제 설명
다음과 같은 배열이 주어질 때, 여러 쌍의 쿼리에 대해 특정 구간의 합을 효율적으로 구하는 프로그램을 작성하시오.
배열: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
쿼리: [(1, 3), (2, 5), (3, 7)]위 배열과 쿼리가 주어졌을 때, 쿼리는 (시작 인덱스, 끝 인덱스) 형태로 주어집니다. 예를 들어 (1, 3) 쿼리는 배열의 인덱스 1부터 인덱스 3까지 (1-based index) 합을 계산해야 하는 것을 의미합니다. 즉, 이 경우는 2 + 3 + 4 = 9가 되어야 합니다.
문제 접근 방법
구간 합 문제를 해결하기 위한 기본적인 접근 방식은 여러 가지가 있습니다. 가장 단순한 방법부터 시작해, 효율적인 방법까지 설명하겠습니다.
1. 단순 반복을 이용한 방법
가장 직관적인 방법은 단순히 요구된 구간의 합을 계산하는 것입니다. 쿼리가 적은 경우에는 이 방법이 좋지만, 쿼리가 많을 경우 비효율적입니다. 다음과 같은 방식으로 구현해 볼 수 있습니다.
def simple_range_sum(arr, queries):
results = []
for start, end in queries:
results.append(sum(arr[start - 1:end])) # 1-based index to 0-based index
return results
arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
queries = [(1, 3), (2, 5), (3, 7)]
print(simple_range_sum(arr, queries)) # 출력: [9, 14, 27]위와 같은 코드를 실행하면, 쿼리의 결과로 [9, 14, 27]이 출력됩니다. 그러나 이 방법의 시간 복잡도는 O(Q * N)으로, 여기서 Q는 쿼리의 개수, N은 배열의 크기입니다. 이는 큰 입력에 대해서는 비효율적임을 알 수 있습니다.
2. 누적 합 배열을 이용한 방법
더 효율적인 방식은 누적 합 배열을 만드는 것입니다. 누적 합 배열을 만들면 각 구간의 합을 O(1) 시간에 계산할 수 있습니다. 이 방법은 다음과 같습니다.
def prefix_sum(arr):
n = len(arr)
prefix = [0] * (n + 1)
for i in range(1, n + 1):
prefix[i] = prefix[i - 1] + arr[i - 1]
return prefix
def efficient_range_sum(arr, queries):
prefix = prefix_sum(arr)
results = []
for start, end in queries:
results.append(prefix[end] - prefix[start - 1]) # 1-based index adjustment
return results
arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
queries = [(1, 3), (2, 5), (3, 7)]
print(efficient_range_sum(arr, queries)) # 출력: [9, 14, 27]위 코드에서 누적 합 배열을 계산하는 데 O(N) 시간이 소요되고, 각 쿼리를 처리하는 데 O(1) 시간이 걸립니다. 따라서 전체 시간 복잡도는 O(N + Q)로 줄어듭니다. 이 방법으로 여러 쿼리를 효율적으로 처리할 수 있습니다.
문제 최적화와 선택
구간 합 문제는 다양한 상황에서 활용될 수 있으며, 선택하는 알고리즘은 문제의 조건에 따라 달라질 수 있습니다. 입력 배열의 크기와 쿼리의 개수, 각 쿼리의 구간 길이 등을 고려하여 최적의 방법을 선택하는 것이 중요합니다.
위에서 설명한 방법 외에도 세그먼트 트리와 같은 더 복잡한 자료구조를 사용할 수도 있지만, 이 강좌에서는 생활 속 문제를 해결하기 위한 기초적인 방법에 중점을 두었습니다. 다음 강좌에서는 보다 복잡한 동적 쿼리 문제를 다루어 보겠습니다.
결론
이번 강좌에서는 파이썬을 이용한 구간 합 문제를 다루어 보았습니다. 단순한 반복을 사용할 경우는 비효율적이지만, 누적 합 배열을 이용하면 훨씬 효율적으로 문제를 해결할 수 있음을 알 수 있었습니다. 구간 합 문제는 알고리즘 기초를 다지는 데 매우 유용한 주제이므로, 여러 번 연습해 보시고 다양한 변형 문제를 시도해 보시길 권장합니다!