[바킹독의 실전 알고리즘] 0x14강 - 투 포인터

1. 알고리즘 설명

 

투포인터 알고리즘이란?

배열에서 원래 이중 for문으로 O(N^2)에 처리되는 작업을 2개 포인터의 움직임으로 O(N)으로 해결하는 알고리즘

보통 이중 for문을 돈다면 시간복잡도는 O(N^2)가 될 것임. 이 과정에서 i=0일때 계산하면서 얻은 정보는 i=1일때 사용이 되지 않음. 하지만 투 포인터를 활용한다면 i=0일때 계산하면서 얻은 정보를 i=1일 때 활용할 수 있음! 그리고 그 정보는 바로 포인터의 이동으로 나타남.

 

여기서 포인터라는 건 C에서 흔히 말하는 포인터는 아니고, 커서의 개념과 동일함!

 

투포인터 문제  ⇋ 이분 탐색 문제

투포인터 문제의 경우 이분 탐색으로 풀 수 있는 경우가 많음. 반대로 이분 탐색 문제 역시 투포인터 문제 유형으로 바꿔  풀 수 있는 경우가 많음. 최근 종종 나오는 문제 유형이므로 구현하는 방법을 알아두고 연습하는 게 좋음. 

 

2. 연습 문제 ① 수 고르기 문제

 

바킹독님 문풀

https://blog.encrypted.gg/1004

 

내가 정리한 문풀

https://shingy.tistory.com/31