1. 슬라이딩 윈도우 알고리즘이란?
윈도우(특정범위)가 있을때 배열이나 내부 요소의 값을 윈도우로 이동하며 해결하는 알고리즘이다
1. 위의 파란색 범위를 윈도우라고 한다.
2. 윈도우를 이동을 하며 배열을 탐색한다.
2. 배열에서 연속하는 요소들을 연산하려고 할때
쉽게 중첩된 for loop를 이용해서 구하기 쉬운데
O(n^2)을 가지게 되어 효율성에서 많이 문제가 생긴다.
3. 이럴때 슬라이딩 윈도우 알고리즘을 이용한다
배열이나 문자열같은 선형구조에서 일정범위값이 있을때
// 예 ) 배열이 있을때 배열에서 연속하는 5개 요소의 합중 최대값을 리턴한다.
// [1, 3, 2, 9, 0, 1, 2, 5, 7, 8, 3]연속하는 5개의 요소를 이동하며 합을 구하게 된다.
[1, 3, 2, 9, 0, 1, 2, 5, 7, 8, 3] -> 15
[1, 3, 2, 9, 0, 1, 2, 5, 7, 8, 3] -> 15
[1, 3, 2, 9, 0, 1, 2, 5, 7, 8, 3] -> 14
[1, 3, 2, 9, 0, 1, 2, 5, 7, 8, 3] -> 17
[1, 3, 2, 9, 0, 1, 2, 5, 7, 8, 3] -> 15
[1, 3, 2, 9, 0, 1, 2, 5, 7, 8, 3] -> 23
[1, 3, 2, 9, 0, 1, 2, 5, 7, 8, 3] -> 25
이렇게 범위를 이동하며 하나씩 더해나가서 최대값인 25를 구할 수 있지만
배열의 수가 10281928409284가 된다면 하나씩 계산할 수 없게 된다.
이럴때 Window를 이동하며 계산을 하게 되는데
[1, 3, 2, 9, 0, 1, 2, 5, 7, 8, 3]
[1, 3, 2, 9, 0, 1, 2, 5, 7, 8, 3]
↓window이동↓
합에서 window의 첫번째 index 값을 빼주고
새롭게 이동해서 window의 마지막 index값을 더해주면 된다
[1, 3, 2, 9, 0, 1, 2, 5, 7, 8, 3]
[1, 3, 2, 9, 0, 1, 2, 5, 7, 8, 3]
↓window이동↓
합에서 window의 첫번째 index 값을 빼주고
새롭게 이동해서 window의 마지막 index값을 더해주면 된다
[1, 3, 2, 9, 0, 1, 2, 5, 7, 8, 3]
... 반복해서 최대값을 구하면 된다!
'알고리즘 > 알고리즘' 카테고리의 다른 글
| Two Pointer | 투포인터 알고리즘 (0) | 2023.02.09 |
|---|---|
| Anagram | 아나그램 알고리즘 (0) | 2023.02.09 |