[알고리즘 / 백준 / Swift] 투 포인터와 누적합 - 백준 2003

 

활동하는 스터디 내에서 공부한 뒤 작성된 포스트입니다.

오늘은 투 포인터 알고리즘에 대해 설명해 보겠습니다.

투 포인터 알고리즘을 배우려면 누적합의 개념에 대해서도 알고 가면 좋기 때문에,

이 포스트에서 누적합과 투 포인터 두 가지 개념에 대해 설명하겠습니다.

 

# 투 포인터

먼저 투 포인터에 대해 알아 보겠습니다.

일련적인 배열에서 연속적인 값을 표현할 때는 구간으로 해당 영역의 표현이 가능합니다.

예를 들어 2 부터 7 인덱스는 2, 3, 4, 5, 6, 7 로 표현하지만 시작점과 끝점을 이용하여 2 부터 7 인덱스로 표현이 가능합니다.

 

 투 포인터 알고리즘으 구간의 개념을 이용한 알고리즘입니다.

PS 에서 배열을 순회하여 특정 조건을 찾는 문제가 있습니다.

하지만 배열을 순회하며 너무 많은 연산을 진행하게 되면 시간 초과가 발생합니다.

즉, 시간 복잡도가 꽝인 효율적이지 못한 코드가 됩니다.

 

투 포인터 알고리즘은 배열을 순서대로 순회하며 시작점과 끝점의 인덱스를 기록하며 처리하는 알고리즘입니다.

예를 들어 설명해 보겠습니다.

배열의 합이 10 인 특정 구간의 개수를 구하는 문제라고 생각을 해 보겠습니다.

이때는 문제를 누적합을 이용해서 풀어야 합니다. 누적합의 개념은 밑에서 설명해 보겠습니다.

다시 문제로 돌아가서 배열의 누적합을 구하고 순회한 뒤 모든 누적합의 경우의 수를 확인하여 10 인 구간을 찾은 뒤,

구간이 존재하는 경우 +1 을 해 주며 문제를 해결해나가는 방식입니다.

 

# 누적합

그렇다면 누적합은 무엇일까요?

누적합은 숫자의 집합에서 첫 번째 값부터 마지막 값까지 순차적으로 더해가면서 합계를 계산하는 방법입니다.

집합의 각 위치까지의 합이 얼마나 되는지 알 수 있습니다.

간단히 예를 들면,

숫자들이 들어있는 배열 [2, 3, 5, 7] 이 있다고 할 때, 이 배열의 누적합을 구하면 각 위치까지의 합계를 구해야 합니다.

1. 첫 번째 값인 2 의 누적합 2
2. 두 번째 값인 2 +  3 = 5
3. 세 번째 값인 5 + 5 = 10
4. 네 번째 값 10 + 7 = 17

이렇게 더해가면서 누적합을 17 로 구할 수 있습니다.

 

따라서, [2, 3, 5, 7] 의 누적합은 [2, 5, 10, 17] 이 됩니다.

이렇게 배열의 처음부터 끝까지의 합계를 누적하며 기록하는 것이 누적합이라고 정리할 수 있습니다.

 

# 투 포인터와 누적합

이 두 알고리즘을 적절히 섞어 사용하면 효과적인 순회가 가능하기에 동작이 빨라지고 시간 복잡도가 효율적인 코드를 작성할 수 있습니다.

투 포인터 알고리즘을 누적합에 도입하게 된다면,

누적합을 순회하되, 시작점과 끝점을 기록하며 순서대로 진행되게 됩니다.

시작과 끝을 0 으로 시작하여 누적합을 계산해 보았을 때,

1. 10 인 경우 +1 
2. 10 보다 작은 경우 끝에 +1
3. 10 보다 크거나 같은 경우는 시작점에서 +1

이 과정은 반복하며 시작점이 끝점보다 커질 때, 끝점이 마지막 인덱스보다 커질 때까지 반복해 줍니다.

 

# 문제 풀이

백준의 2003 번 수들의 합 2 문제를 통해 누적합과 투 포인터의 혼용 코드를 작성해 보겠습니다.

 

문제

N개의 수로 된 수열 A[1], A[2], …, A[N] 이 있다. 이 수열의 i번째 수부터 j번째 수까지의 합 A[i] + A[i+1] + … + A[j-1] + A[j]가 M이 되는 경우의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N(1 ≤ N ≤ 10,000), M(1 ≤ M ≤ 300,000,000)이 주어진다. 다음 줄에는 A[1], A[2], …, A[N]이 공백으로 분리되어 주어진다. 각각의 A[x]는 30,000을 넘지 않는 자연수이다.

출력

첫째 줄에 경우의 수를 출력한다.

 

예제 입력

4 2
1 1 1 1

 

예제 출력

3

 

---

Swift 로 이 문제를 풀어 보았습니다.

// 1. 입력을 받는다.
let input = readLine()!.split(separator: " ").map { Int(String($0))! }
let (n, m) = (input[0], input[1])
let arr = readLine()!.split(separator: " ").map { Int(String($0))! }

// 2. 풀이를 작성한다.
// 2-1. 누적합을 구한다.
var pSum = Array(repeating: 0, count: n+1)
for i in 1 ... n {
    pSum[i] = pSum[i - 1] + arr[i - 1]
}

// 2-2. 누적합에서 투 포인터 배열을 순회한다.
var ans = 0
var (start, end) = (0, 0)
while start <= end && end < n + 1 {
    /// 합이 M 이랑 같으면 +1
    /// 합이 작으면 end + 1
    /// 합이 크거나 같으면 start +1
    let sum = pSum[end] - pSum[start]
    if sum == m { ans += 1 }
    if sum < m { end += 1 }
    else { start += 1 }
}

// 3. 정답을 출력한다.
print(ans)