[도구정리] 투포인터

투포인터란? 인덱스를 두 개로 두어 O(N^2)이 될 수 있는 탐색을 O(N)으로 만들어주는 것이다.

예를 들어보자. 연속된 숫자가 존재하는 배열(1,2,3,4,5,1,2,3,4,5,) 같이 존재한다. 이때 연속된 수열의 합을 구하여 원하는 숫자가 나올 수 있는 경우의 수를 구하는 문제이다.

투포인터를 쓰지 않는다면 원하는 숙자가 15일 때, 1 + 2 + 3 + 4 + 5를 하고 정답!을 찾은 다음 2, 2 + 3, 2 + 3 + 4 이런 식으로 또 찾아야 한다는 문제가 생긴다는 것이다. 즉, 인덱스의 시작 지점과 끝지점 같이 저장해 두면 편한 정보를 두 가지로 나누어 저장함으로써 답을 효율적으로 찾는 알고리즘이다.

 

코드를 함께 보자.

int start = 0, end = 0, sum = 0, answer = 0;

while(true){
            if(sum >= n){
                sum -= primeList.get(start++);
            }else if(end == primeList.size()){
                break;
            }else{
                sum += primeList.get(end++);
            }
            if(sum == n){
                answer++;
            }
        }

 

배열로 쓰기도 하지만 위의 코드는 백준 1644번 정답 제출을 위해 리스트로 작성하였다.

투포인터 알고리즘이라는 것만 눈치채면 어려운 문제는 아니었지만 코드에 더욱 집중해보자.

 

먼저 시작 인덱스, 끝 인덱스, 총 합, 정답 개수를 들고 간다.

순서는 다음과 같다.

1. 시작:0, 끝:0으로 된 인덱스를 들고 탐색을 시작한다.

2. 만약 sum이 내가 구하고자 하는 값(n) 보다 크거나 같다면 제일 앞의 인덱스를 빼준다. -> 이후 시작 지점의 인덱스를 한 칸 앞으로 미룬다.(++연산이기 때문에 먼저 get 하고 ++한다는 것에 주의하자.)

2 - 1. else - if 부분은 마지막에 설명하겠다.

2 - 2. 만약 sum이 내가 구하고자 하는 값보다 작다면 제일 끝의 인덱스를 한 칸 더해준다. -> 이후 끝 지점의 인덱스를 한 칸 앞으로 미룬다.(마찬가지로 후술연산자다.)

3. 만약 내가 구하고자 하는 값이 같다면 정답을 하나 ++ 한다.

 

여기서 좀 헷갈릴 수도 있는 건 마지막에 정답만 ++ 했다는 것이다! 하지만 이미 인덱스에 대한 연산은 후술연산으로 처리가 되어있기 때문에 그런 것이다. 

 

마지막으로 다소 의아할 수도 있는 else - if 인 2-1의 위치에 대해 고민해 보자.

만약 아래와 같은 배열이 주어지고, 연속된 인덱스의 합으로 5를 만들라는 질문이 들어온다면?

1 2 3 4 2 5 3 1 1 2

위의 코드 순서를 따라가 보면 다음과 같다.

1. sum : 0 >= 5를 만족시키지 못한다. 즉, else - if 분기로 넘어간다.

2. end : 0!= 10(배열 크기) 이기 때문에 else까지 흘러간다.

3. sum에 1이라는 값을 더하고 end 인덱스가 1이 된다.(인덱스 0에 대해 값을 더한 후 인덱스가 1이 되었음을 인식하자.)

4. sum : 1!= 5이기 때문에 다시 while문으로 돌아간다.

위의 과정을 반복하다 보면 후반 부에 3 1 1 2라는 수열로 들어오게 된다.

 

이때를 잘 보자. 3 1 1은 내가 원하는 값인 5를 만족시키므로 answer++를 해줄 것이다.

이 때 sum은 1이 모자란 상태에서 +1된 상태로 end 인덱스가 2(인덱스 포인트 9)를 가리키게 되었을 것이다.

즉, 저 상태에서의 sum = 5, end = 9, start = 6  -> 1번 포인트

그럼 다음 분기에서는? sum : 5 >= 5를 만족시켰고 3이라는 값을 뺀 뒤 start 인덱스가 +1 이 될 것이다.

 즉, 저 상태에서의 sum = 2, end = 9, start = 7 이 되었다는 소리이다! -> 2번 포인트

그럼 나머지 분기에 걸리지 않고 다음 while반복문 턴으로 돌아가게 된다.(if 문에 걸렸으므로 당연히 end = 9라고 else - if에 또 걸리거나 하지는 않는다.)

이때, sum = 2로 if 문에 걸리지 않고 else - if 문에 걸리게 되어 break가 되고 코드가 마무리된다.

 

이게 무슨 소리냐?????

만약 끝 인덱스가 2라는 작은 값이 아니고 6이라고 쳐보자.

즉, 저 상태에서의 sum = 5, end = 9, start = 6  -> 1번 포인트

이 것이 아닌 sum = 9, end = 9, start = 6이 되었다. 

그다음 분기에서는  즉, 저 상태에서의 sum = 2, end = 9, start = 7 이 되었다는 소리이다! -> 2번 포인트가 아닌 sum = 6, end =9, start = 7이 되었다!

즉 , 아직 if분기에 걸리는 것이 우선이라는 소리이다. 그렇다면?  즉, 저 상태에서의 sum = 5, end = 9, start = 8가 되고 나서야 다음 반복문에서의 while문을 탈출할 수 있게 된다는 것이다.

 

코드가 조금 복잡할 수 있거나 이해가 잘 되지 않는 경우 직접 그림을 그려보거나 https://www.acmicpc.net/problem/2003 문제로 가볍게 익혀보기 바란다.