Post

투포인터

Posted
By ROOT
6 min read

투포인터란?

  • two pointer 라고 불린다.
  • 두 개의 포인터를 활용하여 문제를 해결하는 알고리즘이다.
  • 1차원 배열에서 두 개의 포인터 사이 원소들의 부분합을 구하는 문제가 대표적이다.


슬라이딩 윈도우

  • sliding window 라고 불린다.
  • 부분배열의 길이가 유동적으로 변하는 투포인터와 달리 슬라이딩 윈도우는 길이가 고정되어 있기 때문에 포인터 2개가 필요하지 않다.

투포인터에 비해 어렵지 않으므로 자세히 다루지는 않겠다.


일반적인 알고리즘

  • 부분 배열의 처음과 끝을 가리키는 start, end 를 정의한다.
  • 시작은 start = end = 0 이고, 항상 start <= end 를 만족해야 한다.
  • start = end 인 경우의 부분 배열은 크기가 0인, 아무것도 포함하지 않는다는 것을 뜻한다.
  • 다음의 과정을 start < N 동안 반복한다.

    부분합이 M과 같은 경우의 수를 구하는 문제라고 가정한다.

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


다양한 활용

  • 부분 배열에 end가 가리키는 원소를 포함하는 경우도 있다.
  • 또한 꼭 end를 0부터 시작하지 않고 문제 조건에 따라 배열의 끝부터 시작하는 경우도 있다. 투포인터


BOJ 2470 - 두 용액 (골드 5)

2470-두 용액

  • 이 문제는 부분합을 구하는 문제가 아니고 0에 가까운 두 용액을 찾는 문제다.
  • 음수와 양수가 모두 존재하기 때문에 오름차순 정렬을 한 후 양 끝에 두 포인터를 지정하고 탐색한다.
    • [-2 4 -99 -1 98] -> [-99 -2 -1 4 98]
  • 두 포인터가 가리키는 원소를 합해서 다음 경우에 따라 반복을 진행한다.
    • 합이 0인 경우 : 정답이므로 두 용액을 기록하고 반복을 종료한다.
    • 합이 양수인 경우 : end가 가리키는 원소의 크기를 줄여야 한다. end--
    • 합이 음수인 경우 : start가 가리키는 원소의 크기를 늘려야 한다. start++
  • 각 반복마다 0에 더 가까운 정답을 찾았는지 비교한다.
  • s==e 가 될 때까지 반복을 수행한다.

    풀이에서는 큰 의미는 없지만 원소가 모두 음수인 경우와 양수인 경우를 따로 처리했다.

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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85

import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    static FastReader scan = new FastReader();

    static StringBuilder sb = new StringBuilder();

    static int n;
    static int[] arr;
    static int liquid1;
    static int liquid2;
    static int sum;

    public static void main(String[] args) {
        input();
        solve();
        sb.append(liquid1);
        sb.append(" ");
        sb.append(liquid2);
        System.out.println(sb.toString());
    }
    static void input(){
        n = scan.nextInt();

        arr = new int[n];

        for (int i=0;i<n;i++){
            arr[i] = scan.nextInt();
        }
    }
    static void solve(){
        Arrays.sort(arr);

        if(arr[0] <= 0 && arr[n-1]<=0){
            liquid1 = arr[n-2];
            liquid2 = arr[n-1];
            return;
        }else if (arr[0]>=0 && arr[n-1]>=0){
            liquid1 = arr[0];
            liquid2 = arr[1];
            return;
        }

        int s=0;
        int e=n-1;
        liquid1 = arr[s];
        liquid2 = arr[e];
        sum = arr[s] + arr[e];

        while(s<e){
            int tmp=arr[s]+arr[e];
            if (tmp==0){
                liquid1 = arr[s];
                liquid2 = arr[e];
                sum = tmp;
                return;
            }
            if (isclose(tmp)){
                liquid1 = arr[s];
                liquid2 = arr[e];
                sum = tmp;
            }
            if (tmp>0){
                e--;
            }else{
                s++;
            }
        }
    }
    static boolean isclose(int t){
        if (Math.abs(sum)>Math.abs(t)){
            return true;
        }else{
            return false;
        }
    }

    static class FastReader {
        .
        .
        .
    }
}


투포인터를 사용하는 문제 리스트

이진 탐색과 마찬가지로 효과적인 성능으로 쓰이는 알고리즘이다. 투포인터는 다양한 방식으로 활용할 수 있으니 여러 유형의 문제들을 풀어보는 것이 좋다.


누군가가 물어본다면

투포인터는 1차원 배열에서 두 개의 포인터를 설정하여 문제를 해결하기 위한 알고리즘입니다.
algorithm
algorithm BOJ 투포인터 two pointer
This post is licensed under CC BY 4.0 by the author.