[알고리즘] 투 포인터와 슬라이딩 윈도우 - 파이썬(python)

이번에는 투 포인터와 슬라이딩 윈도우 알고리즘에 대해서 알아보자

 

투 포인터 알고리즘과 슬라이딩 윈도우 알고리즘은 매우 비슷하다.

두 알고리즘 모두 두 개의 포인터를 가지고 있고 포인터가 지나온 곳은 삭제하고 나아간 곳은 추가하는 방식을 가지고 있어 배열에서 원하는 값을 찾을 때 유용하게 사용된다.

 

다만, 투 포인터는 두 개의 포인터가 유동적으로 움직일 수 있지만, 슬라이딩 윈도우는 두 개의 포인터가 하나의 윈도우를 구성하고 있어 포인터 사이의 구간이 일정하게 고정된채로 움직인다.

그림으로 표현하면 이런 느낌이다.

투 포인터

간단한 투 포인터 예시를 살펴보자

# n개의 자연수 중에서 연속된 숫자의 합이 m이 되는 경우의 수는 몇가지일까?

n,m = 10, 5
arr = [1, 2, 3, 4, 2, 5, 3, 1, 1, 2]
cnt,sum = 0, 0
st, ed = 0, 0

while 1:
    if sum >= m or st == n:  # 합이 m보다 크거나 같다면 범위를 좁히기 
        sum -= arr[ed]       # (다음으로 넘어가기 위해 값이 같은 경우도 범위를 좁힌다.)
        ed += 1              # st==n인 경우 st포인터는 끝에 도달했지만 ed포인터도 끝에 도달해야 종료된다.
    elif sum < m:           # 합이 m보다 작다면 범위를 넓히면서 더하기
        sum += arr[st]
        st += 1
    if sum == m:
        cnt += 1
    if ed == n: break
print(cnt)

이렇게 2개의 포인터 st, ed를 가지고 포인터를 움직이고 합을 더하고 빼주는 것이다.

아직 이해가 부족한 것 같다면 실제 문제를 한 번 풀어보자

1940번: 주몽

백준에서 투 포인터로 분류되는 문제이다.

 

문제는 다음과 같다.

주몽은 철기군을 양성하기 위한 프로젝트에 나섰다. 그래서 야철대장을 통해 철기군이 입을 갑옷을 만들게 하였다. 야철대장은 주몽의 명에 따르기 위하여 연구에 착수하던 중 아래와 같은 사실을 발견하게 되었다.

갑옷을 만드는 재료들은 각각 고유한 번호를 가지고 있다. 갑옷은 두 개의 재료로 만드는데 두 재료의 고유한 번호를 합쳐서 M(1 ≤ M ≤ 10,000,000)이 되면 갑옷이 만들어 지게 된다. 야철대장은 자신이 만들고 있는 재료를 가지고 갑옷을 몇 개나 만들 수 있는지 궁금해졌다. 이러한 궁금증을 풀어 주기 위하여 N(1 ≤ N ≤ 15,000) 개의 재료와 M이 주어졌을 때 몇 개의 갑옷을 만들 수 있는지를 구하는 프로그램을 작성하시오.

 

이 문제는 재료를 두 개 선택하여 합이 M이 되면 갑옷이 만들어지고 총 몇 개의 갑옷을 만들 수 있는지 출력해야 한다. 앞선 예시가 두 개의 포인터 모두 0부터 시작했다면 이번 문제는 정렬된 리스트의 양 끝에 포인터가 위치 하고 있다.

n=int(input())  # 갑옷 재료 개수
m=int(input())  # 갑옷하나 만드는데 필요한 합
lst=list(map(int, input().split())) # 갑옷 재료 번호 입력
# 크기 비교에서 정렬을 사용하면 편리하다.
lst.sort()
st=0
ed=n-1
cnt=0

while st<ed:
    # 시작과 끝의 합이 크다면 합을 감소시켜야 하므로 ed-1
    if lst[st]+lst[ed]>m:
        ed=ed-1
    # 작다면 합을 증가시켜야 하므로 st+1
    elif lst[st]+lst[ed]<m:
        st=st+1
    # 두 개의 합이 m이라면 cnt+1하고 다음으로 넘어가기 위해 st+1
    elif lst[st]+lst[ed]==m:
        cnt+=1
        st+=1
        ed-=1
print(cnt)

투 포인터는 위의 문제들처럼 사용되는 것이 일반적이다.

 

슬라이딩 윈도우

그렇다면 이번에는 슬라이딩 윈도우 알고리즘에 대해 알아보자

슬라이딩 윈도우는 구간합을 구하는 문제에서  자주 사용되는데 직접 한 번 풀어보자

2559번: 수열

이 문제는 가장 기본적인 슬라이딩 윈도우 문제이다.

 

문제는 다음과 같다.

매일 아침 9시에 학교에서 측정한 온도가 어떤 정수의 수열로 주어졌을 때, 연속적인 며칠 동안의 온도의 합이 가장 큰 값을 알아보고자 한다.

예를 들어, 아래와 같이 10일 간의 온도가 주어졌을 때,

3 -2 -4 -9 0 3 7 13 8 -3

모든 연속적인 이틀간의 온도의 합은 아래와 같다.

이때, 온도의 합이 가장 큰 값은 21이다.

또 다른 예로 위와 같은 온도가 주어졌을 때, 모든 연속적인 5일 간의 온도의 합은 아래와 같으며,

이때, 온도의 합이 가장 큰 값은 31이다.

매일 측정한 온도가 정수의 수열로 주어졌을 때, 연속적인 며칠 동안의 온도의 합이 가장 큰 값을 계산하는 프로그램을 작성하시오.

 

이 문제는 정해진 N개의 리스트에서  연속으로 K개를 더했을 때 최대값을 출력해야 한다.

# N:온도측정한 날짜수 K: 연속적 날짜수
N,K=map(int,input().split())
lst=list(map(int, input().split()))
# 첫 K개의 구간합 구하기
summ=sum(lst[:K])
# 최대값은 첫 구간합
mx=summ
# K개의 묶음의 개수만큼 for문 실행하기
for j in range(N-K):
    summ-=lst[j]
    summ+=lst[K+j]
    mx = max(summ, mx)

print(mx)

슬라이딩 윈도우는 위의 코드에서 보이듯이 매번 구간합을 새로 구하는 것이 아니라 윈도우가 움직이면서 연산하기 때문에 매번 구간합을 구하는 것에 비해 훨씬 짧은 시간으로 해결할 수 있다.

 

지금까지 투 포인터와 슬라이딩 윈도우 문제에 대해서 알아보았다. 두 알고리즘은 비슷하지만 투 포인터는 포인터 간의 간격이 자유로운 반면, 슬라이딩 윈도우는 간격이 일정하다는 것을 알아두자.