투 포인터(Two Pointer)란?
2개의 포인터를 사용하여 특정 조건을 만족하는 구간이나 숫자의 쌍을 구하는 알고리즘이다. 주로 정렬된 배열에서 사용된다. 정렬되지 않은 배열이라면 누적합을 이용해 정렬된 배열의 형태로 바꿔 사용할 수 있다.
동작 방식
다음과 같이 정렬된 배열을 생각해보자.
left는 탐색 범위의 시작을 나타내는 왼쪽 포인터이다.
right는 탐색 범위의 끝을 나타내는 오른쪽 포인터이다.
우리가 선택한 구간은 left ~ right이 된다.
right 포인터가 3에 위치한다면, 구간은 1~3이 되며 그때의 sum은 1+2+3이 된다.
만약 문제에서 목표 값 N이 주어진다면, sum과 N을 비교하여 포인터만 움직이면 된다.
투 포인터 이동 원칙
- sum > N: left를 오른쪽으로 이동한다. sum의 값은 작아진다.
- sum < N: right를 오른쪽으로 이동한다. sum의 값은 커진다.
- sum == N: 정답을 찾았다. 계속 탐색하려면 right를 오른쪽으로 이동한다. sum의 값은 커진다.
현재 상태 sum과 목표 N을 비교하면서 목표에 가까워지도록 포인터를 이동한다. 특정 조건을 만족하는 범위를 찾거나, 특정 조건을 만족하는 수의 쌍을 찾는데 유용하다.
시간 복잡도
투 포인터 알고리즘의 시간 복잡도는 일반적으로 O(n)이다. 그 이유는 두 개의 포인터가 배열의 시작과 끝에서 출발하여 각 포인터가 배열을 최대 한 번만 순회하기 때문이다.
(예제) 백준 2018번 "수들의 합5"
문제 정보
- 링크: https://www.acmicpc.net/problem/2018
- 난이도:
실버 5
문제 요약
입력으로 정수 N이 주어진다. N을 몇 개의 연속된 자연수의 합으로 나타내는 가지수를 구해라. 이때, 사용하는 자연수는 N이하여야 한다.
예시1. 입력으로 15가 주어짐
15를 나타내는 방법은 15, 7+8, 4+5+6, 1+2+3+4+5의 4가지가 있다. => 정답 4
예시2. 입력으로 10이 주어짐
10을 나타내는 방법은 10, 1+2+3+4의 2가지가 있다. => 정답 2
문제 풀이
1부터 15까지 자연수가 나열되어있다고 생각해보자. 우리의 목표는 15를 연속된 자연수의 합으로 나타내는 것이다.
left = 1, right = 1
left부터 right까지의 합은 1이다.
목표인 15보다 작으므로 right를 이동한다.
left = 1, right = 2
left부터 right까지의 합은 1+2 = 3이다.
목표인 15보다 작으므로 right를 이동한다.
left = 1, right = 3
left부터 right까지의 합은 1+2+3 = 6이다.
목표인 15보다 작으므로 right를 이동한다.
left = 1, right = 4
left부터 right까지의 합은 1+2+3+4 = 10이다.
목표인 15보다 작으므로 right를 이동한다.
left = 1, right = 5
left부터 right까지의 합은 1+2+3+4+5 = 15이다.
목표값과 동일하므로, 정답의 개수를 +1 시킨다. (누적: 1개)
그리고 right를 이동한다.
left = 1, right = 6
left부터 right까지의 합은 1+2+3+4+5+6 = 21이다.
목표인 15보다 크므로 left를 이동한다.
left = 2, right = 6
left부터 right까지의 합은 2+3+4+5+6 = 20이다.
목표인 15보다 크므로 left를 이동한다.
left = 3, right = 6
left부터 right까지의 합은 3+4+5+6 = 18이다.
목표인 15보다 크므로 left를 이동한다.
left = 4, right = 6
left부터 right까지의 합은 4+5+6 = 15이다.
목표값과 동일하므로, 정답의 개수를 +1 시킨다. (누적: 2개)
그리고 right를 이동한다.
.
.
.
(반복)
그 다음은 어떻게 될까?
right를 이동하면 목표값보다 커지므로 다시 left를 이동할 것이다. 이 과정을 반복하면 두 포인터가 계속 오른쪽으로 움직이게 되며, 다른 정답인 7+8(left=7, right=8), 15(left=15, right=15)을 찾아 정답이 4개가 된다.
풀이 코드
import sys
realine = sys.stdin.readline
N = int(realine())
left = 1 # 왼쪽 포인터
right = 1 # 오른쪽 포인터
sum = 1 # 현재까지의 합
answer_count = 0
while right <= N: # right가 오른쪽 끝에 도달할 때까지 진행
if sum > N:
sum -= left
left += 1
elif sum < N:
right += 1
sum += right
else: # sum == N
answer_count += 1
right += 1
sum += right
print(answer_count)위에서 적었던 투포인터의 이동 법칙을 상기시켜보자.
투 포인터 이동 원칙
sum > N: left를 오른쪽으로 이동한다. sum의 값은 작아진다.
sum < N: right를 오른쪽으로 이동한다. sum의 값은 커진다.
sum == N: 정답을 찾았다. 계속 탐색하려면 right를 오른쪽으로 이동한다. sum의 값은 커진다.
1번 케이스) sum > N
if sum > N:
sum -= left
left += 1sum이 N보다 큰 경우를 생각해보자.
left=1, right=6일 때, sum = 1+2+3+4+5+6 = 21이다.
목표한 값보다 크므로 left를 오른쪽으로 이동하고, sum에서 1을 빼고 싶다.
sum에서 1을 빼기 위해서는 sum에서 left를 먼저 뺀 후(sum -= 1), left를 이동시켜야 한다.(left=2)
2번 케이스) sum < N
elif sum < N:
right += 1
sum += rightsum이 N보다 작은! 경우를 생각해보자.
left=1, right=3일 때, sum = 1+2+3 = 6이다.
목표한 값보다 작으므로 right를 오른쪽으로 이동하고, sum에 4를 더하고 싶다.
sum에 4를 더하기 위해서는 right를 4로 먼저 이동시킨 후(right=4), sum에 더해야 한다.(sum += 4)
3번 케이스) sum == N
else: # sum == N
answer_count += 1
right += 1
sum += right
left=4, right=6일 때, sum = 4+5+6 = 15이다.
목표한 값과 동일하므로 정답 개수를 1 늘린다.
정답이 1개였다면 반복문을 종료했겠지만, N을 만드는 연속된 자연수의 합은 여러 개일수 있으므로 탐색을 계속한다.
right를 7로 이동시킨 뒤, sum에 right를 더한다.
(그러면 sum이 N보다 커지므로 그 다음엔 left가 이동하고, 위의 과정이 반복될 것이다.)
정리
투 포인터는 언제 쓰는가?
정렬된 배열에서의 특정 조건을 만족하는 요소 쌍이나 부분 배열을 찾는 데 자주 사용된다. 정렬된 배열의 특성을 이용하여 두 포인터를 배열의 왼쪽에서 시작하거나 양 끝에서 시작함으로써 문제를 해결할 수 있다.
투 포인터가 양쪽 끝에서 시작하는 경우?
left는 배열의 가장 왼쪽에, right는 배열에 가장 오른쪽에 위치시켜 합이 목표 값보다 작으면 왼쪽 포인터를 오른쪽으로 이동시키고, 크면 오른쪽 포인터를 왼쪽으로 이동시키는 방법
누적합과의 조합
투 포인터 알고리즘은 누적합(prefix sum)과 함께 쓰이기도 한다.
위의 예제처럼 풀기 위해서는 배열이 정렬되어있어야 한다.
마구잡이인 배열에서 특정 합을 갖는 부분 배열을 구해야 한다면 누적합을 이용할 수 있다.
각 인덱스까지의 합을 미리 구해 놓고, 두 포인터를 사용하여 누적합의 차이가 특정 값을 만족하는 부분 배열을 찾으면 된다.
슬라이딩 윈도우와의 차이점
슬라이딩 윈도우는 고정 길이를 갖는다. 예를 들어 가로 길이가 5라고 고정되어 있어서 한쪽의 포인터가 움직이면 다른쪽의 포인터도 움직인다.
가변 길이의 슬라이딩 윈도우가 투포인터라고 생각하면 될 것 같다.
참고자료
<Do it! 알고리즘 코딩 테스트 - 자바 편>
[ktb-algorithm-study] 2주차
