5. 투 포인터

두 개의 인덱스를 양쪽 또는 같은 방향에서 움직여, 이중 반복(O(n²))을 선형(O(n))으로 줄이는 기법입니다. 정렬된 배열에서 "두 수의 합" 같은 문제의 단골 해법이에요. 발상 자체는 아주 단순합니다. "모든 짝을 다 확인하지 말고, 지금 값을 보고 어느 포인터를 움직일지 결정해서 확인할 짝을 확 줄이자."

이 한 챕터에서 배우는 것:

• 양끝에서 좁혀오는 양끝 포인터로 정렬된 배열의 두 수의 합 풀기
• 투 포인터가 왜 O(n²)를 O(n)으로 줄이는지 (확인을 통째로 건너뛰는 원리)
• 정렬이라는 전제가 왜 반드시 필요한지
• 한 방향으로 같이 나아가는 같은 방향 포인터 (구간/윈도우 문제)

왜 필요할까: 완전탐색의 벽

"정렬된 배열에서 더해서 target이 되는 두 수를 찾아라." 자료구조/해시 챕터에서 본 문제죠. 가장 먼저 떠오르는 건 모든 짝을 다 확인하기(완전탐색) 입니다. 소수 챕터에서 배운 그 사고 흐름 그대로예요.

def two_sum_brute(arr, target):
    n = len(arr)
    for i in range(n):
        for j in range(i + 1, n):     # i 뒤의 모든 짝
            if arr[i] + arr[j] == target:
                return (arr[i], arr[j])
    return None

print(two_sum_brute([1, 3, 4, 6, 8, 10], 14))   # (4, 10)
print(two_sum_brute([1, 3, 4, 6, 8, 10], 100))  # None

반복문이 이중으로 겹쳐 있으니 최악의 경우 약 n × n / 2번 확인합니다. 이게 O(n²) 예요.

• n = 1,000 → 약 50만 번 (괜찮음)
• n = 100,000 → 약 50억 번 😱 (시간 초과)

💡 이중 반복문이 보이면 일단 O(n²) 를 의심하세요. 소수 챕터에서 배웠듯, 보통 컴퓨터는 1초에 약 1억 번 연산합니다. n이 10만만 넘어가도 O(n²)는 위험 신호예요.

양끝 포인터: 양쪽에서 좁혀오기

배열이 정렬돼 있다는 사실을 이용하면 이중 반복을 없앨 수 있습니다. 포인터 두 개를 맨 왼쪽(lo)과 맨 오른쪽(hi) 에 놓고, 둘의 합을 보면서 한 칸씩 좁혀옵니다.

핵심은 합이 목표와 다를 때 어느 쪽을 움직일지 정하는 규칙입니다.

• arr[lo] + arr[hi] == target → 찾았다! 끝.
• arr[lo] + arr[hi] < target → 합을 키워야 함 → 작은 쪽인 lo를 오른쪽으로 (lo += 1)
• arr[lo] + arr[hi] > target → 합을 줄여야 함 → 큰 쪽인 hi를 왼쪽으로 (hi -= 1)

def two_sum_sorted(arr, target):
    lo, hi = 0, len(arr) - 1
    while lo < hi:                     # 포인터가 엇갈리기 전까지
        s = arr[lo] + arr[hi]
        if s == target:
            return (arr[lo], arr[hi])  # 찾음
        elif s < target:
            lo += 1                    # 합이 작으니 왼쪽을 키운다
        else:
            hi -= 1                    # 합이 크니 오른쪽을 줄인다
    return None                        # 못 찾음

print(two_sum_sorted([1, 3, 4, 6, 8, 10], 14))   # (4, 10)
print(two_sum_sorted([1, 3, 4, 6, 8, 10], 7))    # (1, 6)
print(two_sum_sorted([1, 3, 4, 6, 8, 10], 100))  # None

target = 14일 때 실제로 어떻게 좁혀오는지 따라가 볼까요.

[1, 3, 4, 6, 8, 10]
 lo=0(1), hi=5(10) → 합 11 < 14 → lo++
 lo=1(3), hi=5(10) → 합 13 < 14 → lo++
 lo=2(4), hi=5(10) → 합 14 == 14 → 찾음! (4, 10)

왜 O(n²)가 O(n)이 될까

완전탐색은 lo를 하나 고정할 때마다 그 오른쪽 전부를 다시 훑었습니다. 투 포인터는 그 되돌아가는 재확인을 통째로 없애요.

비결은 한 번 움직일 때마다 "확인할 짝 한 무더기를 통째로 버린다" 는 데 있습니다. 예를 들어 arr[lo] + arr[hi] < target이라 lo를 올리기로 했다면, 이건 곧 "현재 lo와 짝지을 수 있는 그 어떤 값도 답이 될 수 없다" 는 뜻입니다. 왜냐하면 arr[hi]는 남은 것 중 가장 큰 값인데, 그것과 더해도 모자랐으니 더 작은 값들과는 볼 것도 없거든요. 그래서 lo를 다시는 쳐다보지 않고 버립니다.

