Algorithm - Two pointers (Baekjoon 2003, 2559 C)

Docs › Algorithm
, ,

투 포인터

배열과 같은 선형자료구조에서 특정 부분집합을 빠르게 찾아낼 때 이용한다. 알고리즘 이름의 포인터는 실제로 C의 포인터 개념이 아니다. 배열의 인덱스라고 생각하자. 하나의 배열을 두 개의 포인터를 이용해서 특정한 부분을 찾아낼 수 있는 알고리즘이다.

시간복잡도는 O(N)이다. 매 반복마다 두 포인터의 하나는 1씩 증가하고, 둘 중 하나가 배열의 끝에 도달해야 문제를 풀 수 있기 때문이다.

백준 - 수들의 합 2 (실버4)

  • https://www.acmicpc.net/problem/2003
  • N개의 수로 된 수열 A[1], A[2], …, A[N] 이 있다. 이 수열의 i번째 수부터 j번째 수까지의 합 A[i] + A[i+1] + … + A[j-1] + A[j]가 M이 되는 경우의 수를 구하는 프로그램
    • 입력 
      1
      2
      4 2
      1 1 1 1
    • 출력 
      1
      3
  • C 코드
    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
    #include <stdio.h>

    int n, m;

    int main() {
        scanf("%d %d", &n, &m);
        int arr[n];
        for (int i = 0; i < n; i++) {
            scanf("%d", &arr[i]);
        }

        int cnt = 0;
        int left = -1;
        int right = -1;
        int sum = 0;

        while (left <= right && right < n) {
            if (sum > m) {
                sum -= arr[++left];
            } else if (sum < m) {
                sum += arr[++right];
            } else if (sum == m) {
                cnt++;
                sum += arr[++right];
            }

        }

        printf("%d\n", cnt);
    }

n개의 정수로 이루어진 수열이 있을 때, 연속된 값의 합이 m이 되는 경우의 수를 구하는 문제이다. 연속된 값을 더하는 것이 핵심이기 때문이기 때문에 투 포인터 알고리즘을 이용한다. left와 right 변수를 하나씩 두고 조건에 따라 둘 중 하나의 포인터를 이동시켜 그 값을 더하거나 뺀다. 중요한 것은 left는 항상 right의 왼쪽에 위치하고, right는 정수의 크기 즉, n보다 작아야 한다.

연속된 값이 m이 되는 경우의 수를 구하는 것이기 때문에 조건은 sum이 m보다 큰가, 작은가, 같은가로 나눌 수 있다. 만약 sum이 m보다 크다면 left를 오른쪽으로 한 칸 이동시켜 left가 가리키는 값을 sum에서 뺀다. 만약 sum이 m보다 작다면 right를 오른쪽으로 한 칸 이동시켜 right가 가리키는 값을 sum에 더한다. sum과 m이 같다면 cnt를 증가시켜주고 right를 오른쪽으로 한 칸 이동시키고 다른 경우의 수를 찾는다.

백준 - 수열 (실버3)

  • https://www.acmicpc.net/problem/2559
  • n개 정수의 수열이 주어졌을 때, 연속적인 k개의 값의 합이 가장 큰 값을 계산
    • 입력 
      1
      2
      10 2
      3 -2 -4 -9 0 3 7 13 8 -3
    • 출력 
      1
      21
  • C 코드
    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
    #include <stdio.h>

    int n,k;

    int main() {
        scanf("%d %d", &n, &k);
        int arr[n];
        for (int i = 0; i < n; i++) {
            scanf("%d", &arr[i]);
        }

        int sum = 0;
        int max = 0;
        for (int i = 0; i < k; i++) {
            sum += arr[i];
        }

        max = sum;
        for (int i = k; i < n; i++) {
            sum += arr[i];
            sum -= arr[i-k];
            if (sum > max) {
                max = sum;
            }
        }

        printf("%d\n", max);
    }

앞의 문제와 다르게 합이 m이 되는 경우의 수를 구하는 것이 아닌, k개의 연속된 값의 합이 가장 큰 값을 계산해야 한다. 앞의 문제는 연속된 값이 수를 예측할 수 없기 때문에 left와 right를 독립적으로 계산했지만 이 문제는 연속된 값의 수를 알 수 있기 때문에 굳이 그러지 않아도 된다. i와 i-k 번째 인덱스(투 포인터 알고리즘에서 포인터의 개념)로 left와 right를 대체할 수 있다.

처음에 arr[0] ~ arr[k-1]의 합을 구해주고 max로 저장한다. 이 값이 기준점이 될 것이고, 이 값보다 큰 경우 새로운 값을 max로 지정할 것이다. arr[k]에서 arr[n-1]로 반복이 진행될 동안 arri를 sum에 더하고 arri-k를 sum에서 빼준다. 해당 반복이 끝나면 문제에서 요구하는 max를 구할 수 있다.