투 포인터란?
투 포인터: 1차원 배열에서 2개의 포인터의 움직임으로 원하는 값을 찾는 알고리즘이다.
(* 이 포인터 아니고 가르키는 의미의 포인터이다)
2중 for문을 사용할 수도 있겠지만 2중 for문의 시간 복잡도는 O(N²)이지만 투 포인터는 O(N)의 시간 복잡도를 갖는다.
투 포인터 알고리즘 과정
백준 2230 수 고르기 문제를 예시로 살펴보자
문제
N개의 정수로 이루어진 수열 A[1], A[2], …, A[N]이 있다. 이 수열에서 두 수를 골랐을 때(같은 수일 수도 있다), 그 차이가 M 이상이면서 제일 작은 경우를 구하는 프로그램을 작성하시오.
예를 들어 수열이 {1, 2, 3, 4, 5}라고 하자. 만약 M = 3일 경우, 1 4, 1 5, 2 5를 골랐을 때 그 차이가 M 이상이 된다. 이 중에서 차이가 가장 작은 경우는 1 4나 2 5를 골랐을 때의 3이 된다.
투 포인터를 활용해서 어떻게 풀 수 있을까?
- 두 개의 포인터 st와 en으로 배열의 시작을 가르킨다.
- A[en] - A[st] >= M이 될 때까지 en을 증가시키고 m보다 커질 때 최솟값을 갱신한다.
- st의 값이 1 증가한다.
- 2번과 3번을 en이 배열의 마지막을 넘어설 때 까지 반복한다.
그림을 통해 살펴보자.
st와 en으로 배열의 시작을 가르킨다. 최솟값을 무한대로 설정하고 차이 M을 임의로 3으로 설정했다.
A[en] - A[st] = 0 < M이므로 en을 증가시킨다.
A[en] - A[st] = 2 < M이므로 en을 증가시킨다.
A[en] - A[st] = 6 > M 이고 INF보다 작으므로 최솟값을 갱신한다. 여기서 중요한점은 en을 증가시킬 필요가 없다. st를 1 증가시킨다.
A[en] - A[st] = 4 > M이고 기존의 최솟값인 6보다 작으므로 최솟값을 갱신한다. st를 1 증가시킨다.
A[en] - A[st] = 0 < M이므로 en을 증가시킨다.
A[en] - A[st] = 3으로 M이상이여야 하는 조건에 만족한다. 기존의 최솟값인 4보다 작으므로 최솟값을 갱신한다. 사실상 정답은 찾았지만 계속 진행해보자. st를 1 증가시킨다.
A[en] - A[st] = 0 < M이므로 en을 증가시킨다.
A[en] - A[st] = 2 < M이므로 en을 증가시킨다.
이 때 en이 배열의 범위를 넘어가서 더이상 어떠한 것도 가르키지 않으므로 알고리즘이 끝나게 된다.
구현 코드
#include <bits/stdc++.h>
using namespace std;
long A[100001];
int main()
{
int n,m;
cin >> n >> m;
for(int i=0; i<n; i++)
cin >> A[i];
sort(A,A+n);
long Min=2000000001;
int en=0;
for(int st=0; st<n; st++)
{
//A[en]-A[st]가 M이상이 될 때 까지 en을 증가시킨다
while(A[en]-A[st] < m && en < n )
en++;
//en이 배열크기를 넘어서면 반복문을 종료한다.
if(en==n)
break;
Min=min(Min,A[en]-A[st]);
}
cout << Min;
}위 과정을 잘 이해했다면 코드도 쉽게 이해할 수 있을 것이다.
en의 범위를 잘 신경써서 구현하는 것이 중요하다.
투 포인터 관련 문제
백준 13144 List Of Unique Numbers / 난이도: 골드4
13144 List Of Unique Numbers 문제풀이
백준 1806 부분합 / 난이도: 골드4
1806 부분합 문제풀이
