<투 포인터> 투 포인터의 원리

투 포인터 알고리즘은 중첩 반복문(보통 $O(N^2)$ 즉 for문 2개)을 $O(N)$의 복잡도로 수행할 수 있는 상황에 많이 쓰입니다. 상당히 매력적입니다. 포인터 2개니까 느낌적으로 중첩 반복문 역할을 수행하는구나 라는 생각이 들겠지만 저를 포함해서 아마 많은 분들이 정확한 동작 과정을 모르실 거라 생각돼서 이 글을 쓰게 되었습니다.

한 문제를 중첩 반복문과 투 포인터로 해결해보고 비교 과정을 통해 원리를 알아봅니다.

문제

양수로 이루어진 길이 N의 배열이 주어지고 자기 자신을 포함한 일정 구간의 배열을 부분 배열이라고 칭합시다. 이 때 부분 배열에 포함되는 수의 합이 m이 되는 경우의 수를 구해봅니다.

문제는 투 포인터를 활용해서 해결해야 하는 대표적인 문제로 중첩 반복문을 이용해 해결하면 시간 초과가 나도록 N을 크게 설정해놓는 문제가 많습니다.

중첩 반복문을 통해 해결

시간 복잡도는 생각하지 않고 중첩 반복문을 이용한 풀이는 아래와 같습니다.
부분합을 미리 구해놓고 for문 2개를 중첩해서 해결하였습니다.

import java.util.*;

class Main{
  public static void main(String[] args){
import java.util.*;

class Main{
  public static void main(String[] args){
    int[] numbers = {/*배열*/};
    int m = /*목표 합*/;
    
    int[] sum = new int[numbers.length+1];
    
    int now = 0;
    for(int i = 1; i<numbers.length+1; i++){
      now += numbers[i-1];
      sum[i] = now;
    }
    
    int answer = 0;
    
    for(int i=1; i<numbers.length+1; i++){
      for(int j=i; j<numbers.length+1; j++){
        if(sum[j] - sum[i-1] == m){
          answer++;
        }
      }
    }
    
    System.out.print(answer);
  }
}

투 포인터를 이용한 해결

안쪽 for문을 담당하던 변수 j를 for문 밖으로 빼서 선언했습니다.
이렇게 되면 j와 i 모두 배열을 한번만 탐색하게 됩니다.

이렇게 할 수 있는 이유는 무엇일까요? 투 포인터를 어떤 문제에 적용할 수 있을지에 대한 근본적인 질문입니다. 예를 들어 i를 고정시켜보겠습니다. i가 고정된 상태에서 j가 오른쪽으로 이동하면 수열의 합은 커집니다. 작아지진 않습니다. j가 고정된 상태에서 i가 움직이면 수열의 합은 작아집니다. 커지진 않습니다. 그래서 서로에게 종속적이지 않고 따로 움직이는게 가능합니다.

import java.util.*;

class Main{
  public static void main(String[] args){
import java.util.*;

class Main{
  public static void main(String[] args){
    int[] numbers = {/*배열*/};
    int m = /*목표 합*/;
    
    int[] sum = new int[numbers.length+1];
    
    int now = 0;
    for(int i = 1; i<numbers.length+1; i++){
      now += numbers[i-1];
      sum[i] = now;
    }
    
    int answer = 0;
    
    int j = 1;
    for(int i=1; i<numbers.length+1; i++){
      for(; j<numbers.legnth+1; j++){
        if(sum[j] - sum[i-1] == m){
          answer++;
        }else if(sum[j] - sum[i-1] > m)
          break;
      }
    }
    
    System.out.print(answer);
  }
}

결론

실제 중첩 반복문을 투 포인터로 변경함으로써 어떤 방식으로 투 포인터가 동작하는지 알아보았습니다. 투 포인터를 변수로 나누어 억지로 적용하려고 하면 직관적이지 않습니다. 위와 같은 과정을 충분히 익히는게 중요하다고 생각합니다.