[DS&AL] Two Pointer
Two Pointer
Two Pointer (투 포인터) 알고리즘은 2개의 인덱스를 이용해서 배열이나 문자열을 효율적으로 탐색하는 기법을 말합니다. 보통 완전탐색으로 진행할 때, $O(N^2)$의 복잡도가 소요되는 문제를 $O(N)$이나 $O(log N)$으로 줄일 때 많이 사용합니다.
배열: [1, 2, 3, 4, 5]
↑ ↑
left right
투 포인터는 다음과 같이 2개의 포인터를 특정 조건에 따라 이동시키면서 원하는 답을 찾아가는 방식으로 문제가 구성됩니다.
문제 유형
크게 투 포인터의 문제 유형은 크게 다음과 같습니다.
양 끝에서 좁혀오는 유형
해당 문제는 정렬된 배열의 양 끝에 포인터를 두고, 조건에 따라 한 쪽을 이동하는 방식입니다.
[1, 2, 3, 4, 7, 9]
↑ ↑
left right
다음 포인터로 시작 지점을 설정하고, 합이 target보다 작으면 left + 1, 크면 right - 1과 같이 움직입니다.
같은 방향으로 이동하는 유형
left, right가 둘 다 왼쪽에서 시작해서 오른쪽으로 이동하는 형태입니다.
[1, 2, 3, 4, 5, 6]
↑
L
↑
R
다음과 같이, 연속 부분 배열이나 부분합 문제에 주로 사용되며, 연속된 수의 합이 M이 되는 구간을 찾는 문제라면, 합이 M보다 작은 경우, right 증가, 합이 M보다 큰 경우, left 증가와 같은 방식을 사용합니다.
Sliding Window
left ~ right 사이를 하나의 window로 관리하는 방법입니다.
[1, 2, 3, 4, 5, 6]
[---------]
L R
여기서 나올 수 있는 대표 문제는
- 길이가 K인 연속 부분 배열 최대 합
- 중복이 없는 가장 긴 문자열
- 특정 조건을 만족하는 가장 짧은 부분 배열
- 최대/최소 길이 구간 과 같은 문제가 출제될 수 있습니다.
이는 조건을 만족할 때까지 right를 늘리고, 조건을 만족하면 left를 줄이는 방식으로 최적의 구간을 찾아가면 됩니다.
두 배열을 동시에 탐색하는 경우
각 배열에 하나의 포인터를 두는 방법입니다.
A = [1, 3, 5, 7]
↑
i
B = [2, 3, 6, 8]
↑
j
여기서 나올 수 있는 대표 문제는
- 정렬된 두 배열 합치기
- 두 배열의 공통 원소 찾기
- 두 배열에서 차이가 가장 작은 두 수 찾기
- 교집합 구하기 과 같은 문제가 출제될 수 있습니다.
이 경우 코드를 다음과 같이 구현할 수 있는데,
if A[i] < B[j]:
i += 1
elif A[i] > B[j]:
j += 1
else:
# 공통 원소
i += 1
j += 1
다음과 같이 쉽게 구현할 수 있습니다.
Fast & Slow
두 포인터가 서로 다른 속도로 움직이는 유형입니다. 이는 주로 Linked List에서 많이 등장합니다.
여기서 나올 수 있는 대표 문제는
- Linked List Cycle Detection
- 연결 리스트의 중간 노드 찾기
- 사이클 시작점 찾기 과 같은 문제가 출제될 수 있습니다.
Two Pointer 코드 구현
Two Point의 대표 문제인 정렬된 배열에서 두 수의 합을 찾는 투 포인터 문제만 가져오면 코드는 다음과 같이 구현할 수 있습니다.
arr = [1, 2, 3, 4, 7, 9]
target = 10
left = 0
right = len(arr) - 1
while left < right:
current_sum = arr[left] + arr[right]
if current_sum == target:
print(arr[left], arr[right])
break
elif current_sum < target:
left += 1
else:
right -= 1
이 과정에서, 합이 작으면 왼쪽을 더 크게, 합이 너무 크다면 오른쪽을 줄이는 방향으로 범위를 이동합니다. 이는 배열이 정렬되어 있다는 가정 하에 진행되기 때문에, 이러한 방법이 가능합니다.
투 포인터의 가장 기본적인 형태는 left, right를 사용하며, 조건에 따라 하나 혹은 둘을 이동하는 방식으로 이해하면 편리합니다.
Leave a comment