[알고리즘] 투포인터 알고리즘

신입 개발자를 위한 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);
}
}

참고

Share