알고리즘 자체에서 크게 설명할 건 없고 문제를 해결하는 예시를 몇개 보면 쓰임새를 파악하기 좋다.
투포인터는 배열에서 원래 이중 for문으로 O(N**2)에 처리되는 작업을 2개 포인터의 움직임으로 O(N)에 해결하는 알고리즘
이분탐색 문제를 투포인터 문제로 해결할 수 있는 경우가 많다. 반대의 경우도 생각해보면 좋을 듯!
가장 많이 실수 하는 것이 인덱스 하나 차이로 하는 실수이다.
ex ) 0-인덱스 기준으로 길이가 N인 배열 a의 a[N]은 참조하면 안되는 값이다. 반복문 탈출 조건을 잘못줘서 end값이 이미 N이 되었는데도 값을 참조하려고 해서 문제가 생길 수 있다.
boj-2230
시간초과가 나겠지만 아래와 같이 이중 for문으로 간단하게 답을 구할 수 있다.
a.sort()
for i in range(N):
for j in range(i, N):
if (a[j] - a[i] >= M):
answer = min(answer, a[j] - a[i])
이렇게 반복문을 순회하다보면 하나의 규칙을 발견할 수 있다.
투포인터 버전
import sys
N, M = map(int, input().split())
numbers = sorted([int(input()) for _ in range(N)])
answer = sys.maxsize
right = 0
for left in range(N):
while right < N and numbers[right] - numbers[left] < M:
right +=1
if right == N:
break
answer = min(answer, numbers[right] - numbers[left])
print(answer)
이분탐색 버전
import sys
def lower_bound(nums, target):
left, right = 0, len(nums)
while left < right:
mid = left + (right - left) // 2
if nums[mid] < target:
left = mid + 1
else:
right = mid
return right
N, M = map(int, input().split())
numbers = sorted([int(input()) for _ in range(N)])
answer = sys.maxsize
for number in numbers:
idx = lower_bound(numbers, number+M)
if idx != N:
answer = min(answer , abs(numbers[idx] - number))
print(answer)
boj-1806
import sys
N, S = map(int, input().split())
numbers = list(map(int, input().split()))
answer = sys.maxsize
right = 0
total = numbers[0]
for left in range(N):
while right < N and total < S:
right+=1
if right != N:
total += numbers[right]
if right == N: break
answer = min(answer, right - left+1)
total -= numbers[left]
if answer == sys.maxsize:
print(0)
else: print(answer)
연습문제들은 모두 인덱스가 왼쪽에서 오른쪽으로 움직였는데 하나는 왼쪽에서 오른쪽이고 다른 하나는 오른쪽에서 왼쪽으로 혹은 다른 배열에서 각기 포인터가 움직이는 경우도 있다.