자료구조와 알고리즘 - 투 포인터(Two Pointer)

 

 

---

 

 

1. 투포인터란

 

 투 포인터 알고리즘(Two Pointer Algorithm)은 배열이나 리스트에서 두 개의 포인터를 사용하여 원하는 결과를 얻는 데에 활용되는 알고리즘이다. 주로 정렬된 배열이나 리스트에서 부분합, 특정 합 등을 구하는 데에 활용된다. 

 

 

 

위 그림처럼 투 포인터는 배열에서 두 인덱스를 가리키는 포인터를 정의하고, 이 포인터를 조건에 맞게 이동시켜 배열을 효율적으로 탐색하여 원하는 결과를 찾는 알고리즘이다.

 

 

 

 

 예를 들어 배열에서 두 개의 인덱스를 선택하여 두 인덱스 사이의 연속된 숫자의 합이 5가 되는 경우의 수를 구한다고 하자.

 

선택한 인덱스가 0,0이면 List[0]

선택한 인덱스가 0,1이면 List[0] + List[1]

선택한 인덱스가 0,2이면 List[0] + List[1] + List[2]

선택한 인덱스가 1,2이면 List[1] + List[2]

선택한 인덱스가 n,m이면 List[n] + List[n+1] + .... + List[m]     (n < m)

 

전체 배열을 탐색하여 찾는다면 시간복잡도는 n^2이 될 것이다.

 

투 포인터는 다음과 같다.

 

 

두 개의 포인터를 이용하여 배열을 한번만 탐색하므로 시간복잡도는 n이 된다.

 

 

 투 포인터는 배열에서 두 인덱스를 가리키는 포인터를 조작하며, 포인터 이동 시 어떤 의미를 부여하고 어떤 포인터를 어떻게 옮길 것인지를 정의하는 것이 핵심이다. 즉, 투 포인터 알고리즘은 두 인덱스 간의 상호작용을 통해 배열을 효과적으로 탐색하고 원하는 조건을 충족시키는 방식을 설계하는 것에 중점이 있다.

 예를 들어 위 사례에서 Left포인터를 옮기는 것은 합의 숫자 작아지고 Right포인터를 옮기는 것은 합의 숫자가 커진다는 것을 전제로 문제를 푼 것이다. 

 

 

 

2. 예시 문제

1)

 

https://www.acmicpc.net/problem/2003

2003번: 수들의 합 2

 

import sys

input = sys.stdin.readline

n,m = [int(i) for i in input().split()]

lst = [int(i) for i in input().split()]

start = 0
end = 0
sum_ = lst[0]
cnt = 0

while True:

    if sum_ == m:
        cnt += 1

    if sum_ <= m:
        end += 1
        if end > n-1:
            break
        sum_ += lst[end]

    else:
        sum_ -= lst[start]
        start += 1
    
print(cnt)

 

 

2)

https://www.acmicpc.net/problem/3273

3273번: 두 수의 합

 

 

n = int(input())
arr = [int(i) for i in input().split()]
arr.sort()
target = int(input())

l = 0   
r = n - 1
cnt = 0

while l < r:
    s = arr[l] + arr[r]
    if s == target:
        cnt += 1
        l += 1
    elif s < target:
        l += 1
    else:
        r -= 1


print(cnt)

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

3)

https://leetcode.com/problems/container-with-most-water/description/

Container With Most Water - LeetCode

 

class Solution:
    def maxArea(self, height: List[int]) -> int:
    
        left = 0
        right = len(height) - 1
        result = 0
        while True:

            
            left_v = height[left]
            right_v = height[right]

            l = right - left
            
            section = l * min(left_v, right_v)
            
            result = max(result, section)
            
            if left_v <= right_v:

                left += 1

            else:

                right -= 1

            if left == right:
                break

        return result

 

 

위 문제는 투 포인터를 응용해서 풀 수 있다. 이때 두 개의 포인터를 양 끝에 위치시키고 푼다.

 

이때 while문을 이용하여 포인터를 계속 안쪽으로 이동시킨다.

left, right 중에서 어느 포인터를 이동시킬 지를 정의한다. 두개의 숫자 중에서 숫자가 작은 숫자인 포인터를 안쪽으로 움직여야 한다. 이유는 숫자가 작은 값을 안쪽으로 이동시켜야 높이가 커질 가능성이 높기 때문이다.( 너비는 포인터가 안쪽으로 이동하므로 무조건 작아진다.)