🗂️ 2024.08.16 TIL

Python

1. 슬라이딩 윈도우 기법

   슬라이딩 윈도우 기법(Sliding Window Technique)은 연속적인 부분 배열(subarray)이나 부분 문자열(substring)을 효율적으로 다루기 위한 알고리즘 기법입니다. 이 기법은 배열 또는 문자열에서 일정한 크기의 윈도우를 이동시키면서 원하는 결과를 빠르게 계산하는 데 사용.

   ✅ 슬라이딩 윈도우 기법의 핵심 아이디어

   • 윈도우 설정:
     • 고정 크기 윈도우 (Fixed-size Window): 윈도우의 크기가 고정되어 있으며, 이를 배열이나 문자열의 부분 구간으로 생각할 수 있다.
     • 가변 크기 윈도우 (Variable-size Window): 윈도우의 크기가 변동하며, 문제에 따라 윈도우의 크기를 조정하면서 최적의 결과를 찾는다.
   • 윈도우 이동:
     • 윈도우를 배열 또는 문자열 위에서 한 단계씩 이동시키며, 매번 윈도우 내부의 값을 계산하거나 갱신.
     • 윈도우의 이동에 따라 내부 값을 갱신하는 방식으로 시간 복잡도를 줄일 수 있다.
   • 효율적인 계산:
     • 슬라이딩 윈도우 기법은 배열이나 문자열을 반복적으로 순회하면서 매번 $O(1)$ 시간에 윈도우의 계산을 수행할 수 있어, 전체 알고리즘의 시간 복잡도를 $O(n)$으로 줄일 수 있다.

   예문: https://velog.io/@ehdtkd98/프로그래머스-할인행사-파이썬