[APS] 이론 : 투포인터

투포인터

투 포인터(two-pointer)란, 선형 자료구조(배열, 리스트 등)에서 위치(index)를 가리키는 변수(=포인터) 두 개를 사용하여 탐색 범위를 효율적으로 좁혀나가는 알고리즘 풀이 기법이다.

 

위와 같이 정렬되어있는 배열에서 두 수의 합이 6이 되는 쌍을 탐색하는 문제가 있다고 가정하자. 우리가 생각할 수 있는 가장 기본적인 아이디어는 이중 for문을 사용한 완전탐색(brute-force)으로, 이러한 경우 O(N^2) 의 시간복잡도 내에 문제를 해결할 수 있게 된다.

 

그러나 만약 배열의 길이가 너무 길다면 단순 완전탐색으로는 주어진 시간 내에 문제를 풀 수 없을 수도 있다. 따라서 시간을 조금 줄이기 위해, 조금 다른 방식으로 문제에 접근해보자. 숫자 쌍을 찾을 때, 한 숫자가 정해졌다면 특정 조건을 만족시키기 위한 다른 숫자는 유일하다. 예를 들어 2와 3이 더했을 때 5를 만족하는 숫자 쌍이라면, 2와 3 둘 중 하나만 바꿔서는 더 이상 더해서 5라는 조건을 만족시킬 수 없다. 2 쪽의 숫자가 커진다면, 3 쪽은 반드시 작아져야 한다.

 

투 포인터의 기본 아이디어도 이곳에서 출발한다. 한 숫자가 커지면 다른 숫자는 작아져야 하므로, 두 개의 포인터를 양쪽 배열 끝, 즉 가장 작은 숫자와 가장 큰 숫자에 둬보는 것이다. 이러한 경우 두 수의 합은 7이 되므로, 합이 6이 되려면 두 숫자 중 한 쪽은 반드시 작아져야 한다.

 

직관적으로 생각했을 때 (1이 주어진 가장 작은 숫자라 작아질 수도 없지만), 합을 줄이기 위해선 더 큰 수(6)쪽이 작아져야 하므로, 오른쪽 끝 포인터를 왼쪽으로 한칸 옮기는 것이다. 이제 두수의 합이 6인 쌍 (1,5)를 찾을 수 있을 것이다.

 

주의할 것은 포인터를 옮기는 것을 "합을 줄이거나 늘리기 위해서"라는 수학적 개념으로 생각해서는 안된다는 것이다.

포인터는 우리가 고려해야 할 범위 혹은 대상을 가리키는 개념적인 변수이다. 포인터의 움직임은 탐색 대상 혹은 범위를 줄여나가는 과정으로 이해해야 하며, 해당 포인터가 가리키는 대상은 이후 탐색 범위에서 제외된다. 쉽게 말해 (1,6)에서 (1,5)로 움직였다는 것은, 6은 고려할 필요가 없기 때문에 이후에 오른쪽으로 움직여 다시 6을 가르킬 필요가 없고, 이후 탐색 과정에 따라 왼쪽으로만 움직일 수 있는 것이다. 

 

물론 미묘한 차이긴 하지만, 위의 예시처럼 정확히 (1,5) 쌍을 찾았다면 이제 합을 늘리기 위해 왼쪽 포인터(s)를 움직여야 하는가? 아니면 합을 줄이기 위해 오른쪽 포인터(e)를 움직여야 하는가? 와 같은 경계조건 에 관한 질문이나,

"합을 늘리기 위해서"가 그 이유라면, 오른쪽 포인터를 다시 오른쪽으로 움직이는 것도 방법이 될 수 있을텐데 왜 항상 왼쪽으로만 움직여야 하는가? 와 같은 개념적인 질문의 경우 수학적 개념으로 포인터를 움직인다고 이해한다면 섣불리 대답할 수 없을 것이다. 

위에서 찾은 숫자쌍 (1,5)를 출력하거나 저장해 둔 뒤, 또 양쪽 포인터를 조절하면서 숫자를 찾다보면, 또다른 숫자 쌍 (2,4)를 찾을 수 있을 것이다. 

 

이렇게 문제를 풀게 되면, 두 포인터는 배열을 한 번만 순환하게 되어 결국 시간 복잡도는 O(N)으로 줄어들게 된다. 물론 예시처럼 배열이 정렬되어있지 않다면 정렬 알고리즘 만큼의 시간복잡도(보통 O(NlogN))이 추가되긴 하지만, N이 충분히 큰 대부분의 문제에서는 투 포인터 알고리즘이 완전탐색에 비해 훨씬 효율적이다.

 

즉, 투 포인터 알고리즘은 탐색의 시간 복잡도를 줄이기 위한 기법이다. 쉽게 설명하자면, "반복문 2번 쓸걸 1번으로 줄이는 데" 쓰이는 알고리즘 기법이라고 보면된다. 위의 예시를 Java 코드로 구현한다면 다음과 같다.

int[] arr = {1,2,3,4,5,6};

int s = 0;
int e = 5;

while(s<e){
    int sum = arr[s] + arr[e];
    if(sum >= 6){
    	if(sum == 6) System.out.println("("+arr[s]+","+arr[e]+")");
        e--;
    }
    else s++;
}

 

