5주차

Two Pointers / Sliding Window

요약

🖱️ Two Pointers (투 포인터)

1차원 배열이나 리스트를 다룰 때 두 개의 포인터(인덱스)를 조작하며 원하는 조건을 만족하는 결과를 찾는 알고리즘이다.

특징

• 두 개의 포인터(인덱스)를 조작하여 원하는 조건을 만족하는 결과를 탐색한다.
• 완전 탐색(이중 for문)으로 O(N^2)의 시간이 걸리는 작업을 O(N)으로 단축시킬 수 있다는 것이 가장 큰 핵심이다.
• 정렬된 배열에서의 탐색, 연속된 부분 배열(수열)의 처리와 깊게 연결되어 있다.

개념

🖱️ Two Pointers (투 포인터)

이름 그대로 두 개의 포인터(시작점과 끝점, 혹은 두 개의 이동점)를 사용하여 배열을 탐색하는 방식이다.

특징

• 보통 1차원 배열에서 두 개의 포인터를 조작한다.
• 반복문 내에서 두 포인터가 각자의 조건에 따라 이동 방향과 속도를 결정한다.
• 한 번 이동한 포인터는 뒤로 돌아가지 않으므로(역방향 이동 불가), 전체 배열을 한 번만 순회하게 되어 시간 복잡도 O(N)을 보장한다.
• 슬라이딩 윈도우와 자주 비교되며, 문제에 따라 혼용되어 쓰이기도 한다.

동작 방식의 종류

1. 양방향 포인터

• 하나의 포인터는 배열의 처음(Left), 다른 하나는 배열의 끝(Right)에서 시작한다.
• 주로 정렬된 배열에서 두 수의 합이나 차를 구할 때 사용된다.
• 조건에 따라 Left를 증가시키거나, Right를 감소시키며 서로 만날 때까지 가운데로 좁혀온다.

2. 동방향 포인터

• 두 포인터 모두 배열의 처음(Start, End)에서 같은 방향으로 출발한다.
• 주로 연속된 부분 수열의 합이나 길이를 구할 때 사용된다.
• 조건에 따라 End를 전진시켜 구간을 넓히거나, Start를 전진시켜 구간을 좁히며 탐색한다.

Two Pointers vs 완전 탐색 비교

어떤 상황에서 투 포인터를 떠올려야 할까?

1. 배열 안에서 두 요소의 합 또는 차를 구해야 하는데 입력 크기(N)가 100,000 이상이라서 O(N) 또는 O(N log N)으로 풀어야 한다면? ➡ 투 포인터 (양방향)
2. 연속된 부분 배열이나 수열의 합이 특정 값이 되는 구간을 찾아야 한다면? ➡ 투 포인터 (동방향)

참고: 양방향 투 포인터를 사용할 때, 배열이 정렬되어 있지 않다면 먼저 정렬O(N log N)을 수행해야 한다. 정렬 시간을 포함하더라도 O(N^2)보다 훨씬 빠르다.

문제 패턴

투 포인터 문제는 대부분 포인터의 이동 조건을 묻는 경우가 많으며, 다음과 같은 패턴이 등장하면 투 포인터 문제일 가능성이 높다.

📚 패턴 1: 양끝에서 좁혀오기 (정렬된 배열)

1. 문제에서 자주 나오는 형태

1. 정렬된 배열에서 두 수의 합이 Target이 되는 쌍 찾기
2. 세 수의 합이 0이 되는 조합 찾기
3. 가장 두 물의 양이 많은 용기 찾기 (수조 문제)

2. 접근 방법

1. 배열을 오름차순으로 정렬한다.
2. Left = 0, Right = 배열의 길이 - 1로 초기화한다.
3. 두 값의 합이 Target보다 크면 Right를 왼쪽으로 이동(값을 줄임).
4. 두 값의 합이 Target보다 작으면 Left를 오른쪽으로 이동(값을 키움).

📚 패턴 2: 같은 방향에서 전진하기 (연속 부분 수열)

1. 문제에서 자주 나오는 형태

1. 연속된 부분 수열의 합이 Target이 되는 경우의 수 찾기
2. 합이 Target 이상이 되는 가장 짧은 연속 구간 길이 구하기

2. 접근 방법

1. Start = 0, End = 0으로 초기화한다.
2. 현재 구간의 합이 Target보다 작거나 같으면 End를 오른쪽으로 이동하여 합을 증가시킨다.
3. 현재 구간의 합이 Target보다 크거나 같으면 (또는 조건 만족 시) Start를 오른쪽으로 이동하여 구간을 좁히고 합을 감소시킨다.

예시 문제 기반 설명

예시 문제 기반 설명 2 (동방향 투 포인터)

📝 연속된 자연수의 합 (프로그래머스: 숫자의 표현)

자연수 n이 매개변수로 주어질 때, 연속된 자연수들로 n을 표현하는 방법의 수를 반환하라! (예: 15는 1+2+3+4+5, 4+5+6, 7+8, 15로 총 4가지 방법으로 표현할 수 있다.)

문제 접근 방법

연속된 수열의 합을 구하는 문제이므로, 두 포인터가 같은 방향으로 전진하는 동방향 투 포인터(또는 슬라이딩 윈도우)를 사용한다.

1. 두 포인터 start와 end를 모두 1로 초기화한다.

2. start부터 end까지의 합을 sum이라고 할 때, sum과 목표값 n을 비교하며 포인터를 이동시킨다.

