투 포인터

오늘은 투 포인터 알고리즘에 대해서 공부해보자.

이 투 포인터를 모르면 코테에서 낭패를 볼 수 있다?라고 말할 정도로 생각보다 중요한 알고리즘 테크닉이다.

남들도 다 아는 알고리즘을 나만 몰라서 틀린다.. 이거 매우 억울한 일이다. 얼른 공부해서 습득하자!

투 포인터 (Two pointer)

이름과 똑같이 두 개의 포인터를 가지고 문제를 해결하는 알고리즘이다.

문제를 풀다보면 배열의 길이가 2중 포문으로 해결을 할 수 없을 정도로 큰 배열이 주어지게 됐을 때, 구간의 합이 M인 곳이 몇 개 인지? 물어보는 문제에서는 완전 탐색으로는 시간 초과로 해결할 수 없는 문제가 있다.

대표적으로 BOJ2003 수들의 합2 문제와 BOJ2470 두 용액 문제다.

 

이런 문제들의 특징은 입력 크기가 너무 커서 완전 탐색으로는 해결할 수 없는 문제들이다.

이럴 때 사용하는 것이 바로 투 포인터 알고리즘이다.

 

투 포인터 알고리즘이 강력한 이유

두 개의 포인터만 하나의 배열에서 움직이므로 O(N) + O(N) = O(2N) => 시간 복잡도 O(N)

 

투 포인터 알고리즘의 유형은 2가지가 있는데 다음과 같다.

1. 포인터 2개가 같은 방향으로 진행하기
2. 포인터 하나는 왼쪽에서 오른쪽으로, 다른 하나는 오른쪽에서 왼쪽으로 진행하기

성능은 알겠는데 어떻게 구현하고 사용할까?

 

BOJ2003 수들의 합 2 

위의 문제를 예시로 살펴보자.

이 문제는 투 포인터 알고리즘 유형의 1번에 속하는 문제다.

포인터 2개가 같은 방향으로 진행하기

두 포인터가 배열의 첫 번째부터 시작해서 한 step씩 확인하면서 구간의 합이 M이 되는지 체크해서 문제를 해결해나간다.

들어가기 앞서서 사전 작업이 있다.

• left 포인터와 right 포인터는 모두 0으로 시작한다.
• 현재 구간의 합은 left와 right모두 0을 가리키고 있기 때문에 배열의 첫 번째 값이 된다.
• 반드시 left는 right보다 같거나 작아야 한다. 이 순서가 꼬이게 되면 알 수 없는 상황이 발생할 수 있다.

위의 사전 작업을 숙지하고 아래를 보자.

1. 현재 구간의 합 sum < M
   1. 아직 구간의 합이 M보다 작기 때문에 늘리려면 어떻게 할까? right 포인터를 한 칸 오른쪽으로 늘리면 된다.
2. 현재 구간의 합 sum > M
   1. 구간의 합이 M보다 커졌다. 이럴 때는 줄여야 한다. left 포인터를 한 칸 오른쪽으로 늘리면 된다.
3. 현재 구간의 합 sum == M
   1. 우리가 원하는 구간의 합 M을 찾았기 때문에 정답을 +1 하자.
   2. 그런 다음 두 포인터를 모두 한 칸씩 늘리면 된다. 왜?
      1. 현재 구간의 합이 답이 되기 때문에 left를 한 칸 늘리거나, right를 한 칸 늘려도 절대 답이 될 수 없기 때문이다.

위의 이론을 바탕으로 구현을 하게 되면 아래의 구현처럼 된다.

//2003 수들의 합2
#include <iostream>
using namespace std;

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    
    int n, m;
    int arr[10001];
    
    cin >> n >> m;
    for(int i = 0; i < n; i++) cin >> arr[i];
    
    int left = 0;
    int right = 0;
    int sum = arr[0]; //처음에 left, right가 모두 0을 가르키고 있기 때문에 합은 첫번째 배열의 값이다.
    int ans = 0;
    while(right < n) {
        //합이 m보다 작으면 right 포인터를 오른쪽으로 이동
        if(sum < m) {
            right++;
            if(right < n)
                sum += arr[right];
        }
        //합이 m보다 크다면 left 포인터를 오른쪽으로 이동
        else if(sum > m) {
            sum -= arr[left];
            left++;
        }
        //합이 같다면 두 포인터 모두 오른쪽으로 이동하고, 정답을 +1
        else {
            sum -= arr[left];
            left++;
            right++;
            if(right < n)
                sum += arr[right];
            
            ans++;
        }
    }
    cout << ans << endl;
    return 0;
}

