투 포인터와 슬라이딩 윈도우 기법 쉽게 이해하기

이 기법들이 해결하는 문제

배열과 문자열 문제 중에는 쌍이나 연속 구간을 묻는 것이 많습니다. 합이 목표 값이 되는 두 수, 반복 문자가 없는 가장 긴 부분 문자열, 합이 k 이상인 가장 짧은 부분 배열 같은 문제입니다. 모든 쌍이나 모든 구간을 확인하면 O(n²) 이상이 듭니다. 투 포인터는 정렬된 순서나 윈도우에 작은 갱신만 필요하다는 점 같은 데이터의 성질을 이용해 많은 후보를 한꺼번에 제외합니다.

양 끝 포인터: 정렬된 배열의 두 수 합

정렬된 리스트 [1, 3, 4, 6, 8, 11]에서 합이 10인 두 수를 찾아 봅시다. 가장 작은 값과 가장 큰 값에서 시작합니다. 합이 너무 작으면 키울 방법은 left를 오른쪽으로 옮기는 것뿐이고, 너무 크면 right를 왼쪽으로 옮깁니다.

def pair_with_sum(nums, target):
    left, right = 0, len(nums) - 1
    while left < right:
        s = nums[left] + nums[right]
        if s == target:
            return left, right
        if s < target:
            left += 1
        else:
            right -= 1
    return None
print(pair_with_sum([1, 3, 4, 6, 8, 11], 10))   # (2, 3)
print(pair_with_sum([1, 3, 4, 6, 8, 11], 2))    # None

매 단계 포인터 하나가 안쪽으로 움직이므로 단계는 최대 n − 1번입니다. 시간은 O(n), 공간은 O(1)입니다. 같은 구조로 문자열이 팰린드롬인지 검사하거나 배열을 제자리에서 뒤집을 수 있고, 바깥 반복문 안에 넣으면 3Sum을 O(n³)이 아니라 O(n²)에 풀 수 있습니다.

빠른 포인터와 느린 포인터: 제자리 필터링

느린 포인터는 다음에 남길 요소가 들어갈 위치를 가리키고, 빠른 포인터는 모든 요소를 훑습니다. 이렇게 하면 추가 메모리 없이 정렬된 리스트에서 중복을 제거할 수 있습니다.

def dedupe_sorted(nums):
    """Remove duplicates in place; return the new length."""
    if not nums:
        return 0
    slow = 0
    for fast in range(1, len(nums)):
        if nums[fast] != nums[slow]:
            slow += 1
            nums[slow] = nums[fast]
    return slow + 1
a = [1, 1, 2, 3, 3, 3, 5]
k = dedupe_sorted(a)
print(k, a[:k])   # 4 [1, 2, 3, 5]

연결 리스트에서는 빠른 포인터가 단계마다 두 노드, 느린 포인터가 한 노드 움직입니다. 둘이 만나면 리스트에 사이클이 있는 것입니다(플로이드의 사이클 검출). 빠른 포인터가 끝에 닿았을 때 느린 포인터는 가운데에 있습니다.

슬라이딩 윈도우: 반복 없는 가장 긴 부분 문자열

슬라이딩 윈도우는 구간 s[left:right + 1]이 항상 유효하도록 유지합니다. right를 한 글자씩 앞으로 옮기다가 새 글자가 규칙을 깨면 윈도우가 다시 유효해질 때까지 left를 앞으로 옮깁니다. 진행하면서 가장 좋은 윈도우를 기록합니다.

def longest_unique(s):
    last_seen = {}          # char -> last index
    left = best = 0
    for right, ch in enumerate(s):
        if ch in last_seen and last_seen[ch] >= left:
            left = last_seen[ch] + 1   # jump past the repeat
        last_seen[ch] = right
        best = max(best, right - left + 1)
    return best
print(longest_unique("abcabcbb"))   # 3  ("abc")
print(longest_unique("pwwkew"))     # 3  ("wke")
print(longest_unique(""))           # 0

윈도우에는 두 종류가 있습니다. 크기가 k로 고정된 윈도우는 오른쪽으로 들어오는 요소를 더하고 왼쪽으로 나가는 요소를 빼며, 이동 평균을 계산할 때 쓰입니다. 크기가 가변인 윈도우는 위 예제처럼 조건을 맞추기 위해 커지고 줄어듭니다.

def min_len_subarray(nums, k):
    """Shortest subarray with sum >= k (non-negative nums)."""
    left = total = 0
    best = float("inf")
    for right, x in enumerate(nums):
        total += x
        while total >= k:
            best = min(best, right - left + 1)
            total -= nums[left]
            left += 1
    return 0 if best == float("inf") else best
print(min_len_subarray([2, 3, 1, 2, 4, 3], 7))   # 2  ([4, 3])

시간 복잡도와 공간 복잡도

while 반복문이 중첩되어 있는데도 슬라이딩 윈도우가 O(n)인 이유는 left와 right가 각각 전체에서 최대 n번만 앞으로 움직이기 때문입니다. 따라서 전체 작업은 최대 2n단계입니다.

흔한 실수

• 정렬되지 않은 데이터에 양 끝 포인터를 쓰는 경우입니다. left와 right 중 어느 쪽을 옮길지의 판단은 배열이 정렬되어 있을 때만 맞습니다.
• 음수가 있을 수 있는데 합 기반 슬라이딩 윈도우를 쓰는 경우입니다. 윈도우를 줄여도 합이 항상 줄어들지는 않습니다. 대신 누적 합과 해시 맵을 사용하세요.
• 윈도우 길이의 off-by-one 오류입니다. left..right를 양 끝 포함으로 보면 요소는 right - left + 1개입니다.
• left < right에서 멈추는 것을 잊는 경우입니다. 그러면 요소 하나가 자기 자신과 짝이 됩니다.
• left를 뒤로 옮기는 경우입니다. 부분 문자열 예제에서는 last_seen[ch] >= left 검사로 옛 위치로 되돌아가는 것을 막습니다.

사용 시점과 대표적인 면접 문제

입력이 정렬되어 있고(또는 저렴하게 정렬할 수 있고) 쌍을 찾거나 배열을 제자리에서 수정해야 한다면 투 포인터를 쓰세요. 문제에 연속된 부분 배열이나 부분 문자열이라고 되어 있고, 윈도우가 커지면서 예측 가능하게 변하는 조건에서 가장 길거나 짧은 것, 최댓값, 개수를 묻는다면 슬라이딩 윈도우를 쓰세요. 데이터가 정렬되어 있지 않고 쌍이 필요하다면 보통 해시 셋이 더 간단하고 마찬가지로 O(n)입니다.

• Two Sum II(정렬된 입력), 3Sum, Container With Most Water, Trapping Rain Water.
• Valid Palindrome, Reverse String, Move Zeroes, Remove Duplicates from Sorted Array.
• Longest Substring Without Repeating Characters, Minimum Window Substring, Sliding Window Maximum(덱 사용).
• Linked List Cycle, Middle of the Linked List.

면접 밖에서도 같은 발상이 정렬된 파일 병합, 확인 응답을 받지 못한 패킷의 윈도우를 추적하는 네트워크 프로토콜(TCP 슬라이딩 윈도우), 최근 N초 동안의 이벤트를 세는 속도 제한기, 시계열의 이동 평균에서 쓰입니다.