[12강] 투 포인터 알고리즘

---

안녕하세요 Gliver 입니다.

이번 글에서는 투 포인터 알고리즘에 대해 알아보겠습니다.

 

목차

1. 투 포인터 알고리즘
2. 실제 문제에서 투 포인터 알고리즘

 

 

1. 투 포인터 알고리즘

투 포인터 알고리즘은 두 개의 포인터(지점)를 이용하는 알고리즘이다.

정의는 간단하지만, 단순히 두 개의 포인터를 이용하는 것만으로 문제가 쉽게 풀리는 경우가 종종 있다.

 

 

투 포인터(Two Pointer) 알고리즘을 어떤 상황에서 사용할 수 있는지와 어떻게 동작하는지 문제를 통해서 살펴보자.

 

[문제] (백준 2003번)
크기가 N인 양의 정수로 이루어진 배열이 있다고 해보자.
이때, 부분 구간의 합이 M인 부분 구간이 몇 개인지 구하여라.
(1 ≤ N ≤ 10,000, 1 ≤ M ≤ 300,000,000) (시간 제한: 1초)

 

 

먼저, 이 문제를 어떻게 풀 수 있을지 5분 정도 생각해보길 바란다.

 

보통은 "투 포인터 알고리즘 글인데 투 포인터로 풀지 뭘 어떻게 풀어?" 라고 생각할 것이다.

맞는 말이다. 하지만 이 문제는 투 포인터 알고리즘으로 풀 수 있지만 더 심플한 방법이 있다.

[이 문제에 있어 가장 심플한 방법을 살펴보자. (브루트 포스 알고리즘)]

문제에 대해서 다시 보도록 하자.

문제에서 우리가 구해야하는 것은 합이 M인 부분 구간의 개수이다.

 

부분 구간의 후보 개수는 $_{N} \mathrm{C} _{2}$ 이고, 이를 하나하나 살펴보는 것은 2중 for문이면 충분하다.

후보의 개수가 $_{N} \mathrm{C} _{2}$인 이유는 인덱스 2개를 뽑으면 작은 수와 큰 수가 각각 부분의 시작점과 끝점에 대응되기 때문임

 

이 방법의 시간 복잡도는 $O(N^2)$이므로 이 방법으로도 문제를 해결할 수 있다!

 

 

 

이 풀이는 시간 제한이 아슬아슬해서 Python3로 제출하면 시간초과가 뜬다!

따라서 백준에 제출할 때는 PyPy3로 제출하도록 하자!

 

 

 

 

 

그런데 말이다. 만약에 N의 범위가 1 ≤ N ≤ 100,000 이라면 어떻게 풀어야 할까?

 

앞에서 살펴 본 $O(N^2)$ 풀이로 풀게 된다면 N = 100,000인 경우 당연히 시간초과가 일어나게 된다.

1초에 약 1억 번 연산할 수 있으므로, N = 100,000인 경우에 약 100억 번 연산을 수행해야 답을 구할 수 있음

 

따라서, 우리는 조금 더 효율적인 풀이를 떠올려야 한다.

[더 효율적으로 살펴보는 방법을 생각해보자. (투 포인터 알고리즘)]

위에서 살펴본 브루트 포스 알고리즘 풀이를 조금만 활용해보자.

브루트 포스 알고리즘 풀이에선 시작점과 끝점의 모든 조합을 살펴보는 풀이를 사용했었다.

 

시작점 하나를 고정해보고 생각해보자.

그 시작점에 대해서 합을 M으로 만드는 끝점은 없거나 유일하지 않은가?

즉, 어떤 시작점을 기준으로 우리가 살펴봐야 할 끝점은 1개라는 것이다!

 

이러한 사고과정을 효율적으로 구현한 것이 투 포인터 알고리즘이라고 할 수 있다.

 

시작점을 $l$, 끝점을 $r$으로 설정하고 투 포인터 알고리즘을 진행하며 $l$을 기준으로 $r$을 살펴보면 된다.

이러한 과정이 두 개의 포인터가 나란히 이동하는 것처럼 보여서 투 포인터 알고리즘이라고 하는 것이다.

하지만, 이러한 과정은 위에서 설명한 사고과정에 기반하여 나와야 한다는 것을 잊지말자.

 

 

아래와 같은 배열에 대해서 투 포인터 알고리즘을 이용하여 답을 구해보자. (N=10, M=5)

 

 

[초기 설정]
답(합이 M인 부분구간의 개수)을 저장하는 변수 res를 0으로 초기화
현재 부분 구간의 합을 저장하는 변수 cur_sum을 0으로 초기화
현재 부분 구간의 끝점을 나타내는 변수 $r$을 -1으로 초기화

[1단계] $\small{l}$ = 0
$\small{l}$=0,  $r$=-1, cur_sum=0, res=0

현재 부분 구간 [0, -1]에서 인덱스가 0인 원소(1)를 추가하면 cur_sum = 0+1 ≤ M(5) 이므로 $r$=0으로 갱신
현재 부분 구간 [0, 0]에서 인덱스가 1인 원소(2)를 추가하면 cur_sum = 1+2 ≤ M(5) 이므로 $r$=1으로 갱신
현재 부분 구간 [0, 1]에서 인덱스가 2인 원소(2)를 추가하면 cur_sum = 3+3 ＞ M(5) 이므로 stop


[2단계] $\small{l}$ = 1
$\small{l}$=1,  $r$=1, cur_sum=2, res=0
$\small{l}$이 1이 되면서 인덱스가 0인 원소를 빼줘야 하므로 cur_sum = 3-1 = 2로 시작

