투포인터 (Two pointer)

투포인터란 이름 그대로 두 개의 포인터를 사용하여 문제를 풀어나갑니다.

2개의 포인터로 배열이나 문자열을 탐색할 때 탐색 위치를 저장하고 있습니다.

 

말로 하는거보다는 예를 들어서 한 번 살펴봅시다.

수들의 합.

N개의 자연수 배열이 주어질 때, i~j 번째 수들의 합이 M이 되는 경우의 수를 구하는 문제입니다.

 

1

1

1

1

배열은 위와 같고, M = 2 라고 했을 때 투포인터로 정답을 구해봅시다.

두 개의 포인터를 두고 이들을 left, right라 합시다. left는 i, right는 j 번째 수의 위치를 가리킵니다.

left는 범위를 줄이고자 할 때 증가시키고, right는 범위를 증가시키고자 할 때 증가시킵니다.

시작 인덱스는 둘 다 0입니다.

left	right	부분 배열합
0	0	1
0	1	2
1	1	1
1	2	2
2	2	1
2	3	2
3	3	1
3	4	out of bounds -> 종료

 

배열의 원소들은 자연수이기 때문에 항상 0보다 큽니다.

left~right 부분 배열합이 M 보다 작은 경우, 부분 배열합이 커져야 하므로 부분 배열의 크기도 커져야합니다. 따라서 이 경우, right 인덱스를 하나 증가시킵니다.
left~right 부분 배열합이 M 보다 같거나 큰 경우, 부분 배열합이 작아져야 하므로 부분 배열 크기도 작아져야 합니다. 따라서 이 경우, left 인덱스를 하나 증가시킵니다.

---

비슷한 느낌으로 슬라이딩 윈도우(Sliding window)라는게 있습니다. 필자는 요 단어를 알고리즘에서 보다는 네트워크 과목에서 패킷을 처리하는 방법 관련 수업에서 먼저 들었었는데 기본 이론은 투포인터랑 같으나 왼쪽, 오른쪽 포인터의 차이가 항상 동일하다는 차이가 있습니다. 이 때, 오른쪽, 왼쪽 포인터의 차이를 윈도우 크기라 합니다.

 

개인적으로 좋아하는 알고리즘 중 하나입니다.

two-pointer 태그 에서 해당 알고리즘을 사용하는 다양한 문제에 대한 풀이가 있으니 참고바랍니다.