투 포인터 (같은 방향)

Source: Dev.to

개요

Two Pointers (Same Direction) 패턴은 데이터 구조(보통 배열이나 문자열)를 두 개의 인덱스를 함께 앞으로 이동시켜 사용합니다.
반대 방향 포인터와 달리, 두 포인터는 모두 왼쪽 → 오른쪽으로만 이동하지만 다른 속도이거나 조건에 따라 이동합니다.
이 패턴은 선형 시간 최적화에서 매우 흔하게 사용됩니다.

두 포인터를 사용할 때 (같은 방향)

이 패턴을 사용할 경우:

• 요소를 순서대로 처리할 때.
• 두 위치를 비교하거나 연관시키고 싶을 때.
• 범위를 건너뛰거나, 필터링하거나, 추적해야 할 때.
• 중첩 루프(O(N²))를 피하고 싶을 때.

Typical Problem Statements

• 정렬된 배열에서 중복 제거
• 배열이 다른 배열의 부분 수열인지 확인
• 중복 문자 없이 가장 긴 부분 문자열
• 두 정렬된 배열 병합
• 조건에 따라 배열 분할
• 빠른 포인터와 느린 포인터 문제 (변형)

핵심 직관

• 리더 & 라이터
• 느림 & 빠름
• 앵커 & 탐험가

하나의 포인터는 참조 위치를 나타내고, 다른 하나는 앞을 스캔합니다.

일반 알고리즘 템플릿

slow = 0
for fast in range(0, n):
    if condition_satisfied:
        # perform operation using slow & fast
        slow += 1

• fast는 매 반복마다 이동합니다.
• slow는 필요할 때만 이동합니다.

주요 속성

• 시간 복잡도: O(N)
• 공간 복잡도: O(1)
• 정렬된 배열 또는 문자열에 가장 적합합니다.
• 불필요한 비교를 피합니다.

Example 1 – 정렬된 배열에서 중복 제거

문제
정렬된 배열이 주어지면, 제자리에서 중복을 제거하고 새로운 길이를 반환합니다.

아이디어
fast가 요소를 스캔하고, slow는 고유 값을 기록할 위치를 표시합니다.

코드

def remove_duplicates(nums):
    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

예제 2 – 부분 수열 확인

문제
s 문자열이 t 문자열의 부분 수열인지 확인합니다.

아이디어
slow는 s에서 현재 위치를 추적하고, fast는 t를 순회합니다.

코드

def is_subsequence(s, t):
    slow = 0
    for fast in range(len(t)):
        if slow < len(s) and s[slow] == t[fast]:
            slow += 1
    return slow == len(s)

Example 3 – 중복 문자 없는 가장 긴 부분 문자열

Problem
중복 문자가 없는 가장 긴 부분 문자열의 길이를 찾으세요.

Idea
left와 right가 모두 앞으로 이동하며, 집합(set)이 고유성을 유지합니다.

Code

def longest_unique_substring(s):
    seen = set()
    left = 0
    max_len = 0

    for right in range(len(s)):
        while s[right] in seen:
            seen.remove(s[left])
            left += 1
        seen.add(s[right])
        max_len = max(max_len, right - left + 1)

    return max_len

예제 4 – 두 정렬된 배열 병합

문제
두 개의 정렬된 배열을 하나의 정렬된 배열로 병합한다.

아이디어
첫 번째 배열을 위한 포인터 i, 두 번째 배열을 위한 포인터 j; 두 포인터 모두 앞으로 이동한다.

코드

def merge_sorted(a, b):
    i = j = 0
    result = []

    while i < len(a) and j < len(b):
        if a[i] <= b[j]:
            result.append(a[i])
            i += 1
        else:
            result.append(b[j])
            j += 1

    result.extend(a[i:])
    result.extend(b[j:])
    return result

Difference from Sliding Window

일반적인 실수

• 두 포인터를 무작정 이동시키기.
• 포인터 경계를 잊어버리기.
• 순서가 중요한데 정렬되지 않은 데이터에 사용하기.
• 반대 방향 포인터와 혼동하기.

이 패턴을 식별하는 방법

스스로에게 물어보세요:

• 한 번 앞으로 스캔해야 하나요?
• 한 포인터가 진행 상황을 추적하고 다른 포인터가 앞을 스캔할 수 있나요?
• 순서가 중요한가요?

중첩 루프를 이러한 스캔으로 대체할 수 있다면, 이 패턴이 적용됩니다.

정신 모델

• 하나의 포인터가 앞으로 이동합니다.
• 또 다른 포인터가 참조를 기록합니다.
• 두 포인터 모두 앞으로만 이동하고, 뒤로는 가지 않습니다.

요약

최종 생각

이 패턴은 무차별 탐색과 최적 솔루션 사이의 격차를 메워줍니다.
숙달하면, 중첩 루프를 깔끔한 선형 스캔으로 직관적으로 대체하게 될 것입니다.