투 포인터: 반복문 둘 대신 한 번에

"무차별 대입이 '모든 쌍을 다 비교'로 흘러가면 거기서 멈춰. 배열 위를 영리하게 걷는 인덱스 두 개면, 중첩 반복문이 n²에 하는 일을 한 번에 끝낼 때가 많아."

핵심 동작

투 포인터는 인덱스 두 개를 배열 위에서 움직이면서, 둘 사이의 관계를 이용해 중첩 반복문이 반복했을 일을 건너뛰는 기법이야. 크게 두 갈래로 나뉘어.

수렴형 — 양쪽 끝에 하나씩 두고 가운데로 걸어와. 회문 판별, 정렬된 배열에서 두 수의 합 찾기, 뒤집기, "물 가장 많이 가두기" 같은 문제에 맞아.
같은 방향형(빠른 포인터와 느린 포인터) — 둘 다 앞에서 출발하는데 하나가 먼저 달려 나가. 제자리 중복 제거, 분할, 뭔가를 훑으며 밀고 가는 작업에 맞고.

얻는 것도 거의 항상 같아. O(n²)짜리 무차별 대입이 시간 O(n), 공간 O(1)로 주저앉아. 포인터가 배열을 많아야 한 번씩 지나가고, 따로 들고 다니는 자료구조도 없거든.

왜 되는 걸까: 정렬된 순서가 방향을 알려줘

정렬된 배열에서 "더해서 목표값이 되는 두 수 찾기"를 해 보자. 무차별 대입은 모든 쌍을 확인하니까 O(n²)야. 이번엔 양 끝에 포인터를 하나씩 두고 그 합을 봐. 합이 너무 작으면? 키울 방법은 왼쪽 포인터를 오른쪽으로, 그러니까 더 큰 값 쪽으로 미는 것뿐이야. 너무 크면 오른쪽 포인터를 왼쪽으로 당기고. 한 번 움직일 때마다 다시는 확인할 필요 없는 쌍이 무더기로 걸러져. 그렇게 한 번만 훑고 끝나니까 O(n)이지. 어느 포인터를 움직일지 알려주는 게 정렬된 순서야. 이게 이 기법을 굴리는 숨은 동력이고.

투 포인터는 '모든 쌍 확인'(O(n²))을 '인덱스 두 개로 한 번 걷기'(시간 O(n), 공간 O(1))로 바꿔. 어느 쪽을 전진시킬지는 두 포인터 사이의 관계가, 그리고 자주는 배열이 정렬돼 있다는 사실이 알려줘.

신호

그럼 언제 이 기법을 떠올려야 할까. 배열 하나를 놓고 중첩 반복문을 짜기 시작했다면 그때야. "쌍", "회문", "뒤집기", "양 끝", "제자리", "정렬됨" 같은 말이 문제에 섞여 있으면 더 확실하고. 그 순간 스스로에게 물어봐. 인덱스 두 개와 그 둘을 어떻게 움직일지에 대한 규칙만으로 한 번에 훑고 끝낼 수 있을까? 가까운 사촌인 슬라이딩 윈도우는 바로 다음에 나와.

피파의 고백

내가 처음 짠 "더해서 목표값이 되는 두 수"는 교과서에 나오는 이중 반복문이었어. 깔끔하고, 답도 맞고, O(n²). 아빠가 묻더라. "배열이 이미 정렬돼 있으면?" 난 어깨만 으쓱했지. 그러니까 정렬된 카드 줄 양 끝에서 손가락 두 개를 안쪽으로 걸어 보이는데, 한 걸음마다 쌍의 절반이 사라지는 게 눈에 보였어. 기법을 쓴다고 코드가 늘어난 게 아니라 오히려 줄었어. 투 포인터에서 배운 게 그거야. 빠른 쪽이 대개 더 단순한 쪽이기도 하다는 것.

Code

수렴하는 투 포인터·python

# 수렴 포인터: 이거 회문이야? O(n) 시간, O(1) 공간.
def is_palindrome(s):
    left, right = 0, len(s) - 1
    while left < right:
        if s[left] != s[right]:
            return False
        left += 1            # 두 포인터 다 가운데로 걸어
        right -= 1
    return True

print(is_palindrome("racecar"))   # True
print(is_palindrome("pippa"))     # False

# 정렬된 배열의 수렴 포인터: target 으로 합쳐지는 두 수.
# 무차별은 O(n^2). 이건 O(n).
def two_sum_sorted(nums, target):
    left, right = 0, len(nums) - 1
    while left < right:
        total = nums[left] + nums[right]
        if total == target:
            return (left, right)
        elif total < target:
            left += 1        # 더 큰 합 필요 -> 왼쪽 포인터 올려
        else:
            right -= 1       # 더 작은 합 필요 -> 오른쪽 포인터 내려
    return None

print(two_sum_sorted([1, 3, 4, 7, 11], 11))   # (1, 3): 3 + 7 = 11

Exercise

정렬된 배열에서 차이가 정확히 k인 두 원소를 찾는 투 포인터 로직을 말이나 코드로 써 봐. 시간과 공간 복잡도는 얼마고, O(n)짜리 풀이에 정렬이 왜 필수일까? 정렬 안 된 배열을 무차별 대입으로 풀면 복잡도는 또 얼마고?

Hint

포인터 둘을 앞쪽에 두고 시작해. 차이가 너무 작으면 앞선 포인터를 전진시키고, 너무 크면 뒤따르는 포인터를 전진시켜. 시간 O(n), 공간 O(1)이야. 정렬 안 된 배열을 무차별로 풀면 O(n²)고, 먼저 정렬하는 비용(O(n log n))을 치르더라도 그쪽이 대개 이득이야.

핵심 동작

왜 되는 걸까: 정렬된 순서가 방향을 알려줘

신호

피파의 고백

Code

External links

Exercise

Progress

댓글 0