처음 봐도 이해가 잘 되지 않는다면, 공책을 펼쳐놓고 직접 디버깅해보자!

어떤 알고리즘이든 한 번에 습득하기 어렵다. 반복 숙달하자.

 

BOJ2470 두 용액

이번에는 다른 스타일의 문제를 살펴보자.

이 문제의 유형은 위에서 말했듯이 2번 스타일이다.

포인터 하나는 왼쪽에서 오른쪽, 다른 하나는 오른쪽에서 왼쪽으로 진행

 

그렇다면 사전 작업은 어떻게 할까?

• left는 0, right는 n - 1
• ans는 초기 두 용액의 합으로 나올 수 있는 절댓값인 20억으로 세팅하기
• 합이 0에 가까운 두 용액을 저장할 변수

사전 작업을 숙지하고 어떻게 풀지 생각해보자.

두 용액의 합을 0에 가깝게 만들기 위해서는 최대한 왼쪽에 있는 애들은 오른쪽 애들보다 작아야 할 것이다.

그렇기 때문에 처음에 정렬을 수행한다. 이렇게 되면 왼쪽에는 작은 애들이 몰리고, 오른쪽은 큰 애들이 몰린다.

이렇게 세팅을 한 후 두 용액을 합쳤을 때 기존에 저장된 ans보다 더 작고 0에 가깝다면 갱신을 시키면서 문제를 해결해나간다.

정리하면 다음과 같다.

• 우선 입력된 배열을 정렬한다.
• 두 용액의 합의 절댓값이 기존에 저장된 ans보다 더 작다면? 갱신하자.
  • ans = abs(arr[left] + arr[right]
  • ret[0] = arr[left] 두 용액 중 왼쪽 용액 저장
  • ret[1] = arr[right] 두 용액 중 오른쪽 용액 저장
• arr[left] + arr[right] < 0
  • 두 용액의 합이 0보다 작다는 말은 무슨 뜻일까?
  • 0에 가깝게 만들기 위해서는 left를 오른쪽으로 옮겨주면 된다.
• arr[left] + arr[right] > 0
  • 반대로 0보다 크다면?
  • 0에 가깝게 만들기 위해서는 right를 왼쪽으로 옮겨주면 된다.

위의 이론을 바탕으로 구현을 하게 되면 아래의 구현처럼 된다.

//2470 두 용액
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;

int n;
int arr[100001];

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    
    cin >> n;
    for(int i = 0; i < n; i++) cin >> arr[i];
    sort(arr, arr + n); //정렬 필수, 서로 합이 0에 가깝게 만들기 위해서
    
    int left = 0;
    int right = n - 1;
    int ans = 2e9; // 두 용액의 합을 최대 20억으로 잡아두고 시작
    int ret[2];
    while(left < right) {
        //두 용액의 합이 0에 가까운지 확인하기
        int value = arr[left] + arr[right];
        
        if(ans > abs(value)) {
            ret[0] = arr[left];
            ret[1] = arr[right];
            ans = abs(value);
            
            // 합이 0이면 탈출하자.
            if(value == 0) break;
        }
        
        if(value > 0) right--;
        else left++;
    }
    cout << ret[0] << ' ' << ret[1] << endl;
    return 0;
}

정리해보면 투 포인터 알고리즘은 다음과 같다.

유형에 익숙해지는 것도 좋지만,

투 포인터를 어떤 조건일 때는 증가시키고 감소시키는지를 잘 결정하면 어떤 유형이 나오더라도 해결할 수 있을 것이다.

연습문제

부분합

수 고르기

회전 초밥

소수의 연속합

세 용액

[카카오 인턴] 보석 쇼핑