투 포인터, 그림으로 쉽게 이해하기

0. 글이 흘러가는 방향

먼저 개념 설명을 하고, 투 포인터를 활용하는 대표적인 문제 2개를 직접 풀어보며, 개념에 대한 보충을 하겠다.

1. 개념

1차원 배열에 두 개의 포인터를 두고, 두 포인터에 의미를 부여하여 문제를 푸는 기술
배열 안에서 특정 조건의 값을 구하는 문제에서, 일반적으로 시간 복잡도가 O((N^{2}))가 든다면, 투 포인터 기법을 활용하면 시간 복잡도를 O(N)으로 줄일 수 있다. (이유는 활용을 살펴보며 설명하겠다.)

(1) 유형

투 포인터를 운용하는 유형에는 크게 2가지가 있다.

a.단방향 운용

L 포인터와 R 포인터가 한쪽 방향으로만 움직이는 것이다. 슬라이딩 윈도우의 양끝을 의미한다고 보면 된다. 슬라이딩 윈도우와 다른 점은 포인터에 따라 구간의 길이가 가변적이라는 것이다.

b. 양방향 운용

두 개의 포인터를 서로 마주보고 최종적으로 만나도록 포인터를 운용하는 방법이다.

2. 활용

(1) 수들의 합2( 백준 2003 )

문제 링크

위에서 보는 단방향 운용으로 문제를 풀면된다.

구간 내의 합을 S, target 합을 M이라고 할 때,
S < M: S가 커져야 함으로, R을 움직인다. (구간 내의 합 커지도록)
S >= M: S가 작아져야함으로, L을 움직인다. 만약 S==M이면 답이 될 수 있는 구간임으로 ans_cnt를 +1 올린다.

만약 해당 문제를 완전탐색으로 푼다면? :thinking:

완전탐색으로 푼다는 것은 L과 R이 수평적 관계가 아닌 수직적 관계가 된다는 의미이다.

L을 먼저 고르고, R을 나중에 골라서 그 구간 내의 합을 구해야 한다. L을 고르는 횟수는 O(N), R은 L 포인터가 가리키는 값보다 큰 값 중에서 골라야함으로 평균 O(N/2)의 계산횟수가 들 것이다. L을 고를 때마다, R을 다시 골라줘야 함으로, 이 둘은 연속적이다. 따라서 O(N * N/2) 이여서, 최악의 시간 복잡도는 O(\(N^{2}\))가 될 것이다.

반면, 투 포인터를 활용한다면, L과 R 포인터는 수평적 관계이다. L을 움직인다고 해서 필연적으로 R을 움직이지 않는다. 그 반대도 마찬가지다. 둘의 관계는 비연속적이고, 최악의 상황을 가정해도, L을 N번 움직이고, R을 N번 움직이는 2N번의 계산만 하면 된다. 따라서 최악의 시간복잡도는 O(N)이다.

(2) 두 용액

문제 링크

문제의 요구사항은 용액의 고유 값이 오름차순으로 이루어져 있고, 이 중에서 2개의 용액을 뽑아 고유 값을 합해서 0에 가장 가까운 경우를 구하는 것이다. 해당 문제는 양방향 운용이 필요한 문제이다. 이유는 음수 값이 입력에 포함되기 때문이다.

단방향으로 풀어보면 어떨까? 위의 수들의 합 문제를 풀듯이,

• 두 용액의 합 < 0이면 R 포인터를 움직인다.
• 두 용액의 합 >= 0이면 L 포인터를 움직인다.

라고 가정해보자.

끝까지 R포인터만 움직임으로 답을 구할 수 없다. 해당 예시에서는 0이 나오도록 두 용액을 고르는 경우의 수가 많은데도 불구하고 말이다. 반면 투 포인터를 양방향에서 운용한다면 더 쉽게 모든 경우의 수를 찾을 수 있다.

• 두 용액의 합 < 0: L 포인터를 오른쪽으로 이동
• 두 용액의 합 >= 0: R포인터를 왼쪽으로 이동