[알고리즘] 투포인터 (Two Pointer)

 

투포인터의 개념

투포인터: 두개의 포인터를 사용해 문제를 푸는 알고리즘. 

1. start와 end (또는 front, back이나 left, right 등 이름은 다양하게 할 수 있다.) 두개의 포인터를 만든다. 

반드시 start <= end 여야 한다. 2. 초기 두개의 포인터는 0번 인덱스를 가리키도록 세팅한다. 3. 현재 s에서 e-1까지의 합을 sum이라 하였을때 sum이 구하려는 값(m)보다 크다면 s++4. sum이 m보다 작다면 e++ 5. sum과 m이 같다면 카운트 해준다. 6. s와 e의 위치를 바꿔가면서 모든 경우를 확인한다. 정리하자면 start 시작과 end 끝을 모두 증가시켜가며 부분 배열의 합이 m인 경우를 찾는 알고리즘이다. 예를 들어 배열의 크기 n=7, 구하려는 값 m=5 일때 투포인터를 움직여보자

투포인터 개념 설명 1

start와 end가 0번째 인덱스에서 시작한다.

0번 인덱스에서 0번 인덱스까지 더한 값은 1이므로 sum = 1이다. 

sum < m이므로 end를 추가해준다. 

투포인터 개념 설명2

0번 인덱스에서 1번 인덱스까지 더한 값(start에서 end까지 더한 값) 

sum = 3, sum < m이므로 end++ 해준다. 

투포인터 개념 설명3

이번엔 sum > m이므로 start ++ 해준다. 

투포인터 개념 설명4

sum과 m이 같으므로 카운트개수를 1 늘려준다. 

그리고 같을때에도 end++ 해준다. 

투포인터 개념 설명5

똑같이 sum >m이므로 start++

투포인터 개념 설명6

위 과정을 반복한다. 

투포인터 개념 설명7

sum이 m과 같으므로 카운트 개수 늘려준다. 

투포인터 개념 설명8

투포인터 개념 설명9

투포인터 개념 설명10

투포인터 개념 설명11

원래 sum>m인 경우 start를 늘려줘야하지만 현재 s와 e가 같다. 

s는 반드시 e보다 작거나 같아야 되므로 s만 늘려주는 것이 아닌 s와 e 둘다 +1 해준다. 

투포인터 개념 설명12

s와 e가 끝에 도달했기에 더이상 증가할 수 없는 상태가 되어 종료한다. 

여기서는 s와 e가 동시에 도달했지만 보통 e만 도달하여도 루프를 마무리하거나 s가 도달할때까지 비교하는 경우도 있다. 

 

---

시간복잡도

두개의 포인터가 각각 n번(배열의 크기만큼) 움직이므로 시간 복잡도는 O(n+n)이다. 

즉 O(n)으로 나타낼 수 있다. 

 

 

---

풀어보면 좋을 백준 문제

1. 2003번 수들의 합 2

2. 14246번 k보다 큰 구간

3. 2531번 회전초밥

4. 3151번 합이 0