[JS 알고리즘] 연속된 구간의 합(시간 초과) – 투 포인터 알고리즘(4)

연속 부분수열 알고리즘은 연속된 구간의 합을 효율적으로 계산하는 대표적인 코딩 테스트 문제 유형입니다. 이 글에서는 연속 부분수열 알고리즘 문제를 예제로 삼아, 잘못된 접근과 정답 접근의 차이를 단계별로 설명합니다.

• 문제
• 내가 푼 풀이 분석
• 정답 풀이 해설
• FAQ

연속 부분수열 알고리즘 문제

N개의 수로 이루어진 수열이 주어진다.
이 수열에서 연속부분수열의 합이 특정 숫자 M이 되는 경우가 몇 번 있는지 구하는 프로그램을 작성하시오.

입력
첫째 줄에 N(1≤N≤100,000), M(1≤M≤100,000,000)이 주어진다.
둘째 줄에 수열이 주어진다. 수열의 각 원소는 1,000을 넘지 않는 자연수이다.

예시
입력
5 5
1 3 1 2 3

출력
10

연속 부분수열 알고리즘 내가 푼 풀이

function solution(m, arr) {
    let result = 0;

    for (let i = 0; i < arr.length; i++) {
        let sum = 0;

        for (let j = i; j < arr.length; j++) {
            sum += arr[j];

            if (sum === m) result++;
            if (sum > m) break;
        }
    }

    return result;
}

이 풀이는 배열의 모든 인덱스를 시작점으로 삼아, 그 지점부터 뒤쪽으로 값을 하나씩 더해 가며 연속 부분수열의 합을 계산하는 방식입니다. 즉, 첫 번째 반복문에서 시작점 i를 정하면, 두 번째 반복문에서는 i부터 배열의 끝까지 이동하면서 매번 새로운 구간 합을 만들어 검사합니다.

이 접근 방식이 직관적인 이유는, 사람이 직접 종이에 문제를 풀 때 떠올리는 사고 과정과 매우 유사하기 때문입니다. “이 위치에서 시작하면 어떤 연속 구간들이 나올까?”를 하나씩 확인하는 방식이므로 논리적으로 틀리지는 않습니다. 실제로 입력 크기가 작다면 정답도 올바르게 나옵니다.

하지만 문제는 연산 횟수입니다. 배열의 길이가 N일 때, 첫 번째 시작점에서는 최대 N번, 두 번째 시작점에서는 N-1번, 세 번째는 N-2번의 연산이 발생합니다. 이를 모두 합치면 대략 N × N / 2에 가까운 연산이 수행되며, 시간 복잡도는 O(N²)이 됩니다.

이 문제에서는 N이 최대 100,000까지 주어질 수 있습니다. O(N²) 알고리즘은 이 경우 최악의 상황에서 수십억 번의 연산을 수행하게 되며, 자바스크립트 실행 환경에서는 제한 시간 안에 처리하는 것이 사실상 불가능합니다. 따라서 이 풀이는 문제의 입력 조건을 만족하지 못하는 비효율적인 풀이라고 판단할 수 있습니다.

연속 부분수열 알고리즘 정답 풀이

function solution(m, arr) {
    let answer = 0;
    let sum = 0;
    let lt = 0;

    for (let rt = 0; rt < arr.length; rt++) {
        sum += arr[rt];
        while (sum > m) {
            sum -= arr[lt++];
        }
        answer += (rt - lt + 1);
    }

    return answer;
}

이 정답 풀이는 투 포인터(슬라이딩 윈도우) 기법을 사용합니다. 먼저 코드의 전체 구조부터 보면, 하나의 반복문 안에서 두 개의 포인터 lt(왼쪽)와 rt(오른쪽)를 함께 움직이며 하나의 연속 구간을 유지합니다. 이 구간은 항상 lt부터 rt까지의 범위를 의미합니다.

가장 바깥의 for문에서 rt는 배열의 시작부터 끝까지 한 칸씩 이동합니다. 이때마다 sum += arr[rt]를 통해 현재 구간에 새로운 값을 하나 추가합니다. 즉, rt가 이동할 때마다 연속 부분수열의 오른쪽 경계가 확장되는 구조입니다.

이제 중요한 판단이 이루어지는 부분이 while (sum > m) 구문입니다. 배열의 모든 값이 자연수이기 때문에, 구간에 값을 추가하면 합은 반드시 커집니다. 따라서 sum이 목표 값 m을 초과하는 순간, 더 이상 오른쪽으로 확장해도 조건을 만족할 수 없습니다. 이때 왼쪽 포인터 lt를 이동시키며 구간을 줄이는 것이 가장 합리적인 선택입니다.

왼쪽 포인터가 이동할 때는 sum -= arr[lt]를 수행하여 실제 구간의 합과 포인터 위치를 항상 일치시킵니다. 이 과정을 통해 반복문이 끝났을 때는 항상 sum <= m인 상태가 유지됩니다. 즉, 현재 구간은 조건을 만족하거나, 조건에 가장 가까운 상태가 됩니다.

그 다음 실행되는 answer += (rt - lt + 1)은 이 알고리즘의 핵심입니다. 현재 구간이 lt ~ rt라면, 끝이 rt로 고정된 상태에서 시작점은 lt, lt + 1, lt + 2 … rt까지 모두 가능합니다. 이 모든 구간은 이미 sum <= m 조건을 만족하므로, 한 번에 그 개수를 누적할 수 있습니다.

이 방식의 가장 큰 장점은 각 포인터가 배열을 한 번씩만 이동한다는 점입니다. rt는 오른쪽으로만 이동하며 총 N번, lt 역시 왼쪽에서 오른쪽으로 최대 N번 이동합니다. 중첩 반복문이 존재하지 않기 때문에 전체 시간 복잡도는 O(N)이 되며, 입력 크기가 100,000인 경우에도 시간 초과 없이 안정적으로 동작합니다.

연속 부분수열 알고리즘 FAQ

Q. 왜 이중 반복문 풀이는 안 되나요?
입력 크기가 최대 100,000이기 때문에 O(N²) 방식은 실행 시간이 제한을 초과합니다.

Q. 투 포인터는 언제 사용하나요?
연속된 구간을 다루고, 모든 값이 양수일 때 특히 효과적으로 사용할 수 있습니다.

Q. 모든 배열 문제에 투 포인터를 쓸 수 있나요?
아닙니다. 값에 음수가 포함되면 슬라이딩 윈도우 방식은 성립하지 않을 수 있습니다.