파이썬 : 알고리즘 - 슬라이딩 윈도우

Part . 6 슬라이딩 윈도우 슬라이딩 윈도우란?? - 2개의 포인터로 범위를 지정한 다음 범위(window)를 유지한 채로 이동(sliding)하며 문제를 해결하는 알고리즘.

연습문제 1. 최솟값 찾기 백준 온라인 저지 11003번 풀이는 어떻게?

< 문제 분석하기> 1. 일정 범위 안에서 최솟값을 구하는 문제로 슬라이딩 윈도우와 정렬을 사용하면 된다. 2.

윈도위의 크기는 문제에서 최솟값을 구하는 번위가 i-L+1 부터 i까지이므로 L로 생각하면 된다. 3. 일반적으로 정렬은 nlog(n)의 시간 복잡도를 가지므로 이 문제에서는 사용할 수 없다. 4.

O(n)의 시간 복잡도로 해결해야 한다. 5. 슬라이딩 윈도우를 덱(deque)으로 구현하여 정렬효과를 볼 수 있다. 1.

덱에서는 (인덱스, 숫자) 형태의 노드를 클래스로 구현하여 저장한다. 2. 새 노드(3, 2)가 덱에 저장될 때 덱 뒤에서부터 비교를 시작다. (2, 5)는 (3, 2)보다 숫자가 크므로 (2, 5)는 덱에서...