Two Pointers 투포인터 알고리즘 (연속합 구하기)

투포인터 알고리즘이란

주어진 배열에서 연속합을 이용한 문제일때 사용할 수 있는 알고리즘.

보통 연속합으로 가능한 경우의 수를 구하거나, 그 길이를 구하거나 할때 사용된다. (대표문제 참고)

 

start, end라는 변수를 배열의 인덱스로 사용하며 sum(arr[start:end])을 구하는 방법이다.

처음에 start = end = 0으로 시작하고, start <= end여야한다.

(코드에서는 end를 1로 초기화하고, end앞까지만 포함되도록 짰다. -> arr[start:end])

 

예를들어 배열의 연속합이 S가 되는 경우의 수를 구하는 문제에서는 

무한루프를 돌며

sum이 S보다 작은 경우: sum += arr[++end]

sum이 S와 같거나 클 경우: sum -= arr[start++] 를 해준 후,

무한루프는 start == end == len(arr)이 되면 빠져나온다. 

 

https://emre.me/coding-patterns/two-pointers/

저장할때는 파이썬의 sum()을 사용하지 않고 sum이라는 변수 하나로 저장하기 때문에 시간복잡도는 O(N)이다.

 

 

파이썬 코드

# 두개의 포인터 역할을 할 인덱스값들
start = 0
end = 1

# 경우의수를 카운팅해줄 변수
count = 0

# sum(arr[start:end])를 정수형 변수 하나로 저장 (시간을 낮추기 위함)
sum = arr[start]
if sum == S:
    count += 1

while not (start == end == len(arr)):
    if sum < S and end < len(arr):
        sum += arr[end]
        end += 1
    else:
        sum -= arr[start]
        start += 1

    if sum == S:
        count += 1

print(count)

 

 

 

대표 문제 

#2003(yuuj.tistory.com/160), #1806(yuuj.tistory.com/161), #1644(yuuj.tistory.com/162) 순으로 풀면 좋다. 

2003번: 수들의 합 2

1806번: 부분합

1644번: 소수의 연속합

 

참고

Coding Patterns: Two Pointers