lo와 hi는 서로를 향해서만 움직이고 절대 되돌아가지 않습니다. 둘이 만나면 끝. 그래서 두 포인터가 움직이는 총 횟수는 배열 길이 n을 넘지 않아요. 이게 O(n) 입니다.

💡 완전탐색은 "짝을 하나 확인 = 한 걸음"이라 총 걸음이 n²이었습니다. 투 포인터는 "포인터를 한 칸 옮김 = 한 걸음"인데 포인터가 총 n칸밖에 못 가니 n걸음이에요. "짝을 세지 말고 포인터의 이동을 세라" — 이 관점 전환이 핵심입니다.

정렬이라는 전제

투 포인터의 판단 규칙(합이 작으면 lo++, 크면 hi--)은 "오른쪽으로 갈수록 값이 커진다" 는 정렬 순서에 전적으로 기댑니다. 정렬돼 있지 않으면 lo++를 해도 합이 커진다는 보장이 없어서 규칙이 무너져요.

그래서 입력이 정렬돼 있지 않다면 먼저 정렬하고 시작합니다.

def two_sum_any(arr, target):
    arr = sorted(arr)                 # O(n log n) 정렬 후
    lo, hi = 0, len(arr) - 1
    while lo < hi:
        s = arr[lo] + arr[hi]
        if s == target:
            return (arr[lo], arr[hi])
        elif s < target:
            lo += 1
        else:
            hi -= 1
    return None

print(two_sum_any([8, 1, 10, 3, 6, 4], 14))   # (4, 10)

정렬 비용 O(n log n)이 붙어서 전체는 O(n log n) 이 됩니다. 그래도 O(n²)보다 훨씬 빠르죠.

💡 해시 챕터의 two_sum은 딕셔너리로 정렬 없이 O(n) 에 풀었습니다. "짝의 값 하나만" 찾을 땐 해시가 더 빠를 수 있어요. 하지만 이미 정렬돼 있거나, 세 수의 합처럼 정렬이 어차피 필요한 문제에서는 투 포인터가 추가 메모리 없이 깔끔합니다. 도구는 상황에 맞게 고르는 겁니다.

같은 방향 포인터: 나란히 나아가기

양끝 포인터만 투 포인터가 아닙니다. 포인터 둘이 같은 방향(왼→오)으로 나란히 움직이며 그 사이 구간을 다루는 방식도 있어요. "합이 조건을 만족하는 가장 짧은 연속 구간" 같은 문제에 씁니다. 흔히 슬라이딩 윈도우라고도 불러요.

right로 구간을 오른쪽으로 넓혀 값을 더하고, 조건을 넘으면 left로 왼쪽을 좁혀 값을 뺍니다. 창문 하나가 배열 위를 미끄러지듯 지나가는 그림이에요.

def min_window(arr, target):
    # 합이 target 이상이 되는 가장 짧은 연속 구간의 길이
    left = 0
    total = 0
    best = len(arr) + 1               # "아직 못 찾음"을 뜻하는 큰 값
    for right in range(len(arr)):
        total += arr[right]           # 오른쪽을 넓히며 더함
        while total >= target:        # 조건을 만족하는 동안
            best = min(best, right - left + 1)
            total -= arr[left]        # 왼쪽을 좁히며 뺌
            left += 1
    return best if best <= len(arr) else 0

print(min_window([2, 3, 1, 2, 4, 3], 7))   # 2   (구간 [4, 3])
print(min_window([1, 1, 1, 1], 7))         # 0   (아예 못 만듦)

right는 전체를 한 번 훑고, left도 앞으로만 가며 전체를 한 번 훑습니다. 각자 되돌아오지 않으니 안쪽 while이 있어도 총 이동은 약 2n번, 즉 O(n) 이에요. 겉보기엔 이중 반복 같지만 O(n²)가 아니라는 점이 포인트입니다.

💡 while이 for 안에 있다고 무조건 O(n²)는 아닙니다. 안쪽 포인터가 바깥 반복 전체에서 딱 n번만 전진한다면 합쳐서 O(n)이에요. 투 포인터·슬라이딩 윈도우의 복잡도는 이렇게 "총 이동 횟수"로 따져야 정확합니다.

정리

💡 소수 챕터의 사고 틀을 그대로 적용한 챕터였어요. ① 완전탐색으로 일단 풀고 → ② O(n²)임을 확인하고 → ③ 정렬이라는 성질을 관찰해 포인터로 범위를 확 줄인다. 투 포인터는 "이중 반복을 선형으로 접는" 대표적인 도구입니다.

직접 풀어보기

1. two_sum_sorted를 고쳐서, 짝이 아니라 두 수의 인덱스를 반환하게 만들어 보세요. (힌트: return (lo, hi))
2. 정렬된 배열에서 합이 target이 되는 모든 짝의 개수를 세보세요. (힌트: 찾았을 때 멈추지 말고 lo += 1; hi -= 1로 양쪽을 동시에 좁히며 계속 진행)
3. min_window를 응용해, 합이 정확히 target이 되는 연속 구간이 존재하는지 판별해 보세요. (힌트: 모든 값이 양수라면 윈도우 합이 넘칠 때 왼쪽을 좁히면 됩니다.)