투 포인터

🎯 학습 목표

이 강을 마치면 투 포인터 기법의 세 가지 형태를 구분하고, 각각이 왜 O(n)인지 설명할 수 있습니다. 그리고 이중 반복문으로 O(n²)이 되는 문제를 투 포인터로 O(n)으로 바꾸는 판단 기준을 갖게 됩니다.

투 포인터는 정렬이나 단조성이라는 성질을 이용해 불필요한 비교를 통째로 건너뛰는 기법입니다. 아이디어는 단순한데 적용 범위가 넓습니다.

💡 세 가지 형태

투 포인터는 두 개의 인덱스를 움직이며 배열을 훑는 방식입니다. 두 인덱스가 어떻게 움직이느냐에 따라 세 형태로 나뉩니다.

형태 1 — 양 끝에서 좁혀 오기 (정렬된 배열)

  [1, 3, 5, 7, 11]  에서 합이 12인 두 수 찾기
   ↑             ↑
  left         right

   1 + 11 = 12  → 찾았다

  합이 목표보다 작으면 → left 를 오른쪽으로 (합을 키운다)
  합이 목표보다 크면   → right 를 왼쪽으로  (합을 줄인다)

  ▲ 왜 O(n)인가
    left 는 오른쪽으로만, right 는 왼쪽으로만 간다.
    둘이 만나면 끝이므로 총 이동이 n번을 넘지 않는다.

  ▲ 왜 건너뛰어도 되는가 (정렬이 전제)
    1 + 11 이 목표보다 크다면
    1보다 큰 어떤 수 + 11 도 당연히 목표보다 크다.
    → 11과 짝지을 수 있는 후보가 통째로 사라진다


형태 2 — 같은 방향으로 따라가기 (구간 늘이고 줄이기)

  [2, 3, 1, 2, 4, 3]  에서 합이 7 이상인 최소 길이 구간

  right 를 늘려 합을 키우고,
  조건을 만족하면 left 를 늘려 구간을 줄인다

   left        right     구간합   동작
   0           0..2        6      늘린다
   0           0..3        8      조건 만족 → 길이 4 기록, left++
   1           1..3        6      다시 늘린다
   1..         ...

  ▲ 왜 O(n)인가
    left 와 right 가 각각 n번씩만 전진한다 → 최대 2n번


형태 3 — 두 배열을 동시에 훑기

  A = [1, 3, 5]   B = [2, 3, 6]   정렬된 두 배열 병합
   i                j

   A[i]=1 vs B[j]=2 → 1을 담고 i++
   A[i]=3 vs B[j]=2 → 2를 담고 j++
   ...
  → 9강 병합 정렬의 merge 가 정확히 이 형태다

세 형태의 공통점은 "인덱스가 되돌아가지 않는다"입니다. 되돌아가지 않으므로 각 원소를 상수 번만 보게 되고, 그래서 O(n)입니다.

📖 언제 투 포인터를 쓸 수 있는가

모든 이중 반복문을 투 포인터로 바꿀 수 있는 것은 아닙니다. 다음 조건 중 하나를 만족해야 합니다.

조건	의미	대표 문제
정렬돼 있다	한쪽을 움직이면 값이 단조롭게 변함	두 수의 합, 세 수의 합
값이 모두 양수	구간을 늘리면 합이 반드시 커짐	최소 길이 부분배열
조건이 단조적	만족하면 더 늘려도 만족	중복 없는 최장 부분문자열
양쪽이 정렬	두 배열을 순서대로 비교 가능	병합, 교집합

반대로 음수가 섞인 배열에서 구간합을 다룰 때는 투 포인터를 쓸 수 없습니다. 구간을 늘려도 합이 줄어들 수 있어 단조성이 깨지기 때문입니다. 이때는 누적합과 해시를 조합합니다(7강의 "지나온 것을 기억" 패턴).

판단 순서

  이중 반복문이 떠올랐다
        │
        ├─ 정렬해도 되는 문제인가?
        │     └─ 예 → 정렬 후 형태 1 검토
        │
        ├─ 구간(연속된 부분)을 다루는가?
        │     └─ 예 → 형태 2 검토
        │            ⚠️ 값이 모두 양수인지 확인
        │
        └─ 두 개의 정렬된 목록을 비교하는가?
              └─ 예 → 형태 3

  ▲ 어느 쪽도 아니면 해시(7강)나 이분 탐색(10강)을 본다

💻 실전 예제 — 세 형태 구현

def two_sum_sorted(arr, target):
    """정렬된 배열에서 합이 target 인 두 값 → O(n)"""
    left, right = 0, len(arr) - 1
    while left < right:
        total = arr[left] + arr[right]
        if total == target:
            return (arr[left], arr[right])
        elif total < target:
            left += 1                # 합을 키운다
        else:
            right -= 1               # 합을 줄인다
    return None


