[알고리즘] 'N의 연속된 자연수의 합 찾기'와 투 포인터(Two Pointers) 알고리즘

N의 연속된 자연수의 합 찾기

---

n의 연속된 자연수의 합 찾기 분제는 입력값 N이 주어졌을 때, 1부터 N 사이의 연속된 자연수의 값을 합해 N이 되는 경우의 수를 구하는 문제이다. 예를들어 N = 15가 주어졌다면 1부터 15 사이의 자연수 중, 연속된 값을 합해 15가 되는 경우의 수 4가지(12345, 456, 78)을 구하는 문제이다. 

 

이 문제를 단순히 완전 탐색(Brute Force)으로 경우의 수를 구하려면 2중 루프를 돌아 O(n^2)의 시간 복잡도가 걸린다.

for (int start = 1; start <= N; start++) {
    int total = 0;
    for (int end = start; end <= N; end++) {
        total += end;
        if (total == N) {
            count++;
            break;          // N을 찾았으니 더할 필요 없음
        }
        if (total > N) break; // 넘어가면 중단
    }
}

 

 

 

투 포인터(Two Pointers) 알고리즘

---

두 개의 포인터(start, end)를 사용하여 구간을 확장/축소하며 조건을 만족하는 구간을 찾는 알고리즘이다. 포인터는 보통 배열의 시작과 끝을 나타낸다. 구간 조건에 따라 포인터를 확장하거나 축소하며 조건을 체크한다. 연속된 구간 문제, 슬라이딩 윈도우 문제, 문자열 탐색에서 자주 사용된다.

 

N의 연속된 자연수의 합 찾기를 투포인터 알고리즘으로 해결하면?

 

위 문제를 투포인터로 푼다면 start포인터와 end포인터를 한 방향으로만 움직이며 구간의 조건을 탐색하여 O(n)의 시간 복잡도가 나온다. 완전 탐색에서의 중복 연산 문제를 해결하고 연산 비용을 절감할 수 있다.

start와 end 사이의 구간 합을 저장하는 total 변수를 하나 두고, start와 end 포인터가 이동할때 해당 값만 total에 +, -해주면 완전 탐색에서의 중복 연산 문제를 피할 수 있다.

int start = 1, 
int end = 1;
int total = 1;     // start~end 구간 합
int count = 0;     // 경우의 수 result 

while (start <= N) {
    // 구간 발견, start++
    if (total == N) {
        count++;            
        total -= start;
        start++;
    }
    // 구간 확장
    else if (total < N) {
        end++;
        total += end;       
    }
    // 구간 축소
    else { // total > N
        total -= start;     
        start++;
    }

    if (end > N) break;      
}