투 포인터는 한 가지 알고리즘을 말하는 것이라기보다,

포인터 i, j 두 개를 사용해서, 브루트 포스로는 O(N^2)이 걸리는 문제를,

O(N)으로 만드는 그리디 알고리즘의 모음라고 보는 게 좋다.

 

따라서, 투 포인터는 예제를 통해서 익히는 게 좋고,

투 포인터를 통해서 그리디가 가능한 문제는 부분합,

배열의 두 값의 합이나 차가 특정 수가 되는지(A [i]+A [j]=S) 찾는 문제 등이 있다.

위 링크들은 백준 문제로 연결된다.

 

구현 난이도는, 아무래도 그리디다 보니 조건절이 브루트 포스보다는 더 들어가야 해서,

조금 더 어렵고 주의를 요한다고 볼 수 있다.

 

 

반응형

+ Recent posts