투포인터 - 바킹독 유튜브를 보고

개념

알고리즘 자체에서 크게 설명할 건 없고 문제를 해결하는 예시를 몇개 보면 쓰임새를 파악하기 좋다.

투포인터는 배열에서 원래 이중 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])

이렇게 반복문을 순회하다보면 하나의 규칙을 발견할 수 있다.

1. i가 증가함에 따라 a[j] - a[i]가 m이상이 되는 최초의 지점 j 또한 증가한다. (a가 정렬되어 있기 때문에 자연스럽게 유추할 수 있다.)
2. 각 i에 대해 a[j] - a[i]가 m이상이 되는 최초의 지점 j를 찾은 이후에는 a[j+1] a[j+2]를 찾을 필요가 없다. (m이상이 되는 차이의 최소를 구해야하므로)

투포인터 버전

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)

정리

연습문제들은 모두 인덱스가 왼쪽에서 오른쪽으로 움직였는데 하나는 왼쪽에서 오른쪽이고 다른 하나는 오른쪽에서 왼쪽으로 혹은 다른 배열에서 각기 포인터가 움직이는 경우도 있다.