1. sum == n : 조건을 만족하므로 경우의 수(정답)를 1 증가시킨다. 그리고 새로운 구간을 탐색하기 위해 sum에서 start 값을 빼고, start를 오른쪽으로 한 칸 이동시킨다. (구간 축소)
2. sum < n : 현재 합이 부족하므로 구간을 넓혀야 한다. ➡ end를 오른쪽으로 한 칸 이동시키고, 새로운 end 값을 sum에 더한다.
3. sum > n : 현재 합이 넘치므로 구간을 좁혀야 한다. ➡ sum에서 현재 start 값을 빼고, start를 오른쪽으로 한 칸 이동시킨다.

3. start가 n 이하일 때까지 위 과정을 반복한다.

예시

n = 15인 경우를 예로 들어 보겠습니다.

1. start = 1, end = 1 ➡ 합: 1 (15보다 작으므로 end 증가)
2. start = 1, end = 5 ➡ 합: 15 (정답 도출! 카운트 증가 후 start를 빼서 합을 줄이고 start 전진)
3. start = 2, end = 5 ➡ 합: 14 (15보다 작으므로 end 증가)
4. .. 이런 식으로 꼬리를 물며 이동합니다!

참고

시간 복잡도 : $O(N)$ (이중 for문으로 O(N^2) 탐색을 하면 시간 초과가 날 수 있으나, 투 포인터는 각 포인터가 최대 n번만 이동하므로 빠르다.)

JavaScript

function solution(n) {
    let answer = 0;
    let start = 1;
    let end = 1;
    let sum = 1; // start부터 end까지의 합

    while (start <= n) {
        if (sum === n) {
            answer++; // 정답 카운트
            sum -= start; // 현재 start 값을 빼고
            start++; // start를 오른쪽으로 이동
        } else if (sum < n) {
            end++; // end를 오른쪽으로 이동하고
            sum += end; // 새로운 end 값을 더함
        } else { // sum > n
            sum -= start; // 현재 start 값을 빼고
            start++; // start를 오른쪽으로 이동
        }
    }

    return answer;
}

1. 시작점 start와 끝점 end를 1로 두고, 초기 합(sum)도 1로 설정한다.
2. 매번 반복문을 돌면서 1부터 n까지 일일이 합을 다시 구하지 않고, 포인터가 이동할 때마다 양 끝 값만 더하거나 빼주어 연산을 최소화한다.
3. 합이 n보다 작으면 end를 전진시켜 합을 키우고, 크거나 같으면 start를 전진시켜 합을 줄이면서 탐색을 이어나간다.

Python

def solution(n):
    answer = 0
    start = 1
    end = 1
    total_sum = 1
    
    while start <= n:
        if total_sum == n:
            answer += 1
            total_sum -= start
            start += 1
        elif total_sum < n:
            end += 1
            total_sum += end
        else:
            total_sum -= start
            start += 1
            
    return answer

1. 파이썬의 내장 함수 sum()을 매번 호출하면 슬라이싱하는 데 O(N)이 걸려 전체 O(N^2)이 되므로, total_sum이라는 정수 변수에 값을 직접 더하고 빼는 방식이 핵심이다.
2. start와 end를 조건에 맞게 우측으로만 이동시키며 경우의 수를 찾는다.

Java

class Solution {
    public int solution(int n) {
        int answer = 0;
        int start = 1;
        int end = 1;
        int sum = 1;

        while (start <= n) {
            if (sum == n) {
                answer++;
                sum -= start;
                start++;
            } else if (sum < n) {
                end++;
                sum += end;
            } else {
                sum -= start;
                start++;
            }
        }

        return answer;
    }
}

1. 로직은 JavaScript와 완벽히 동일하다.
2. 이중 반복문(for 문 두 개)을 사용했을 때 발생할 수 있는 불필요한 중복 연산을, sum 변수 하나를 유지하며 더하고 빼는 방식으로 O(N)의 시간 복잡도로 최적화했다.

실수 포인트

1️⃣ 정렬 여부를 확인하지 않은 경우 (양방향 투 포인터)

양끝에서 좁혀오는 투 포인터 로직은 '배열이 오름차순으로 정렬되어 있다는 가정' 하에 성립한다. 정렬되지 않은 배열에서 크기 비교를 통해 포인터를 이동시키면 전혀 엉뚱한 결과를 낳게 된다. 입력된 배열이 정렬되어 있는지 반드시 확인하고, 안 되어 있다면 먼저 정렬(sort())을 수행해야 한다.

2️⃣ 종료 조건(while문 조건)의 오류

while (left <= right)를 써야 할지, while (left < right)를 써야 할지 헷갈려 하는 경우가 많다.

• 서로 다른 두 원소를 골라야 하는 위와 같은 문제에서는 left < right가 맞다. (<=를 쓰면 같은 원소를 두 번 더하는 꼴이 될 수 있음)
• 문제의 요구사항에 따라 하나의 원소를 중복해서 선택해도 되는 상황이라면 범위를 다르게 설정해야 하므로 주의가 필요하다.

3️⃣ 동방향 포인터(연속 부분 배열)에서의 Out of Bounds (배열 범위 초과)

start와 end가 같은 방향으로 이동하는 문제에서, end가 배열의 끝을 넘어갔음에도 계속 인덱스에 접근하려고 하면 에러(Index Out Of Bounds)가 발생한다. 반복문 안에서 포인터가 배열의 길이(N)를 초과하지 않도록 안전하게 예외 처리를 해두는 습관이 필요하다.