파이썬 코딩테스트 강좌, 구간 합 구하기 1

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. 예제 입력 및 출력

예제 입력

예제 출력

    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. 질문 및 피드백

이 글에서 다룬 내용에 대해 궁금한 점이나 피드백이 있다면 댓글로 남겨주세요. 함께 문제를 해결해보아요!