본문 바로가기
알고리즘 이론

투포인터 (Two pointer)

by 햄과함께 2021. 9. 12.
반응형

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

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 태그 에서 해당 알고리즘을 사용하는 다양한 문제에 대한 풀이가 있으니 참고바랍니다.

반응형

'알고리즘 이론' 카테고리의 다른 글

Python 문법 정리  (0) 2021.09.25
투포인터 (Two pointer)  (0) 2021.09.12
유니온 파인드(Union-Find)  (5) 2021.06.26
플로이드 워셜 알고리즘 (Floyd warshall)  (0) 2021.06.13
트리의 지름  (0) 2021.02.21
[C++/STL] stack을 vector로 변환하기  (0) 2021.01.21

댓글0