[알고리즘&코딩테스트] 투 포인터 알고리즘 (Two Pointers)

투 포인터란?

---

· 화살표 두 개에 의미를 부여해서 탐색 범위를 압축하는 방법이다.

· 두 개의 화살표 우치를 기록하면서 문제를 처리한다.

 

카테고리

---

1. 1차원 배열 위에 2개의 포인터를 만드는 경우

· 해당 카테고리는 두가지로 나뉜다.

1. 2개의 포인터가 모두 왼쪽에서 시작해서 같은 방향으로 이동

 

2. 2개의 포인터가 양 끝에서 서로를 향해 이동

 

2. 관찰을 통해서 문제에 등장하는 변수 2개의 값을 두 포인터로 표현하는 경우

ex) A와 B 변수의 곱의 최소 값 구하기

 

꿀팁

---

·  다음의 키워드가 등장하면 두 포인터 접근을 시도해 볼 가치가 있다.

- 1차원 배열에서의 "연속 부분 수열" or "순서를 지키며 차례대로"

- 곱의 최소

 

예제

---

BOJ 1806 - 부분합

· 문제링크: https://www.acmicpc.net/problem/1806

문제: 10,000 이하의 자연수로 이루어진 길이 N짜리 수열이 주어진다. 이 수열에서 연속된 수들의 부분합 중에 그 합이 S 이상이 되는 것 중, 가장 짧은 것의 길이를 구하는 프로그램을 작성하시오. 입력: 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. 출력: 첫째 줄에 구하고자 하는 최소의 길이를 출력한다. 만일 그러한 합을 만드는 것이 불가능하다면 0을 출력하면 된다.

· 문제 파악

- "연속된 수들"이라는 키워드가 존재하므로 두 포인터를 고려한다.

- N = 100,000, S = 100,000,000 이므로 두 변수 모두 Integer로 처리할 수 있다. 

- 시간 복잡도: O(N)

 

문제 풀이

1. N짜리 수열 중 왼쪽 시작을 결정한다. O(N)

2. R을 L의 위치에서 시작하여 오른쪽 끝으로 이동시킨다. 이때, 누적합을 계산한다. O(N)

3. 누적합이 S 이상이 되는 경우 탐색을 중단한다.

총 시간 복잡도: O(N^2)

주어진 수열을 위의 규칙으로 모두 탐색하면, 아래의 결과가 나온다.

 

투 포인터 방법으로 최적화

이때, 탐색 과정에서 R의 위치가 동일한 경우, 최초 탐색을 제외하고는 탐색할 필요는 없다.

L의 위치가 오른쪽으로 이동하면, 어차피 맨 처음 탐색한 값보다 작아서 의미가 없기 때문이다.

따라서 해당 부분을 검정색으로 처리한다. 

이 경우 아래의 규칙으로 탐색하게 되어, 시간 복잡도는 O(N)가 된다.

1. 왼쪽 시작 L의 이동 횟수 N번

2. 이전의 R부터 시작해서 R을 오른쪽 끝으로 이동 

3. L, R이 각장 최대 N번 이동하므로, O(N)

 

public class BOJ1806부분합 {
   static int n;
   static int S;
   static int[] a;

   public static void main(String[] args) {
      input();
      pro();
   }

   private static void input() {
      Scanner sc = new Scanner(System.in);
      n = sc.nextInt();
      S = sc.nextInt();
      a = new int[S + 1];
      for (int i = 1; i < a.length; i++) {
         a[i] = sc.nextInt();
      }
   }

   private static void pro() {
      int R = 0, sum = 0, ans = n + 1;
      for (int L = 1; L <= n; L++) {
         // L - 1을 구간에서 제외하기
         sum -= a[L - 1];

         // R을 옮길 수 있을 때 까지 옮기기
         while (R + 1 <= n && sum < S) {
            R++;
            sum += a[R];
         }

         // [L ... R]의 합, 즉 sum이 조건을 만족하면 정답 갱신하기
         if (sum >= S) {
            ans = Math.min(ans, R - L + 1);
         }
      }

      // ans 값을 보고 불가능 판단하기
      if (ans == n + 1) {
         ans = 0;
      }
      System.out.println(ans);
   }
}

 

BOJ 2470 - 두용액

· 문제링크: https://www.acmicpc.net/problem/2470