투 포인터에서 사용하는 두 개의 포인터는 정해진건 아니지만 보통 start, end의 앞글자를 따서 s,e 로 표기한다.

 

위의 예시 처럼 두 수의 합은, 한 수가 커지면 다른 수가 작아져야 한다는 이유로 양 쪽 끝에 포인터를 두고 시작한다.

그러나 두 수의 차라면 어떨까? 한 수가 커지면 다른 수 역시 커져야하기 때문에 포인터는 계속 같은 방향으로 움직여야 하므로, 양쪽 끝에 포인터를 두는 것은 무리가 있다. 또 다른 예시로, 구간(s이상 e미만)의 합이 5가 되는 경우 를 살펴보도록 하자

위와 같이 양의 정수로 이루어진 구간의 합은 "내부에 포함되는 숫자가 많을 수록" 커지기 때문에 만약 구간의 합이 답을 초과한다면 구간을 줄여야 하고, 부족하다면 구간을 늘여야 한다. 따라서 탐색 범위을 양쪽에서 줄여나가던 앞선 투 포인터 기법과는 달리, 이 경우엔 "고려할 범위을 늘릴 포인터", "고려할 범위 줄일 포인터" 두 가지를 사용해야 한다.

따라서 일단 왼 끝에 포인터를 모두 둔 뒤, 오른쪽 방향으로 움직이며 문제를 풀어보자 (오른쪽 끝에 오른쪽에서 왼쪽으로 움직여도 무관하다.)

고려할 구간의 범위를 늘이기 위해 e가 계속 오른쪽으로 이동하다보면, 어느순간 구간의 합이 6이 되어 답이 5보다 커지게 된다. 이제 고려대상을 줄이기 위해 s 를 오른쪽으로 이동하게 된다.

이렇게 [2,4) 구간을 찾을 수 있게 되고,이러한 방식으로 계속 진행하게 되면 [5,6)구간 까지, 조건을 만족하는 총 2개의 구간을 찾을 수 있다. 코드로 나타내면 다음과 같다.

int[] arr = {1,2,3,4,5,6};

int s = 0;
int e = 0;
int sum = 0;

// 인덱스 s 이상, 인덱스 e 미만의 구간 찾기
while(e<6){
    if(sum <= 5){
    	if(sum == 5) System.out.println(s+"이상"+e+"미만");
        sum += arr[e++];
    }
    else{
        sum -= arr[s++];
    }
}

 

투 포인터는 위와 같이 특정 조건을 만족하는 구간을 찾을 때에도 자주 사용된다. 포인터가 같은 방향으로 이동하게 되는 경우를 마치 움직이는게 자벌레 같다해서 인치웜(inch-worm) 기법이라고도 한다. 만약 두 포인터가 거의 비슷한 간격을 유지하면서 움직일 경우에는 창문처럼 움직인다 하여 슬라이딩 윈도우(sliding window) 기법이라고도 부른다.

 

투포인터를 사용할 때 주의할 점은 다음과 같다.

먼저, 경향성이 있는 선형 자료구조에서만 사용 가능하다.정확히 말하면, 저장된 위치(인덱스)에 따라 경향성이 존재하여, 포인터를 움직이는 것으로 답이 되는 조건을 배제할 수 있는 경우에만 사용이 가능하다.

가끔 '정렬된 배열(리스트)'에서만 사용가능하다는 식으로 알려주는 경우도 있는데, 이는 틀린 말이다. 사칙연산을 통해 숫자쌍을 찾는 예제의 경우에야 경향성이란 정렬을 의미하지만, 위와 같이 누적값을 찾는 경우엔 배열이 정렬되어 있지 않아도 사용 가능하기 때문이다.

두번째로 인덱스 처리에 주의해야 한다. 특정 숫자 쌍을 찾을 때 만약 중복되는 숫자가 없다면 답을 찾는 순간 s와 e를 동시에 이동해도 되겠지만, 중복되는 숫자가 있는 경우엔 둘중 한가지만 이동해야 한다. 두 포인터가 겹칠 때를 고려하냐 안하냐에 따라 반복문의 조건이 달라질 수 있으며, 인치웜이나 슬라이딩 윈도우의 경우 한쪽 끝에 다다랐을 때 증감연산을 제대로 고려하지 않으면 인덱스 초과 오류가 날 수도 있으니 반드시 엣지케이스를 잘 고려하자.

 

마지막으로, s와 e 두개의 포인터를 사용한다고 무조건 투 포인터 기법은 아니다. 많이 사용하게 될 이진 탐색도 탐색 범위를 줄여나가기 위해 두개의 포인터를 사용하지만 투 포인터 기법이라고 부르지는 않는다.

---

요약 : 투 포인터(two pointer)

• 위치 변수 두개를 이용하여 탐색범위를 줄여나가는 알고리즘 기법
• 경향성이 있는 선형 자료구조에서 사용가능
• 이중for문을 사용한 완전탐색에 필요한 시간(O(N^2))을 단축(O(N))
• 주로 사용되는 곳
  • 특정 조건을 만족하는 쌍을 찾을 때
  • 특정 조건을 만족하는 범위를 찾을 때

---

- 최종 수정일 : 25-03-21

- 이 글은 지속적으로 수정되고 있으며, 오타나 잘못된 정보에 대한 사항은 댓글로 남겨주시면 감사하겠습니다.