[JS] 투포인터 (Two Pointer)

✨ 투포인터 알고리즘

• 일차원 배열에 인덱스를 가리키는 두 개의 포인터(변수)를 두고 조작하는 알고리즘 (이 인덱스를 가리키는 변수를 포인터라고 부름)
• 보통 연속적인 구간에 대한 계산을 할 때 많이 사용한다.

 

예시) 다음 배열에서 합이 10인 수열의 수는?

처음에는 포인터 두개가 전부 첫 인덱스를 가리킨다. 이때는 아직 구간에 대한 합(partialSum)이 7이고 구간 합이 10인 경우는 하나도 찾지 못한 상태이다.	count = 0 partialSum = 7 p1 = 0 p2 = 0
아직 구간 합이 10을 넘지 못했기 때문에 두번째 포인터를 증가시키고 해당 index에 대한 값을 구간 합 변수에 더해준다. 따라서 partialSum 변수는 8이 된다.	count = 0 partialSum = 8 p1 = 0 p2 = 1
아직 구간 합이 10을 넘지 않아서 두번째 포인터를 증가시킨다. 이제 구간 합이 11이 된다.	count = 0 partialSum = 11 p1 = 0 p2 = 2
구간 합이 10을 넘었기 때문에 이번엔 반대로 첫번째 포인터를 증가시킨다. 증가시키면서 기존 값을 partialSum에서 뺴준다.	count = 0 partialSum = 4 p1 = 1 p2 = 2
이번엔 두번째 포인터를 증가시킨다. 그리고 구간 합도 더해준다.	count = 0 partialSum = 9 p1 = 1 p2 = 3
마찬가지로 또 두번째 포인터를 증가시킨다. 이번엔 구간 합이 10이 되었기 때문에 count 변수를 증가시켜준다.	count = 1 partialSum = 10 p1 = 1 p2 = 4
다음 수가 0일 수도 있기때문에 이번에도 두번째 포인터를 증가시켜준다.	count = 1 partialSum = 14 p1 = 1 p2 = 5
구간 합이 10을 넘겼기때문에 첫번째 포인터를 증가시켜준다.	count = 1 partialSum = 13 p1 = 2 p2 = 5
또 다시 첫번째 포인터를 증가시킨다. 구간 합이 10이 되었기 때문에 count를 증가시킨다.	count = 2 partialSum = 10 p1 = 3 p2 = 5
두번째 포인터를 증가시킨다.	count = 2 partialSum = 12 p1 = 3 p2 = 6
첫번째 포인터를 증가시킨다.	count = 2 partialSum = 7 p1 = 4 p2 = 6
두번째 포인터를 증가시킨다.	count = 2 partialSum = 9 p1 = 4 p2 = 7
또 두번째 포인터를 증가시킨다.	count = 2 partialSum = 17 p1 = 4 p2 = 8
두번째 포인터가 끝에 도달했기 때문에 이 후로 첫번째 포인터만 계속 증가시켜준다.	count = 2 partialSum = 16 p1 = 5 p2 = 8
첫번째 포인터를 증가시켜준다.	count = 2 partialSum = 12 p1 = 6 p2 = 8
첫번째 포인터를 증가시켜준다. 구간 합이 10이 되었기때문에 count를 증가시켜준다.	count = 3 partialSum = 10 p1 = 7 p2 = 8
결국 모든 포인터가 끝에 도달했다. 투포인터 알고리즘 종료!	count = 3 partialSum = 8 p1 = 8 p2 = 8

 

 

정리

• 어려운 개념은 아니지만 모를 때는 당하는 문제 유형
• 백트래킹을 사용하거나 완전 탐색으로 풀려다 시간 제한에 걸리는 경우가 많다.

 

---

✨ 관련 문제 풀이

https://lazyhysong.tistory.com/entry/JS-Two-Pointer-%EB%B3%B4%EC%84%9D-%EC%87%BC%ED%95%91

[JS] Two Pointer - 보석 쇼핑