현재 부분 구간 [1, 1]에서 인덱스가 2인 원소(3)를 추가하면 cur_sum = 2+3 = M(5) 이므로 $r$=2으로 갱신, res += 1
현재 부분 구간 [1, 2]에서 인덱스가 3인 원소(4)를 추가하면 cur_sum = 5+4 ＞M(5) 이므로 stop


[3단계] $\small{l}$ = 2
$\small{l}$=2,  $r$=2, cur_sum=3, res=1
$\small{l}$이 2가 되면서 인덱수가 1인 원소를 빼줘야 하므로 cur_sum = 5-2 = 3로 시작

현재 부분 구간 [2, 2]에서 인덱스가 3인 원소(4)를 추가하면 cur_sum = 3+4 ＞M(5) 이므로 stop


[4단계] $\small{l}$ = 3
$\small{l}$=3,  $r$=2, cur_sum=0, res=1
$\small{l}$이 3이 되면서 인덱스가 2인 원소를 빼줘야 하므로 cur_sum = 3-3 = 0로 시작

현재 부분 구간 [3, 2]에서 인덱스가 3인 원소(4)를 추가하면 cur_sum = 0+4 ≤ M(5)이므로 $r$=3으로 갱신
현재 부분 구간 [3, 3]에서인덱스가 4인 원소(2)를 추가하면 cur_sum = 4+2 > M(5)이므로 stop


ㆍㆍㆍ


[6단계] $\small{l}$ = 5
$\small{l}$=5,  $r$=4, cur_sum=0, res=1
$\small{l}$이 5가 되면서 인덱스가 4인 원소를 빼줘야 하므로 cur_sum = 2-2 = 0로 시작

현재 부분 구간 [5, 4]에서 인덱스가 5인 원소(5)를 추가하면 cur_sum = 0+5 = M(5) 이므로 $r$=2으로 갱신, res += 1
현재 부분 구간 [5, 5]에서 인덱스가 6인 원소(3)를 추가하면 cur_sum = 5+3 > M(5)이므로 stop


[7단계] $\small{l}$ = 6
$\small{l}$=6,  $r$=5, cur_sum=0, res=2
$\small{l}$이 6이 되면서 인덱스가 5인 원소를 빼줘야 하므로 cur_sum = 5-5 = 0로 시작

현재 부분 구간 [6, 5]에서 인덱스가 6인 원소(3)를 추가하면 cur_sum = 0+3 ≤ M(5) 이므로 $r$=6으로 갱신
현재 부분 구간 [6, 6]에서 인덱스가 7인 원소(1)를 추가하면 cur_sum = 3+1 ≤ M(5) 이므로 $r$=7으로 갱신
현재 부분 구간 [6, 7]에서 인덱스가 8인 원소(1)를 추가하면 cur_sum = 4+1 = M(5) 이므로 $r$=8으로 갱신, res += 1
현재 부분 구간 [6, 8]에서 인덱스가 9인 원소(2)를 추가하면 cur_sum = 5+2 ＞ M(5) 이므로 stop


[8단계] $\small{l}$ = 7
$\small{l}$=7,  $r$=8, cur_sum=2, res=3
$\small{l}$이 7이 되면서 인덱스가 6인 원소를 빼줘야 하므로 cur_sum = 5-3 = 2로 시작

현재 부분 구간 [7, 8]에서 인덱스가 9인 원소(2)를 추가하면 cur_sum = 2+2 ≤ M(5) 이므로 $r$=9으로 갱신
$r$이 배열의 배열의 끝까지 도달하였으므로 종료!

따라서, 우리는 배열에서 부분 구간의 합이 M(5)인 부분 구간은 res(3)개라는 것을 알 수 있다.

 

이 풀이는 $\small{l}$과 $r$이 배열의 크기만큼 이동하므로 시간 복잡도는 $O(N)$이다.

따라서, N의 범위가 1 ≤ N ≤ 100,000인 경우에도 사용할 수 있는 풀이라고 할 수 있다.

 

 

 

 

 

 

 

2. 실제 문제에서 투 포인터 알고리즘

실제 문제에서 투 포인터 알고리즘이 어떻게 쓰이는지 살펴보자.

 

투 포인터 알고리즘이라 사용하려면 두 개의 포인터가 하나의 상황을 나타낼 수 있어야 한다.

즉, 선형 배열에서는 부분 배열, 2차원 배열에서는 사각형 모양의 구간이라 할 수 있을 것이다.

 

따라서, 두 개의 포인터가 하나의 상황을 나타낼 수 있는 상황이라면

투 포인터 알고리즘을 이용하여 답의 후보를 조금 더 효율적으로 탐색할 수 있을 것이다.

 

투 포인터 알고리즘은 문제를 푸는 구체적인 방법론이 아닌 상황을 나타내는 말이므로 여러 문제를 풀며 감을 익히도록 하자.

항상 말하지만, 문제를 알고리즘에 대입하지 말고 '문제를 어떻게 하면 풀 수 있을지'로 접근하는 습관을 들이자! 

 

 

[관련 문제]

백준 : 부분합 (1806번)

백준 : 회문 (17609번)

 

 

 

 

---

궁금한 점이나 코멘트는 댓글로 남겨주세요!

 

• 알고리즘 공부법 : https://gliver.tistory.com/6
• 알고리즘 목차: https://gliver.tistory.com/7