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

이번 강좌에서는 스위프트를 사용하여 구간 합 문제를 해결하는 방법에 대해 알아보겠습니다.

문제 설명

다음과 같은 문제를 고려해 보겠습니다.

정수 N개로 이루어진 배열 A와, M개의 질의가 주어진다. 각 질의는 두 정수 i, j로 주어지며, A[i]부터 A[j]까지의 합을 구하라.

배열의 크기 N과 질의의 개수 M은 다음과 같다:

1 ≤ N, M ≤ 100,000

-10,000 ≤ A[i] ≤ 10,000

1 ≤ i ≤ j ≤ N

입력 예제

입력 형식은 다음과 같다:

위의 입력에서 첫 번째 줄은 배열의 크기 N과 질의의 개수 M을 의미합니다. 두 번째 줄은 배열 A의 요소들입니다. 그 이후의 M줄은 각 질의를 나타냅니다.

출력 예제

입력의 각 질의에 대해 합을 출력해야 합니다.

        6
        9
        15

문제 풀이 방법

이 문제를 해결하기 위한 효율적인 방법은 누적 합을 사용하는 것입니다. 즉, 배열 A의 누적 합을 미리 계산해 놓으면 각 질의의 합을 상수 시간에 구할 수 있습니다.

1단계: 누적 합 계산

누적 합 배열 prefixSum을 생성하여, prefixSum[i]는 배열 A의 첫 번째 요소부터 i번째 요소까지의 합을 저장합니다.

    let N = 5
    let A = [1, 2, 3, 4, 5]
    var prefixSum = [Int](repeating: 0, count: N + 1)

    for i in 1...N {
        prefixSum[i] = prefixSum[i - 1] + A[i - 1]
    }

2단계: 질의 처리

질의를 처리할 때는 prefixSum[j] - prefixSum[i - 1]를 사용하여 i부터 j까지의 합을 구합니다. 이를 통해 각 질의의 시간 복잡도는 O(1)이 됩니다.

    let queries = [(1, 3), (2, 4), (1, 5)]
    for query in queries {
        let i = query.0
        let j = query.1
        let result = prefixSum[j] - prefixSum[i - 1]
        print(result)
    }

전체 코드

위의 설명을 종합하여 전체 코드는 다음과 같습니다.

    let firstLine = readLine()!.split(separator: " ").map { Int($0)! }
    let N = firstLine[0] // 배열의 크기
    let M = firstLine[1] // 질의의 개수

    let A = readLine()!.split(separator: " ").map { Int($0)! }
    var prefixSum = [Int](repeating: 0, count: N + 1)

    for i in 1...N {
        prefixSum[i] = prefixSum[i - 1] + A[i - 1]
    }

    for _ in 0..

    시간 복잡도
    이 알고리즘의 시간 복잡도는 O(N + M)입니다. N은 배열 A의 크기이고, M은 질의의 개수입니다. A의 요소를 모두 더하는 O(N)과 M개의 질의를 처리하는 O(M)이 합쳐졌기 때문입니다.

    결론
    이번 강좌에서는 구간 합 문제를 해결하기 위해 누적 합을 활용하는 방법을 배웠습니다. 이 방법을 통해 성능을 크게 개선할 수 있습니다. 앞으로 유사한 문제를 해결할 때 이 기법을 활용하시기 바랍니다.