[알고리즘] 슬라이딩 윈도우(Sliding window), 투 포인터(Two pointer)

💡슬라이딩 윈도우(Sliding window)란?

슬라이딩 윈도우는 일정한 길이의 범위를 이동하여 조건에 맞는 값을 찾는 알고리즘이다. 한 칸씩 이동 하기 때문에 공통된 부분은 유지하고 처음과 끝 원소만 갱신하여 유용하게 사용할 수 있다.

• 일정 길이 최댓값을 구하는 함수

n,m=map(int,input().split())   # n: 입력받을 정수의 개수, m: 연속된 구간의 크기 (10, 5)
arr=list(map(int,input().split()))

Max,sum=0,0

for i in range(m): # 처음 m개의 구간 (0번 인덱스부터 4번인덱스)의 합 구하기
    sum+=arr[i]

for i in range(n-m+1): 
    if sum>Max:
        Max=sum
    if i==n-m: break
    sum+=arr[i+m] # i+m: 5~10
    sum-=arr[i]   # i: 0~5

print(Max)

• 일정 길이 최솟값을 구하는 함수

# 비효율적인 방법
def minArray(nums, k):
    result = sum(nums[0:k])
    for i in range(1, len(nums)-(k-1)):
        r = sum(nums[i:i+k])
        if r < result:
            result = r
    return result

# 슬라이딩 윈도우
def minSlidingWindow(nums, k):
    min_sum = 9999
    window_sum = 0
    start = 0

    for end in range(len(nums)):
        window_sum += nums[end]

        if end >= k - 1:
            # 0~k-1 까지 더한 값이 최소값보다 작다면, 최소값을 갱신
            if window_sum <= min_sum:
                min_sum = window_sum

            # 윈도우에 포함된 맨 앞자리 수를 제거
            window_sum -= nums[start]
            # 윈도우 시작 인덱스를 하나 증가
            start += 1
    return min_sum

💡투 포인터(Two pointer)란?

투 포인터는 데이터에 순차적으로 접근해야 할 때 두 개의 점 위치를 조절하여 조건에 부합하는지 판단하는 알고리즘이다. 공통 부분을 제외하고 포인터로 이동하는 원소의 처리만 하면 되므로 유용하게 쓰일 수 있다.

• 특정한 합을 가지는 부분 연속 수열의 개수를 구하는 알고리즘

n, target = map(int,input().split())
arr = list(map(int,input().split()))

cnt, sum = 0, 0
high, low = 0, 0
while(1):
    if sum > target:        # 합이 타겟보다 크면
        sum -= arr[low]     # sum에서 뺴고
        low += 1            # low 의 index를 1증가
    elif high == n: break
    else:
        sum+=arr[high]      # 합이 타겟보다 작거나 같다면
        high+=1             # sum에 더하고 high의 인덱스를 1증가
    if sum==target:
        cnt+=1
print(cnt)

• 백준 2003번, 수들의 합 2

범위가 매우 크기 때문에 2중 포문으로 풀면 런타임 에러가 난다. 그러므로 투 포인터를 활용하여 풀이해야 한다.

# 시간 초과가 나는 코드
def not_tow_pointer(nums):
    count = 0
    for i in range(N):
        for j in range(i, N):
            r = sum(nums[i:j+1])

            if r == M:
                count += 1

    print(count)

# 투포인터
def two_pointer(nums):
    count = 0
    start, end = 0, 0

    window_sum = nums[start]
    while start < N:
        if window_sum == M:
            count += 1
            window_sum -= nums[start]
            start += 1
        elif window_sum < M:
            end += 1
            if end >= N:
                break
            window_sum += nums[end]
        else:
            window_sum -= nums[start]
            start += 1
        print(f'start = {start} / end = {end}')