투 포인터: 반복문 둘 대신 한 패스

"무차별이 '모든 쌍 비교' 면, 멈춰. 종종 배열을 영리하게 걷는 두 인덱스가, 중첩 반복문이 n² 에 하는 걸 한 패스에 해."

핵심 동작

투 포인터 기법은 두 인덱스를 배열에서 움직이며, 그 관계를 이용해 중첩 반복문이 반복할 일을 건너뛰어. 주 맛이 둘이야:

수렴 — 양 끝에 포인터 하나씩, 가운데로 걸어. 회문, 정렬된 배열의 쌍-합, 뒤집기, "물 가장 많이 가두기" 에 좋아.
같은 방향 (빠른/느린) — 둘 다 앞에서 시작, 하나가 앞서 달려. 제자리 중복 제거, 분할, 뭔가 따라 미끄러뜨리기에 좋아.

보상은 거의 늘 같아: O(n²) 무차별이 O(n) 시간, O(1) 공간으로 무너져, 각 포인터가 배열을 많아야 한 번 건너고 추가 구조를 안 들거든.

왜 통하나: 정렬된 순서가 방향을 정하게 해줘

"target 으로 합쳐지는 두 수 찾기" 를 정렬된 배열에서 해봐. 무차별은 모든 쌍 확인: O(n²). 양 끝 두 포인터로 그 합을 봐. 너무 작아? 키울 유일한 길은 왼쪽 포인터를 오른쪽으로 (더 큰 값 쪽) 옮기는 거야. 너무 커? 오른쪽 포인터를 왼쪽으로. 각 이동이 절대 확인 안 해도 될 쌍 한 무더기를 배제해. 한 패스, O(n). 정렬된 순서가 어느 포인터를 옮길지 알려줘 — 그게 숨은 엔진이야.

투 포인터는 '모든 쌍 확인' (O(n²)) 을 '두 인덱스 한 번 걷기' (O(n), O(1) 공간) 로 바꿔. 포인터 사이 관계 — 그리고 종종 정렬된 배열 — 이 어느 걸 전진시킬지 알려줘.

신호

이 기법이 언제 머릿속에 번쩍여야 해? 한 배열 위 중첩 반복문을 쓰려는 자신을 잡을 때, 특히 "쌍", "회문", "뒤집기", "양 끝", "제자리", "정렬됨" 같은 단어와 함께. 그게 물을 신호야: 두 인덱스랑 그것들이 어떻게 움직일지에 대한 규칙이 이걸 한 쓸기로 할 수 있을까? 가까운 사촌 — 슬라이딩 윈도우 — 을 바로 다음 lesson 에서 만나.

피파의 고백

내 첫 "target 으로 합쳐지는 두 수" 는 교과서 이중 반복문이었어 — 깔끔하고, 정답이고, 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