투 포인터

 

투 포인터 

• 배열에서 이중 for 문으로 O(N^2) 에 처리되는 작업을 2개 포인터의 움직임으로 O(N) 으로 해결하는 알고리즘
• 리스트에 순차적으로 접근해야 할 때 2개 점의 위치를 기록하며 처리
• 이 포인터는 c의 포인터가 아닌 가리키는 역할
• 머지소트에서 정렬되어 있는 두 리스트의 병합의 기초가 되기도 함. 정렬된 2개 리스트를 포인터를 이용해서 하나의 정렬된 리스트 완성
• 투 포인터는 블로그 설명들을 보면 구현이 조금씩 다양한 것을 알 수 있는데, 이는 포인터와 구간에 대한 문제정의를 맞게 했으면 구현을 어떻게 했던지 간에 풀 수 있는 것을 알 수 있다. 

 

 

초기 단계 

• 2개 포인터는 리스트에서 시작 s, 끝 e 를 의미
• s와 e는 첫 번째 원소를 가리킴 
• 초기에 s와 e가 동일 원소를 가리키기 때문에 문제에 따라 중복처리
• e 인덱스는 항상 s 인덱스 이상임을 항상 유지하도록 s~e 구간 문제 정의 

 

중간 단계

• 문제에서 해결하고자 하는 방법에 따라 s 또는 e 이동
• 보통 s인덱스부터 e인덱스 사이 구간에 대한 문제를 처리. 애매한 표현같겠지만 문제가 다양하게 나올 수 있어 그때그때 사이 구간을 어떻게 정의하고 풀지 고민해야 함.
• 카카오 문제에서 다른 알고리즘과 응용되어 제출된 경우도 있음 
• 예를들어 s와 e 사이 구간 합이 10 이상이 되어야 하는 경우를 구한다면, 구간합이 10보다 작으면 e 증가. 구간합이 10보다 크다면 경우의 수 +1 그리고 s 증가 

 

마지막 단계 

• e 인덱스가 범위를 벗어나면 종료
• s 인덱스는 초기 단계에서 e 인덱스 이하임을 유지하기로 정의했기 때문에 e 인덱스 기준으로 종료
• 구현방법에 따라 s인덱스가 범위를 벗어나면 종료로 처리할 수 있음 

 

 

추가 

• 이분탐색으로 풀리는 문제 중 투 포인터로 풀리는 문제가 많다.
• 반대로 투 포인터로 풀리는 문제가 이분탐색으로 풀리는 문제도 많다. 

 

참고

https://blog.encrypted.gg/1004

https://butter-shower.tistory.com/226