def min_subarray_len(nums, target):
    """합이 target 이상인 최소 길이 구간 (양수 배열) → O(n)"""
    left = 0
    total = 0
    best = len(nums) + 1
    for right, num in enumerate(nums):
        total += num                 # 오른쪽으로 늘린다
        while total >= target:       # 조건을 만족하는 동안
            best = min(best, right - left + 1)
            total -= nums[left]      # 왼쪽을 줄인다
            left += 1
    return best if best <= len(nums) else 0


def intersection(a, b):
    """정렬된 두 배열의 공통 원소 → O(n + m)"""
    i = j = 0
    result = []
    while i < len(a) and j < len(b):
        if a[i] == b[j]:
            result.append(a[i])
            i += 1
            j += 1
        elif a[i] < b[j]:
            i += 1                   # 작은 쪽만 전진
        else:
            j += 1
    return result


print(two_sum_sorted([1, 3, 5, 7, 11], 12))        # (1, 11)
print(min_subarray_len([2, 3, 1, 2, 4, 3], 7))      # 2  ([4,3])
print(intersection([1, 3, 5, 7], [3, 5, 9]))        # [3, 5]

코드를 줄 단위로 보겠습니다.

• while left < right — 두 인덱스가 만나면 종료합니다. <=로 하면 같은 원소를 두 번 쓰게 됩니다.
• elif total < target: left += 1 — 합이 작으므로 더 큰 값이 필요합니다. 정렬돼 있으니 오른쪽으로 가면 값이 커집니다. 이 판단이 정렬을 전제로 성립합니다.
• for right, num in enumerate(nums) — right가 자동으로 전진합니다. 바깥 반복은 정확히 n번입니다.
• while total >= target — if가 아니라 while입니다. 조건을 만족하는 동안 계속 줄여야 최소 길이를 찾습니다.
• total -= nums[left]; left += 1 — 왼쪽을 버리면서 합을 갱신합니다. 매번 구간합을 다시 계산하면 O(n²)가 되므로, 더하고 빼는 방식이 핵심입니다.
• 이중 반복문처럼 보이지만 left는 전체를 통틀어 n번만 전진합니다. 그래서 전체가 O(n)입니다.
• best = len(nums) + 1 — 불가능한 큰 값으로 시작해 갱신 여부를 판별합니다. 끝까지 안 바뀌면 답이 없다는 뜻입니다.
• elif a[i] < b[j]: i += 1 — 작은 쪽만 전진합니다. 큰 쪽은 아직 짝을 만날 가능성이 남아 있기 때문입니다.

min_subarray_len은 값이 모두 양수여야 성립합니다. 음수가 있으면 left를 옮겼을 때 합이 오히려 커질 수 있어 while 조건이 깨집니다.

⚠️ 자주 하는 실수

첫째, 정렬 없이 형태 1을 씁니다. "합이 목표보다 작으니 왼쪽을 전진"이라는 판단은 정렬을 전제합니다. 정렬 안 된 배열에서는 조용히 틀린 답이 나옵니다. 10강 이분 탐색과 같은 함정입니다.

둘째, 음수가 있는데 형태 2를 씁니다. 문제에 "양의 정수"라고 적혀 있는지 반드시 확인하세요. 음수가 섞이면 누적합과 해시로 접근해야 합니다.

셋째, 구간합을 매번 다시 계산합니다. sum(nums[left:right+1])을 반복문 안에서 부르면 O(n)이 곱해져 전체가 O(n²)가 됩니다. 더하고 빼서 갱신하세요.

넷째, while과 if를 헷갈립니다. 형태 2에서 안쪽을 if로 쓰면 한 칸만 줄이고 넘어가 최소 길이를 놓칩니다.

다섯째, 중복 처리를 빠뜨립니다. "세 수의 합" 같은 문제에서 같은 답이 여러 번 나올 수 있습니다. 같은 값은 건너뛰는 처리를 넣거나 결과를 집합으로 관리해야 합니다.

📝 핵심 요약 + 다음 강 예고

이번 강의 내용을 정리합니다.

#	기억할 것
1	투 포인터는 되돌아가지 않아서 O(n)
2	형태 1 — 양 끝에서 좁히기 (정렬 필수)
3	형태 2 — 구간 늘이고 줄이기 (양수 필수)
4	형태 3 — 두 배열 동시 훑기
5	구간합은 더하고 빼서 갱신
6	음수가 섞이면 누적합 + 해시
7	안쪽은 if가 아니라 while

지금 해 볼 것은 min_subarray_len에 음수가 섞인 배열을 넣어 보는 것입니다. 예를 들어 [2, -1, 5, 1]에 target 6을 넣으면 왜 답이 어긋나는지 확인해 보세요.

다음 12강 「슬라이딩 윈도우」에서는 투 포인터 형태 2를 고정 크기 창으로 특화한 기법을 다룹니다. 6강에서 덱으로 풀었던 구간 최댓값 문제를 이론적으로 정리하고, 창 안의 상태를 관리하는 표준 틀을 만들겠습니다.

📚 참고 자료

• enumerate() — Python 공식 문서
• Data Structures — Python 공식 문서
• TimeComplexity — Python Wiki