스위프트 코딩테스트 강좌, 구간 합 구하기 1

서론

오늘의 강좌에서는 구간 합을 계산하는 문제에 대해 깊이 있게 다룰 것입니다. 이 문제는 여러 알고리즘 문제에서도 자주 등장하며, 효율적으로 해결하는 방법을 아는 것이 중요합니다.
이 글에서는 문제를 정의하고, 다양한 접근 방법을 설명하며, 최적의 해법을 찾기 위한 과정을 상세히 보여드리겠습니다.

문제 정의

배열 A가 주어지며, 두 개의 정수 L과 R가 주어질 때,
A[L] + A[L+1] + ... + A[R]의 값을 계산하시오.
단, A의 인덱스는 1부터 시작한다고 가정합니다.

입력

첫 번째 줄: 정수 N (1 ≤ N ≤ 100,000) – 배열의 크기
두 번째 줄: N개의 정수 A[1], A[2], ..., A[N] (-1,000,000 ≤ A[i] ≤ 1,000,000)
세 번째 줄: 정수 Q (1 ≤ Q ≤ 100,000) – 쿼리의 개수
다음 Q개의 줄: 각 쿼리는 두 정수 L와 R를 포함

출력

각 쿼리에 대해 구간 합 결과를 줄 단위로 출력하시오.

문제 접근 방법

이 문제를 해결하기 위해 여러 가지 방법을 생각할 수 있습니다. 간단히 모든 쿼리마다 직접 합계를 계산하는 방법도 있지만,
이는 시간 복잡도 측면에서 비효율적일 수 있습니다. 따라서 우리는 다음과 같은 접근 방식을 고려합니다.

1. 단순 반복을 통한 접근

가장 기본적인 방법은 각 쿼리에 대해 반복문을 사용하여 직접 구간 합을 계산하는 것입니다.
이 방법의 시간 복잡도는 O(N)이며, 쿼리가 Q개일 경우 O(N*Q)입니다.
이는 N과 Q가 모두 최대 100,000일 경우 최악의 상황에서 10억 번의 계산을 요구하게 되어 불가능합니다.

2. 누적 합 배열 사용하기

따라서 누적 합 배열을 사용하여 문제를 해결하는 방법이 더 효율적입니다. 누적 합 배열을 사용하면
구간 합을 O(1) 시간 복잡도로 해결할 수 있습니다. 누적 합 배열을 만들어 선형적으로 데이터를 전처리한 후,
각 쿼리에 대해 O(1) 시간 복잡도로 결과를 얻을 수 있습니다.

누적 합 배열 정의

배열 p를 다음과 같이 정의하겠습니다:
p[i] = A[1] + A[2] + ... + A[i]
이렇게 하면 구간 합 A[L] + A[L+1] + ... + A[R]는
p[R] - p[L-1]로 쉽게 계산할 수 있습니다.

구현

이제 실제로 구현을 해보겠습니다. Swift를 사용하여 알고리즘을 작성하겠습니다.


    import Foundation

    // 입력 받기
    let n = Int(readLine()!)!
    let a = readLine()!.split(separator: " ").map { Int($0)! }
    let q = Int(readLine()!)!

    // 누적 합 배열을 초기화
    var p = [0] + a
    
    // 누적 합 배열 생성
    for i in 1..

결과 및 분석

위 코드는 O(N) 시간 complexity로 입력을 받아 누적 합 배열을 만들고,
각 쿼리에 대해 O(1) 시간에 답을 출력합니다.
최악의 경우, 입력을 받는 데 가정한 시간 사용을 고려할 때 전체 시간 복잡도는 O(N + Q)입니다.

최적화된 접근법에 대한 이점

이 방법은 특히 큰 입력 데이터에서 성능이 매우 우수하게 나타납니다.
누적 합을 사용한 결과로 인해 쿼리가 많아도 효율적으로 대응할 수 있습니다.
이와 같은 문제 해결 방법은 다른 문제에도 적용할 수 있으며, 기본적인 데이터 구조 이해를 요구합니다.

결론

오늘은 구간 합 구하기 문제를 통해 누적 합 배열을 활용한 효율적인 문제 해결 방법에 대해 알아보았습니다.
실질적으로 많은 알고리즘 문제에서 이러한 기법을 사용하므로 반드시 숙지해두시기 바랍니다.
다음 강좌에서는 이와 유사한 다른 문제들을 다뤄볼 예정입니다.
여러분의 코딩 테스트 준비에 도움이 되었으면 좋겠습니다.

서론