오늘은 투 포인터 알고리즘에 대해서 공부해보자.
이 투 포인터를 모르면 코테에서 낭패를 볼 수 있다?라고 말할 정도로 생각보다 중요한 알고리즘 테크닉이다.
남들도 다 아는 알고리즘을 나만 몰라서 틀린다.. 이거 매우 억울한 일이다. 얼른 공부해서 습득하자!
투 포인터 (Two pointer)
이름과 똑같이 두 개의 포인터를 가지고 문제를 해결하는 알고리즘이다.
문제를 풀다보면 배열의 길이가 2중 포문으로 해결을 할 수 없을 정도로 큰 배열이 주어지게 됐을 때, 구간의 합이 M인 곳이 몇 개 인지? 물어보는 문제에서는 완전 탐색으로는 시간 초과로 해결할 수 없는 문제가 있다.
대표적으로 BOJ2003 수들의 합2 문제와 BOJ2470 두 용액 문제다.
이런 문제들의 특징은 입력 크기가 너무 커서 완전 탐색으로는 해결할 수 없는 문제들이다.
이럴 때 사용하는 것이 바로 투 포인터 알고리즘이다.
투 포인터 알고리즘이 강력한 이유
두 개의 포인터만 하나의 배열에서 움직이므로 O(N) + O(N) = O(2N) => 시간 복잡도 O(N)
투 포인터 알고리즘의 유형은 2가지가 있는데 다음과 같다.
- 포인터 2개가 같은 방향으로 진행하기
- 포인터 하나는 왼쪽에서 오른쪽으로, 다른 하나는 오른쪽에서 왼쪽으로 진행하기
성능은 알겠는데 어떻게 구현하고 사용할까?
위의 문제를 예시로 살펴보자.
이 문제는 투 포인터 알고리즘 유형의 1번에 속하는 문제다.
포인터 2개가 같은 방향으로 진행하기
두 포인터가 배열의 첫 번째부터 시작해서 한 step씩 확인하면서 구간의 합이 M이 되는지 체크해서 문제를 해결해나간다.
들어가기 앞서서 사전 작업이 있다.
- left 포인터와 right 포인터는 모두 0으로 시작한다.
- 현재 구간의 합은 left와 right모두 0을 가리키고 있기 때문에 배열의 첫 번째 값이 된다.
- 반드시 left는 right보다 같거나 작아야 한다. 이 순서가 꼬이게 되면 알 수 없는 상황이 발생할 수 있다.
위의 사전 작업을 숙지하고 아래를 보자.
- 현재 구간의 합 sum < M
- 아직 구간의 합이 M보다 작기 때문에 늘리려면 어떻게 할까? right 포인터를 한 칸 오른쪽으로 늘리면 된다.
- 현재 구간의 합 sum > M
- 구간의 합이 M보다 커졌다. 이럴 때는 줄여야 한다. left 포인터를 한 칸 오른쪽으로 늘리면 된다.
- 현재 구간의 합 sum == M
- 우리가 원하는 구간의 합 M을 찾았기 때문에 정답을 +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;
}
처음 봐도 이해가 잘 되지 않는다면, 공책을 펼쳐놓고 직접 디버깅해보자!
어떤 알고리즘이든 한 번에 습득하기 어렵다. 반복 숙달하자.
이번에는 다른 스타일의 문제를 살펴보자.
이 문제의 유형은 위에서 말했듯이 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;
}
정리해보면 투 포인터 알고리즘은 다음과 같다.
유형에 익숙해지는 것도 좋지만,
투 포인터를 어떤 조건일 때는 증가시키고 감소시키는지를 잘 결정하면 어떤 유형이 나오더라도 해결할 수 있을 것이다.
연습문제
'Algorithm > Algorithm Concept' 카테고리의 다른 글
행렬의 다양한 연산들 (0) | 2021.10.11 |
---|---|
플로이드 워셜 (Floyd Warshall) (0) | 2021.09.03 |
다익스트라 알고리즘 (0) | 2021.08.24 |
최단 경로 알고리즘(Shortest Path) (0) | 2021.08.23 |
수학 관련 (0) | 2021.08.18 |