투 포인터
두 개의 포인터를 사용하여 문자열이나 정렬 된 배열에서 원하는 값을 찾거나 구간 합을 구할 때 사용하는 알고리즘입니다.
병합정렬(merge sort)의 counquer 영역(인접한 부분배열끼리 정렬하여 합침) 기초가 되는 알고리즘입니다.
리스트에 순차적으로 접근해야 할 때, 두 개의 점의 위치를 기록하면서 처리합니다.
슬라이딩 윈도우와 유사하나, 고정 된 구간이 아닌 가변적인 구간을 탐색한다는 차이가 있습니다.
c.f> 슬라이딩 윈도우?
투 포인터처럼 구간을 흝으면서 지나간다는 공통점이 있으나, 슬라이딩 윈도우는 어느 순간에도 구간의 넓이가 동일하다는 차이가 있습니다.
투 포인터 적용하기
두 수의 합이 target을 만족하는 두 수를 찾는 문제가 주어졌을 때를 가정하여 투 포인터를 적용해 보겠습니다.
target = 6
우선 투 포인터를 적용하기 위해서 배열을 정렬해야 합니다.
array = [1, 3, 2, 6, 5, 4]
array.sort()시작점과 끝점의 인덱스를 지정하여 탐색을 수행합니다.
start, end = 0, len(array) - 1
target = 6아래와 같은 행위를 반복합니다.
1. 현재 두 수의 합을 구한다.
2. 두 수의 합이 타겟보다 더 큰 경우 끝 점을 당겨옵니다.
3. 두 수의 합이 타겟보다 더 작은 경우 시작 점을 당겨갑니다.
4. 두 수의 합이 타겟과 같은 경우 두 수를 출력 후, 시작점과 끝점을 이동합니다.
while start < end:
s = array[start] + array[end]
if s > target:
end -= 1
elif s < target:
start += 1
else:
print(start, end)
start += 1
end -= 1
다른 풀이 참고하기
투 포인터를 활용할 때, 시작점과 끝점을 중심으로 시작점을 당겨가거나, 끝점을 당겨오는 방식을 활용했습니다.
이 외에 시작점과 끝점을 첫 번째 원소의 인덱스를 가리키도록 하며, 값을 찾아나가는 방법도 있습니다.
array = [1, 2, 3, 4, 5, 6]
array.sort()
count = 0
target = 6
interval_sum = 0
end = 0
for start in range(len(array)):
while interval_sum < target and end < len(array):
interval_sum += array[end]
end += 1
if interval_sum == target:
count += 1
interval_sum -= array[start]
print(count)