https://school.programmers.co.kr/learn/courses/30/lessons/178870?language=python3
슬라이딩 윈도우
슬라이딩 윈도우 접근법은 배열 문제를 해결할 때 자주 사용되며, 주로 부분 배열(subarray)을 찾는 문제에 적용됩니다. 이 방식에서는 보통 두 개의 포인터를 사용합니다: 첫 번째 포인터가 시작점(왼쪽 경계)이 되고, 두 번째 포인터가 끝점(오른쪽 경계)이 됩니다. 창문을 옆으로 밀어 이동시키는 것과 비슷한 원리로 동작하기 때문에 '슬라이딩 윈도우'라고 불립니다. 특정 조건을 만족하는 부분 배열(subarray)을 찾아야 할 때 이 접근법을 사용합니다.
왼쪽 경계(left bound)와 오른쪽 경계(right bound)를 정의합니다. 보통 두 경계 모두 0번 인덱스에서 시작합니다. 오른쪽 경계를 점차 늘려가며 조건을 확인합니다. 조건이 맞지 않을 경우, 조건이 맞을 때까지 왼쪽 경계를 오른쪽 경계와 같거나 작은 수 범위 내에서 증가시킵니다. 오른쪽 경계가 배열의 끝에 도달하면, 알고리즘은 대개 종료됩니다.
왼쪽 경계가 오른쪽 경계를 넘어서거나 뒤로 돌아가는 일이 없기 때문에, 복잡도는 O(n)이 됩니다.
def solution(sequence, k):
start = 0
sum = 0
min_length = float('inf')
min_subarray = []
for end in range(len(sequence)):
sum += sequence[end]
# 부분 배열의 합이 k가 될 때까지 start 포인터를 이동
while sum > k:
sum -= sequence[start]
start += 1
# 부분 배열의 합이 정확히 k일 때
if sum == k:
if end - start < min_length:
min_length = end - start
min_subarray = [start, end]
return min_subarray
코드에서는 두 개의 포인터 (start와 end)를 사용하여 윈도우를 관리합니다. end 포인터는 배열을 순회하며 부분 배열의 끝을 나타냅니다. 한편, start 포인터는 부분 배열의 시작을 나타내며, 부분 배열의 합이 k 이상이 되면 이 포인터를 증가시켜 윈도우의 크기를 줄입니다. 이러한 방식으로, 배열을 한 번만 순회하며 원하는 조건을 만족하는 가장 작은 부분 배열을 효율적으로 찾을 수 있습니다.
이 접근법은 특히 합이나 평균과 같은 연속된 데이터의 특성을 기반으로 최적의 부분 배열을 찾아야 할 때 유용합니다.
