파이썬 투포인터 알고리즘 사용하기(Two pointer)

투포인터 알고리즘?

 

투포인터 알고리즘은 이름에서 알 수 있듯 2개의 포인터를 사용하는 알고리즘이다. 슬라이딩 윈도우 알고리즘과도 많이 비교가 되는데, 그 이유는 밑에서 설명하겠다. 투포인터 알고리즘은 배열의 인덱스를 가르키는 2개의 포인터를 설정하고, 이를 옮겨가면서 내가 원하는 값을 찾는 알고리즘이다.

 

투포인터는 간단하기도 해서 그냥 바로 예시 상황을 보고 이해하는게 빠를 것이다.

 

상황

1. 길이가 5인 배열이 하나 있다. 이 안에는 임의의 10미만의 정수가 할당되어있다.

2. 이 배열에서 어느 한 부분을 잘라서 그 부분의 합이 15가 되는 부분을 찾고 출력하라.

1 4

2 5

3 6

 

순서로 보시면 된다.

(S = 보라색포인터와 파란색포인터 사이의 값의 합)

 

1. 보라색 포인터와 파란색 포인터가 둘다 0번 인덱스에서 시작한다.

2. S가 15보다 작으므로 파란색 포인터 1 증가.

3. S가 15보다 작으므로 파란색 포인터 1 증가.

4. S가 15보다 작으므로 파란색 포인터 1 증가.

5. S가 15보다 크기 때문에 보라색 포인터 1 증가.

6. S가 15보다 작기 때문에 파란색 포인터 1 증가.

7. S = 15가 되었으므로, 종료.

 

코드

 

array = [4,6,-2,9,2,-5]

front = 0
rear = 0

target = 15

while rear < len(array):
    if sum(array[front:rear]) < target:
        rear += 1
    elif sum(array[front:rear]) > target:
        front += 1
    elif sum(array[front:rear]) == target:
        print(array[front:rear])
        rear += 1

이렇게 코드를 짤 수가 있는데, 일단 투포인터로서 문제는 없다만 조건문에 들어갈 때 마다 배열의 값을 다 하나하나 더하는 연산이 너무 낭비가 된다. 이럴 땐 누적합(prefix sum)을 사용하면 된다.

누적합을 간단히 설명하면

4

6

-2

9

2

-5

이런 배열이 있으면, 누적합 배열을 하나 더 만든다.

누적합 배열은 각 인덱스가 전 인덱스를 다 더한값을 저장하는 배열이다.

(편의를 위해, 첫번째 인덱스를 0으로 두고 두번째 인덱스부터 시작)

0

4

10

8

17

19

14

그러면 만약에 여기서 sum(array[1:5])를 구하고 싶다면, prefix_sum_array[6] - prefix_sum_array[1]를 하면 당연히 값도 같고, 연산이 훨씬 줄어든다.

array = [4,6,-2,9,2,-5]

def prefix_sum():
    ps_array = []
    for i in range(len(array)):
        if i == 0:
            ps_array.append(array[i])
        else:
            ps_array.append(ps_array[i-1] + array[i])
    return ps_array

ps_array = prefix_sum()

front = 0
rear = 0

target = 15

while rear < len(array):
    if ps_array[rear]-ps_array[front] < target:
        rear += 1
    elif ps_array[rear]-ps_array[front] > target:
        front += 1
    elif ps_array[rear]-ps_array[front] == target:
        print(array[front+1:rear+1])
        rear += 1

 

슬라이딩 윈도우

 

슬라이딩 윈도우 알고리즘은 위에서 설명한 투포인터와 매우 흡사하다. 하지만 차이점이라면 슬라이딩 윈도우는 투포인터의 간격이 일정하게 움직인다.