투 포인터 알고리즘

투포인터 알고리즘

투포인터 (Two Pointers)

 

• 리스트에 순차적으로 접근해야 할 때 두 개의 점의 위치를 기록하면서 처리하는 알고리즘
• 정렬되어 있는 두 리스트의 합집합으로도 사용되며, 병합정렬의 기초가 되기도 합니다.

 

투포인터 알고리즘을 활용할수 있는 다음과 같은 문제가 있습니다.

아래의 문제는 두가지 방법으로 풀수 있습니다.

Q. 정렬된 리스트 A와 타겟 값 S가 주어졌을 때, 두 수의 합이 S가 되는 순서쌍을 모두 구하여라.
> A = [1, 3, 5, 6, 9, 11, 12, 16, 17, 19, 22, 25, 28]
> S = 27

 

1. 이중 반복문을 이용한 풀이

가장 먼저 떠오르는 풀이는 이중 반복문을 이용해 모든 쌍을 탐색하며 조건을 만족하는 경우를 찾는 방법입니다.

A = [1, 3, 5, 6, 9, 11, 12, 16, 17, 19, 22, 25, 28]
S = 27 

for i in range(len(A)):
    for j in range(i+1, len(A)):
        if A[i] + A[j] == S:
            print(f'{A[i]} + {A[j]} = {S}')

매우 단순하며 직관적입니다.

하지만 이중 반복문을 이용하는 경우 시간 복잡도는 O(n2)이기 때문에 리스트의 데이터가 커지면 시간초과가 발생할 가능성이 다분합니다.

그렇기 떄문에 투포인터 알고리즘을 사용하는 이유가 여기에 있습니다.

 

2. 투 포인터를 이용한 풀이

투 포인터를 알고리즘은 다음과 같은 방식으로 진행됩니다..

1. 리스트를 오름차순으로 정렬합니다.
2. 포인터 left는 리스트의 시작점을, 포인터 right는 리스트의 끝점을 가리킵니다.
3. left와 right가 만날 때 까지(즉, 모든 경우를 확인할 때 까지) 다음을 반복합니다.
   3-1. A[left]와 A[right]의 합이 타겟 값(S)과 같다면 조건을 만족하므로 출력하고, left를 1 증가, right를 1 감소시킵니다.
   3-2. A[left]와 A[right]의 합이 타겟 값(S)보다 작다면 left를 1 증가시킵니다.
   3-3. A[left]와 A[right]의 합이 타겟 값(S)보다 크다면 right를 1 감소시킵니다.

A = [1, 3, 5, 6, 9, 11, 12, 16, 17, 19, 22, 25, 28]
S = 27 

# A.sort()  # 이미 정렬된 경우에는 필요 없음
left, right = 0, len(A)-1
while left <= right:
    tmp = A[left] + A[right]
    if tmp > S: 
        right -= 1
    elif tmp < S:  
        left += 1
    else: 
    	# 조건 만족
        print(f'{A[left]} + {A[right]} = {S}')
        left += 1
        right -= 1

투 포인터를 활용하면 리스트를 한 번만 탐색하기 때문에, 리스트가 이미 정렬되어 있는 경우 O(n), 정렬되어 있지 않더라도 O(nlogn) 정도의 시간 복잡도로 문제를 해결할 수 있습니다.

 

예제 문제 - 특정한 합을 가지는 부분 연속 수열 찾기

 

투포인터 알고리즘의 대표적인 문제입니다.

 

어떤 숫자들의 리스트가 주어질 때, 해당 리스트의 연속 수열의 합이 특정 값을 가지는 것을 확인하는 문제입니다.

1. 시작점과 끝점이 첫번째 원소의 인덱스를 가리키도록 한다.
2. 현재 부분 합이 M과 같다면 카운트한다.
3. 현재 부분 합이 M보다 작다면 end를 1 증가시킨다.
4. 현재 부분 합이 M보다 크거나 같다면 start를 1 증가시킨다.
5. 모든 경우를 확인할 때까지 2-4번 과정을 반복한다.

위와 같은 리스트와 M=5M=5 일 때의 예시를 생각해봅시다.

• [초기 단계] : 시작점과 끝점이 첫번째 원소의 인덱스를 가리키도록 합니다.

• • 현재의 부분 합은 1.
  • 현재 카운트 : 0
• [Step 1] : 이전 단계에서의 부분합이 1 -> end를 증가시킵니다.

• • 현재의 부분 합 : 3
  • 현재 카운트 : 0
• [Step 2] : 부분합이 3 -> end를 증가시킵니다.

• • 현재의 부분 합 : 6
  • 현재 카운트 : 0
• [Step 3] : 부분합 6 -> start를 1 증가시킵니다.

• • 현재의 부분 합 : 5
  • 현재 카운트 : 1 (부분합이 5이기 때문에)
• 이걸 계속 반복

 

[마지막]

• 현재의 부분합 : 5

n = 5 # 데이터의 개수 N
m = 5 # 찾고자하는 부분합 M
 
count = 0
interval_sum = 0
end = 0
 
# start를 차례대로 증가시키며 반복
for start in range(n):
    # end만큼 이동시키기
    while interval_sum < m and end < n:
        interval_sum += data[end]
        end += 1
    # 부분합이 m일 때 카운트 증가
    if interval_sum == m:
        count += 1
    interval_sum -= data[start]
 
print(count)

 

시간복잡도

O(N)

 

매 루프마다 항상 두 포인터 중 하나는 1씩 증가하고 각 포인터가 n번 누적 증가해야 알고리즘이 끝납니다. -> 각각 배열 끝에 다다르는데 O(N)이라 둘을 합해도 여전히 O(N)입니다.

 

슬라이딩 윈도우

투포인터처럼 구간을 훑으면서 지나간다는 공통점이 있으나 슬라이딩 윈도우는 어느 순간에도 구간의 넓이가 동일하다는 차이점이 있습니다.