[알고리즘] Sliding Window VS Dynamic Programming
포스팅 작성 계기: Sliding Window를 접하기 전, Leetcode Maximum Average Subarray I 문제를 보고 Dynamic Programming 방식과 유사하다고 생각이 들어 비교하게 됨.
슬라이딩 윈도우(Sliding Window)와 동적 프로그래밍(Dynamic Programming, DP)은 문제를 최적화하는 데 사용되는 알고리즘적 접근법이지만, 둘은 문제를 해결하는 방식과 적용되는 상황이 다릅니다.
1. 슬라이딩 윈도우(Sliding Window)
핵심 아이디어
- 고정된 크기 또는 가변 크기의 연속된 범위(윈도우)를 사용하여 문제를 해결.
- 윈도우 범위를 한 번에 하나씩 이동하며 중복 계산을 줄임.
적용 문제 유형
- 배열이나 문자열에서 연속된 요소를 다룰 때 사용.
- 연속된 부분 배열/부분 문자열의 최대값, 최소값, 평균, 합 등을 찾는 문제.
특징
- 로컬 계산: 현재 윈도우의 값을 기반으로 다음 상태를 효율적으로 계산.
- 메모리 사용량이 적음(O(1) 또는 O(k), 윈도우 크기와 비례).
- 시간 복잡도는 보통 O(n) (한 번의 순회로 해결).
예제: Maximum Average Subarray I
- 목표: 길이
k의 연속된 부분 배열의 평균 중 최대값 찾기. - 슬라이딩 윈도우를 사용하여 한 번의 순회로 연속된 합계를 효율적으로 계산.
2. 동적 프로그래밍(Dynamic Programming, DP)
핵심 아이디어
- 문제를 더 작은 하위 문제로 분할하고, 하위 문제의 결과를 저장(메모이제이션)하거나 재사용(탑다운 또는 보텀업 방식)하여 중복 계산을 줄임.
적용 문제 유형
- 최적 부분 구조(Optimal Substructure): 큰 문제를 작은 문제로 분할할 수 있는 경우.
- 중복되는 하위 문제(Overlapping Subproblems): 동일한 하위 문제를 여러 번 계산하는 경우.
특징
- 전역 최적화: 현재 상태는 이전 상태들(또는 하위 문제들)의 최적 결과를 기반으로 결정.
- 메모리를 많이 사용할 수 있음(O(n) 이상, 결과를 저장하는 테이블 크기와 비례).
- 시간 복잡도는 문제에 따라 O(n), O(n^2), O(n*m) 등 다양.
예제: Climbing Stairs
- 목표: 계단을 오르는 방법의 총 개수 계산.
- DP 방식을 사용해
dp[i] = dp[i-1] + dp[i-2]로 풀이:- 현재 계단까지 가는 방법은 한 계단 전에서 오는 방법과 두 계단 전에서 오는 방법의 합.
3. 주요 차이점 비교
| 특성 | 슬라이딩 윈도우 | 동적 프로그래밍 |
|---|---|---|
| 문제 구조 | 연속된 데이터 처리 (배열/문자열에서 윈도우 이동). | 하위 문제의 최적해를 재활용 (최적 부분 구조). |
| 사용 목적 | 연속적인 범위의 값에서 최적화된 계산 수행. | 복잡한 문제를 작은 하위 문제로 나눠 최적해 찾기. |
| 적용 사례 | 최대/최소 합, 평균, 길이 등 연속된 데이터의 최적화 문제. | 계단 오르기, 배낭 문제, 문자열 유사성 등 다양한 문제. |
| 계산 방식 | 현재 상태를 이전 윈도우 값으로 효율적으로 갱신. | 하위 문제의 결과를 저장하고 재사용. |
| 시간 복잡도 | O(n) (대체로 한 번의 순회로 해결 가능). | 문제에 따라 다양 (O(n), O(n^2), O(n*m) 등). |
| 공간 복잡도 | O(1) 또는 O(k) (윈도우 크기에 비례). | O(n) 이상 (DP 테이블 크기에 비례). |
4. 공통점
- 둘 다 중복 계산을 피하고 효율성을 높이기 위한 알고리즘.
- 문제를 "현재 상태와 과거 상태"의 관계로 정의.
5. 정리
- 슬라이딩 윈도우는 연속된 범위를 다루는 문제에 적합하며, 제한된 크기의 윈도우에서 계산을 효율적으로 수행합니다.
- 동적 프로그래밍은 최적 부분 구조와 중복되는 하위 문제를 가진 복잡한 문제를 해결하는 데 적합하며, 문제를 작은 단위로 분할하고 저장하여 효율적으로 처리합니다.
한 줄 요약
슬라이딩 윈도우는 "작은 연속된 부분"에 집중하는 효율적인 도구,
동적 프로그래밍은 "복잡한 문제를 작은 하위 문제로 분할"하여 해결하는 전략입니다.
