개요
알고리즘 문제를 풀어내다 보면 간혼 투 포인터 알고리즘이라는 단어를 접할 때가 있다. 배열을 순회할 때 사용하는 것 같은데, 이번 글에서는 투 포인터 알고리즘에 대한 개념을 알아본다
투 포인터 알고리즘
1차원 배열에서 각자 다른 원소를 가리키고 있는 2개의 포인터를 조작해 가면서 원하는 값을 찾을 때까지 탐색하는 알고리즘으로, 보다 쉽게 표현하면 리스트에 순차적으로 접근할 때 두 점의 위치를 기록하면서 처리하는 알고리즘이라고 할 수 있다.
특정 조건을 만족하는 부분 구간을 효율적으로 탐색할 수 있기 때문에 이중 for문으로 처리해 시간복잡도가 O(N^2)인 작업을 O(N)으로 줄일 수 있다. 일반적으로 배열이나 리스트가 정렬되어 있을 때 사용한다.
구현 방식
일반적으로 투 포인터 알고리즘은 다음과 같이 구현한다.
- 두 점을 가리키는 포인터를 선언한다. 일반적으로 변수명은 left, right 또는 start, end 등으로 명명한다.
- 일반적으로 최초 실행 시 두 점은 배열의 첫 번째 원소를 가리킨다. 두 포인터의 관계는 start <= end이다. 경우에 따라서는 양 끝 값을 가리킬 수도 있다.
- 두 포인터는 부분 배열의 시작과 끝을 가리킨다.
- 두 포인터 사이의 구간을 조사하고 조건을 확인한다.
- 조건을 만족하면 알고리즘을 종료하고, 만족하지 않으면 첫 번째 또는 두 번째 포인터를 이동시킨다.
예시 - 특정 합을 가지는 부분 연속 수열 찾기
예시로 N개의 자연수로 구성된 수열이 있을 대 합이 M인 부분 연속 수열의 개수를 구해보자.
먼저 start, end가 첫 번째 원소의 인덱스를 가리키게 한다.
start, end가 0일 때의 부분합은 1이므로 end를 1 증가시킨다.
start가 0이고 end가 1일 때의 부분합은 3이므로 end를 1 증가시킨다.
start가 0이고 end가 2일 때의 부분합은 6이므로 start를 1 증가시킨다.
start가 1이고 end가 2일 때의 부분합은 5이므로 조건에 맞는다. 부분 수열의 개수를 뜻하는 count를 1 증가시키고, start를 1 증가시킨다.
start, end가 3일 때의 부분합은 3이므로 end를 1 증가시킨다.
위 과정을 start가 리스트의 오른쪽 끝에 다다를 때까지 반복하면 된다.
Python 코드로 표현하면 아래와 같다.
list_num = [1, 2, 3, 2, 5]
M = 5
count = 0 # 부분 수열의 개수
start, end = 0, 0
while start < len(list_num): # start가 리스트 끝에 닿을 때까지 반복
subtotal = 0 # 부분합
for i in range(start, end + 1):
subtotal += list_num[i]
if subtotal == M: # 부분합이 조건에 맞으면
count += 1
start += 1
elif subtotal < M: # 부분합이 조건보다 작으면
end += 1
elif subtotal > M: # 부분합이 조건보다 크면
start += 1
참고 문서
[Algorithm] Two-Pointers Algorithm (투 포인터 알고리즘)
[Java/알고리즘] 투 포인터 알고리즘(Two Pointer Algorithm) 이해하기 -1 : 종류, 활용방안