Two pointers algorithm
Two pointers algorithm은 연산량을 줄여주는 효과적인 알고리즘입니다. 주로 원하는 해를 구하는 문제의 연산량 줄이기에 사용되는데, 구현 자체는 그렇게 어렵지 않아서 알아두면 두고두고 쓸 일이 많을 겁니다.
Two pointers algorithm은 두개의 지점을 최종 지점으로 움직이면서 몇가지 처리를 하면 원하는 해가 구해지는 형태입니다.
https://www.acmicpc.net/problem/2003
2003번: 수들의 합 2
첫째 줄에 N(1 ≤ N ≤ 10,000), M(1 ≤ M ≤ 300,000,000)이 주어진다. 다음 줄에는 A[1], A[2], …, A[N]이 공백으로 분리되어 주어진다. 각각의 A[x]는 30,000을 넘지 않는 자연수이다.
www.acmicpc.net
연속된 구간의 합이 M이 되는 모든 경우의 수를 구하는 문제입니다.
N의 범위가 10000으로 그냥 완전탐색을 돌리게 되면 시간초과가 날 것입니다. 그렇기 때문에, Two pointers algorithm를 사용해 O(n^2)보다 적은 시간에 해결해 볼 수 있습니다.
여기서 고려해야 하는 것은 "구간을 어떻게 진행하여 값을 찾아낼 것인가?" 입니다.
O(n^2)의 얘기를 조금 해 보자면, 연속 구간을 찾아서 합을 구할 때 M을 넘어가는 순간에도 계속해서 연산을 했었습니다. 보통 A[i]의 수 중에 음수가 존재한다면 M을 넘어가는 순간에도 그 뒤를 봐야하기 때문에 연산을 계속하는 것이 맞습니다. 하지만, 이 문제의 경우에는 양수만 존재하기 때문에 그 뒤는 굳이 연산해 줄 필요가 없습니다. 즉, 이 부분에서 오버 연산이 일어난다는 것입니다.
그럼 다시 본론으로 넘어와서, 알아낸 것을 바탕으로 정리를 해 보자면. "M을 초과할 시에는 연산할 필요가 없다." 라는 결론을 이용해 연산량을 줄일 것입니다.
첫번째 지점을 진행하며 계속해서 배열의 값을 더해가다가 만약 M을 초과해 버리면? 그 뒤로는 연산할 필요가 없으니까 두번째 지점을 진행하면서 M보다 큰 동안 해당 인덱스를 제거해 줍니다.
정리하자면, 첫번째 지점을 이동할 때에는 구간 확장, 두번째 지점을 이동할 때에는 구간 축소를 하게 됩니다.
해결 코드는 다음과 같습니다.
|
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
|
#include <iostream>
using namespace std;
typedef long long int INT;
int main()
{
int n, m; cin >> n >> m;
INT d[10010] = {};
for(int i=0; i<n; i++) cin >> d[i];
int r = 0, sum = 0, cnt = 0;
for(int l = 0; l < n; l++) {
sum += d[l];
while(sum > m) {
sum -= d[r];
r++;
}
if(sum == m) cnt++;
}
cout << cnt << "\n";
return 0;
}
|
cs |
코드를 보면 매우 간단한데, 아까 위에서 언급했듯이 시간복잡도를 계산해보면 요리보고 저리봐도 O(n)에 해결할 수 있다는 것을 알 수 있습니다.
https://www.acmicpc.net/problem/3273
3273번: 두 수의 합
n개의 서로 다른 양의 정수 a1, a2, ..., an으로 이루어진 수열이 있다. ai의 값은 1보다 크거나 같고, 1000000보다 작거나 같은 자연수이다. 자연수 x가 주어졌을 때, ai + aj = x (1 ≤ i < j ≤ n)을 만족하는
www.acmicpc.net
두 수를 더해서 x값이 되는 경우의 수를 구하는 문제입니다.
이 문제도 역시 시간복잡도 O(n^2)로 완전탐색을 진행할 수도 있지만, Two pointers algorithm을 이용해 O(n)으로 줄일 수 있습니다.
이 문제에서 Two pointers algorithm은 조금 다르게 사용됩니다. 위의 경우에는 두 지점을 모두 시작점에 두고 진행시켰다면, 이 문제의 경우에는 두 지점을 배열의 양끝지점에 두고 중앙으로 모으면서 연산을 진행합니다.
여기서 고려해야 할 것은 "두 지점을 어떻게 움직일 것인가?" 입니다.
우선 배열을 정렬할 필요가 있습니다. 그 이유는 뒤에서 더 자세히 다루겠습니다.
그 다음, 더한 값이 x와 같은지 다른지를 판단해 체크해 주면 됩니다.
마지막으로는 양 끝에 두 지점을 더하면서 만약 더한 값이 x보다 크다면! 두번째 지점을 배열의 중앙 쪽으로 한칸 이동시키고, 아니라면 첫번째 지점을 배열의 중앙 쪽으로 한칸 이동시킵니다.
이때, 아까 정렬한 이유가 나오는데, 정렬을 하지 않을 경우에는 확실히 어디가 큰지 확인하는 것이 골치 아파지므로 정렬을 통해서 확실한 기준을 세우기 위해서 정렬을 한 것입니다.
마지막 연산은 두 지점이 만나지 않는 동안 진행해 주면 됩니다. 왜냐하면 만난 순간 부터는 이미 값들이 모두 연산된 후이기 때문에 그 이후의 연산이 필요가 없는 것입니다. 큰 두수를 더해서 x가 나오지도 않고, 작은 두수를 더해서 x가 나오지도 않기 때문에 이것이 가능합니다.
해결 코드는 다음과 같습니다.
|
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 <cstdio>
#include <algorithm>
int main()
{
int n; scanf("%d", &n);
int a[100010] = {};
for(int i=0; i<n; i++)
scanf("%d", a+i);
int x; scanf("%d", &x);
std::sort(a, a+n);
int fp = 0, ep = n-1, ans = 0;
while(fp != ep) {
if(a[fp]+a[ep] == x) ans += 1;
if(a[fp]+a[ep] > x) {
ep--;
} else {
fp++;
}
}
printf("%d", ans);
return 0;
}
|
cs |
위 두 예시는 Two pointers algorithm을 사용해서 문제를 풀 때 사용하는 가장 기초적인 방법 2가지 입니다.
연습문제는 아래 링크에서 만나보세요!
소수의 연속합
https://www.acmicpc.net/problem/1644
에라토스테네스의 체를 이용해 소수를 찾아주고, N을 만드는 것이 가능한지를 찾아주면 되는 문제입니다. 그냥 소수 판별로 하면 시간초과가 걸릴 수도 있습니다.
세 용액
https://www.acmicpc.net/problem/2473
meet in the middle을 이용해 첫번째 용액을 제외한 나머지 두용액을 O(n)에 찾을 수 있습니다. 정렬을 포함한 용액을 찾는 과정의 시간복잡도를 모두 합하면 O(n log n + n^2)에 풀 수 있습니다.
배열 합치기
https://www.acmicpc.net/problem/11728
조금 특이한? Two pointers algorithm을 사용해야 합니다. 두 지점을 각 배열의 시작점으로 두고, 더 작은 쪽을 먼저 결과 배열에 채우는 연산을 반복해서 해결할 수 있습니다. 이 때, 마지막 수는 비교할 것이 없어서 출력이 잘 이루어지지 않을 수도 있는데, 이것은 배열의 마지막에 큰 수를 넣어주어서 해결이 가능하다.