신입 개발자를 위한 Repository를 만들었습니다. 공부한 내용을 정리 중이니 도움이 되신다면 와서 Star를 눌러주시면 감사하겠습니다.

알고리즘 문제를 풀다가 완전 탐색으로 해결하면 시간 초과가 나서 어떻게 풀어야 하는가 하다가 검색해보니 투 포인터 알고리즘이라는 개념이 나와서 간단하게 정리하고 넘어가겠다.

1차원 배열이 있고 이 배열에서 각자 다른 원소를 가리키고 있는 2개의 포인터를 조작해가면서 원하는 것을 얻는 형태이다. 이 때문에 투 포인터 알고리즘이라고 부른다.

대표적인 문제

문제는 N칸의 1차원 배열이 있을 때, 부분 배열 중 그 원소의 합이 M이 되는 경우의 수를 구하는 것이다. 모든 경우의 수를 다 테스트해보면, 구간 합을 구간합 배열로 O(1)만에 구한다고 해도 경우의 수가 (N^2)이 된다. 따라서 문제를 풀 수 없다.

이 문제에서 각 원소는 자연수이고 M 또한 자연수인데, 이 조건이 성립하면 사용할 수 있는 알고리즘은 다음과 같다.

  • 포인터 2개를 준비한다. 시작과 끝을 나타낼 수 있도록 start, end라고 하겠다.
  • 맨 처음에는 start = end = 0이며, 항상 start<=end 을 만족해야 한다.
  • 이 두개의 포인터는 현재 부분 배열의 시작과 끝을 가리키는 역할을 한다.

s = e일 경우 그건 크기가 0인 즉, 아무것도 포함하지 않는 부분 배열을 뜻한다. 이제 아래의 과정을 start<N 인 동안 반복한다.

  1. 현재 부분합이 M 이상이거나, 이미 end = N이면 start++
  2. 그렇지 않다면 end++
  3. 현재 부분합이 M과 같다면 count++

쉽게 이해하자면, start와 end를 무조건 증가시키는 방향으로만 변화시켜가면서, 도중에 부분 배열의 합이 정확히 M이 되는 경우를 세는 것이다.

그림으로 보는게 편하다. 그림을 그리기에는 시간이 좀 걸려서 내가 보고 이해한 그림을 첨부하겠다. 아래 참고한 블로그를 보면 설명을 아주 잘해주셨다. 이것만 보면 이해가 될 것이다.

대표적인 문제를 풀어봤다. 백준 2003번으로 수들의 합2 문제이다. 풀이는 아래와 같다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
/**
 * 투포인터 알고리즘
 * start : 시작
 * end : 끝
 */
public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] input = br.readLine().split(" ");
        int n = parse(input[0]);
        int m = parse(input[1]);

        int[] arr = new int[n + 1];

        String[] num = br.readLine().split(" ");
        for (int i = 1; i <= n; i++) {
            arr[i] = parse(num[i - 1]);
        }

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

        while (true) {
            // 부분합이 m 보다 큰 경우 start 가 가리키는 원소를 빼고
            // start 의 값을 증가시킨다. 즉, start 뒤로 이동.
            if (sum >= m) {
                sum = sum - arr[start++];

                // end 가 n 에 도달하면 종료한다.
            } else if (end == n) {
                break;
            } else {
                // 위의 두 경우에 해당하지 않으면 end 는 뒤로 이동하면서 원소의 값을
                // sum 에 더한다.
                sum = sum + arr[end++];
            }

            // 부분 합이 m 과 같다면 count 를 증가시켜준다.
            if (sum == m) {
                count++;
            }
        }
        System.out.println(count);
    }

    private static int parse(String str) {
        return Integer.parseInt(str);
    }
}

참고