투포인터

급 문제 풀다가 투포인터가 예전에도 헷갈렸던 기억에

구글링 해가면서 기억을 더듬어봤는데 전혀 기억이 안나..!

이래서 무슨 망각 곡선 이런게 있는거군. 정말 살에 와닿는 그래프다.

왜 구글링 페이지들이 다 초면인가 하니,

예전엔 파이썬 알고리즘 책으로 공부했었어서 더 생경하게 느껴지는지도.

 

투포인터를 치면 블로그에서는 보통 배열 내 요소들의 합에 대한 것을 예시로 들어서

그 예에만 한정된 문제인 줄 알았는데, 알고보니 투포인터는 그런 용도로만 사용되는 기법은 아니었다.

 

예를들어, 배열 내 요소들끼리 비교를 하려면 순차적으로 모든 요소들을 하나씩 비교해야 한다.

어쩌면 for문을 이중으로 돌려서 O(n^2)의 시간복잡도를 만들면서 문제를 풀이 할 수도 있다.

 

반면 투포인터를 이용하면 O(n)의 시간복잡도를 갖고 문제를 풀 수 있다.

문제에서 원하는 방향에 따라 포인터의 위치를 다르게 두고,

각각의 포인터가 가르키는 값끼리 비교하거나, 순서를 바꾸는 방식이다.

 

이렇게 되면 굳이 이중 반복문을 돌지 않고도 O(n)의 시간 복잡도 내에서

배열 내의 두 요소를 비교할 수 있게되므로 좀 더 효율적인 방법이 되겠다.

 

자주 나오는 유형은 

- 배열의 순서 바꾸기

- 글자의 순서 뒤집기

- 배열 내 요소들의 합이 N이 되는 경우의 수, 또는 인덱스