소개
슬라이딩 윈도우(Sliding Window)란?
슬라이딩 윈도우(Silding Window)는 배열이나 리스트와 같은 자료구조 내에서 일정한 크기의 서브 리스트나 서브 배열을 이동시키며 문제를 해결하는 기법이다. 이 방법은 연속적인 데이터 구간을 효율적으로 처리할 수 있게 한다.
정의
슬라이딩 윈도우는 고정된 크기의 윈도우(부분 집합)를 자료구조(주로 배열이나 문자열)에 적용하며, 윈도우를 한 칸씩 이동시키며 각 위치에서의 부분 집합을 처리하는 알고리즘 기법이다. 주로 배열의 특정 구간에 대한 합, 평균, 최대/최소 값을 구하거나 문자열의 패턴 매칭 등에 사용된다.
기본 개념
슬라이딩 윈도우의 핵심 개념은 다음과 같다.
- 윈도우 설정 : 초기 윈도우를 설정한다. 이 윈도우는 처리할 데이터의 부분 집합을 나타내며, 고정된 크기를 갖는다.
- 윈도우 처리 : 윈도우 내의 데이터를 처리한다. 처리 방법은 문제에 따라 다르며, 예를 들어 합을 구하거나 최대값을 찾는 작업 등이 있을 수 있다.
- 윈도우 이동 : 윈도우를 한 칸씩 이동시킨다. 이동할 때는 윈도우의 왼쪽 끝 요소를 제거하고, 오른쪽 끝에 새로운 요소를 추가 한다.
이 과정은 전체 배열이나 문자열을 끝까지 처리할 때까지 반복한다. 이를 통해 각 윈도우 위치에서의 결과를 빠르게 계산할 수 있다.
장점
- 효율적인 데이터 처리 : 연속된 데이터 구간을 효율적으로 처리하여 반복적인 계산을 피할 수 있다.
- 최적화된 시간 복잡도 : 많은 문제를 O(n) 시간 복잡도로 해결할 수 있다.
- 단순한 구현 : 구조가 단순하여 코드 작성과 유지보수가 용이하다.
- 다양한 응용 : 배열, 문자열 처리뿐만 아니라 실시간 데이터 스트리밍, 네트워크 트래픽 분석 등 다양한 분야에 적용 할수 있다.
- 메모리 효율성 : 고정된 크기의 윈도우를 사용하여 필요한 데이터만 메모리에 유지 할수 있다.
종류
슬라이딩 윈도우는 다양한 문제를 해결하기 위해 여러 가지 변형된 형태로 사용된다. 주요 슬라이딩 윈도우의 종류는 다음과 같다.
고정 길이 슬라이딩 윈도우
고정된 크기의 윈도우를 일정하게 이동시키며 데이터를 처리한다. 주로 배열이나 문자열의 특정 구간에 대한 합, 평균, 최대/최소 값을 구할 때 사용된다.
고정 길이 슬라이딩 윈도우는 다음과 같이 작동한다.
- 윈도우의 크기를 k로 설정한다.
- 배열의 처음부터 시작하여, k개의 연속된 요소를 선택한다. 이것이 첫 번째 윈도우이다.
- 윈도우의 오른쪽으로 한 칸씩 이동하면서, 새로운 요소를 윈도우에 추가하고 가장 왼쪽의 요소를 제거한다. 이렇게 하면 항상 k개의 요소를 유지할 수 있다.
- 배열의 끝에 도달할 때까지 과정을 반복한다.
이 방법은 윈도우의 크기가 고정되어 있기 때문에, 윈도우 내의 데이터를 빠르게 업데이트하고 계산할 수 있다는 장점이 있다. 하지만 윈도우의 크기를 동적으로 조절해야 하는 경우에는 이 방법을 사용할 수 없다. 이런 경우에는 '가변 길이 슬라이딩 윈도우' 알고리즘을 사용해야 한다.
예시 코드
#include <iostream>
#include <vector>
using namespace std;
vector<int> SlidingWindowSum(const vector::<int>& nums, int k)
{
vector<int> result;
int sum = 0;
for(int i = 0; i < nums.size(); i++)
{
// 윈도우에 요소 추가
sum += nums[i];
// 윈도우 크기가 k를 초과하면 가장 왼쪽의 요소 제거
if(i >= k)
{
sum -= nums[i-k];
}
// 윈도우 크기가 k가 되면 결과에 추가
if(i >= k -1)
{
result.push_back(sum);
}
}
return result;
}
int main()
{
vector<int> nums = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
int k = 3;
vector<int> result = SlidingWindowSum(nums, k);
for(int sum : result)
{
cout << sum << " ";
}
return 0;
}이 코드는 nums라는 배열에서 크기 k의 윈도우를 슬라이딩하면서 윈도우 내의 모든 요소의 합을 계산한다. 계산된 합은 result 벡터에 저장되고, 마지막에 출력된다. 이 코드를 실행하면 nums 배열에서 크기 k의 모든 연속 부분집합의 합을 출력한다.
가변 길이 슬라이딩 윈도우
고정 길이 슬라이딩 윈도우와 비슷하지만, 윈도우의 크기가 고정되어 있지 않고 동적으로 변할수 있다는 점에서 차이가 있다. 이 알고리즘은 주로 조건을 만족하는 연속적인 부분집합을 찾는 문제에 사용된다.
가변 길이 슬라이딩 윈도우는 다음과 같이 작동한다.
- 두 개의 포인터를 설정한다. 하나는 윈도우의 시작점을 가리키는 'start' 포인터이고, 다른 하나는 윈도우의 끝점을 가리키는 'end' 포인터 이다.
- 'end' 포인터를 오른쪽으로 이동시키면서, 윈도우 내의 요소들이 특정 조건을 만족하는지 확인한다.
- 만약, 윈도우 내의 요소들이 조건을 만족하지 않으면, 'start' 포인터를 오른쪽으로 이동시킨다. 이렇게 하면 윈도우의 크기가 줄어든다.
- 이 과정을 배열의 끝에 도달할 때까지 반복한다.
이 알고리즘은 윈도우의 크기를 동적을 조절할 수 있기 때문에, 고정 길이 슬라이딩 윈도우으로 해결할 수 없는 문제를 해결하는 데 사용될 수 있다. 예를 들어, 배열에서 합이 특정 값 이상이 되는 가장 짧은 부분집합을 찾는 문제등에 사용할 수 있다.
하지만, 이 알고리즘은 윈도우의 크기가 동적으로 변하기 때문에, 고정 길이 슬라이딩 윈도우보다 구현이 조금 더 복잡할 수있다. 또한, 윈도우 내의 요소들을 업데이트하는 데 필요한 시간이 윈도우의 크기에 따라 달라질 수 있다.
예시 코드
#incldue <iostream>
#include <vector>
using namespace std;
// 주어진 합을 가진 부분 배열을 찾는 함수
vector<int> FindSubArrayWithGivenSum(vector<int>& arr, int target_sum)
{
int start = 0, end = 0; // 슬라이딩 윈도우의 시작과 끝을 나타내는 변수
int current_sum = arr[0]; // 현재 윈도우의 합
// 배열의 끝까지 반복
while(end < arr.size())
{
// 현재 윈도우의 합이 목표 합과 같으면 해당 부분 배열을 반환
if(current_sum == target_sum)
{
return vector<int>(arr.begin() + start, arr.begin() + end + 1);
}
// 현재 윈도우의 합이 목표 합보다 작거나 시작과 끝이 같은 위치에 있으면 윈도우를 오른쪽으로 확장
if(current_sum < target_sum || start == end)
{
end++;
if(end < arr.size())
{
current_sum += arr[end];
}
}
// 그렇지 않으면 윈도우를 오른쪽으로 축소
else
{
current_sum -= arr[start];
start++;
}
}
// 목표 합을 가진 부분 배열을 찾지 못한 경우 빈 배열을 반환
return vector<int>();
}
int main()
{
vector<int> arr = {1, 2, 3, 7, 5}; // 입력 배열
int target_sum = 12; // 찾고자 하는 합
// 함수 호출
vector<int> result = FindSubArrayWithGivenSum(arr, target_sum);
// 결과 출력
cout << "Subarray with the given sum : ";
for(int num : result)
{
cout << num << " ";
}
reutrn 0;
}이 코드는 주어진 배열에서 주어진 합을 가진 연속적인 부분 배열을 찾는 코드 이다. 이를 위해 슬라이딩 윈도우를 사용하며, 윈도우의 크기는 동적으로 조정된다.
덱을 이용한 슬라이딩 윈도우
덱(Deque, Double-ended Queue)을 사용하여 윈도우 내의 최대값이나 최소값을 빠르게 찾는 알고리즘이다. 덱을 이용하면 윈도우 내의 값들이 정렬된 상태로 유지되어, 최대값이나 최소값을 효율적으로 찾을 수 있다.
덱을 이용한 슬라이딩 윈도우는 다음과 같이 작동한다.
- 새로운 요소가 들어올 때마다 덱의 뒤쪽에서 이 요소보다 작은 모든 요소를 제거한다. 이렇게 하면 덱의 뒤쪽에는 항상 "잠재적인 최대값들" 이 유지된다.
- 새로운 요소를 덱의 뒤쪽에 추가한다.
- 만약 덱의 앞쪽에 있는 요소가 현재 윈도우 범위를 벗어나면 이 요소를 덱에서 제거한다.
- 이제 덱의 앞쪽에 있는 요소가 현재 윈도우의 최대값이 된다.
이 방식을 사용하면 각 윈도우에서 최대값을 찾는 데 필요한 시간 복잡도가 상수 시간이 된다. 이는 덱이 항상 윈도우의 최대값을 앞쪽에 유지하기 때문이다.
예시 코드
#include <iostream>
#include <vector>
#include <deque>
#include <utility>
using namespace std;
vector<int> MaxSlidingWindow(vector<int>& nums, int k)
{
deque<pair<int, int>> dq; // 덱은 윈도우에서 최대값의 인덱스와 값을 저장한다.
vector<int> result; // 결과를 저장할 벡터
for(int i = 0; i < nums.size(); ++i)
{
// 덱의 첫 번째 원소가 윈도우 범위에서 벗어나면 제거
if(!dq.empty() && dq.front().secont == i - k)
{
dq.pop_front();
}
// 현재 원소보다 작은 덱의 원소를 제거
while(!dq.empty() && dq.back().first < nums[i])
{
dq.pop_back();
}
// 현재 원소의 값을 덱에 추가
dq.emplace_back(nums[i], i);
// 윈도우의 크기가 k가 되면 결과에 추가
if(i >= k - 1)
{
result.push_back(dq.front().first);
}
}
return result;
}
int main()
{
vector<int> nums = {1, 3, -1, -3, 5, 3, 6, 7}; // 입력 배열
int k = 3; // 슬라이딩 윈도우의 크기
vector<int> result = MaxSlidingWindow(nums, k); // 함수 호출
// 결과 출력
cout << "슬라이딩 윈도우의 최대값 : ";
for(int val : result)
{
cout << val << " ";
}
return 0;
}
'프로그래밍 > 알고리즘' 카테고리의 다른 글
| [알고리즘] 버블 정렬(Bubble Sort) (1) | 2024.01.06 |
|---|