[Do it! 알고리즘 코딩테스트: Chapter 3] 슬라이딩 윈도우(Sliding Window)

본 포스팅은 Do it! 알고리즘 코딩테스트: C++편을 토대로 공부한 내용을 정리하기 위한 포스팅입니다.

https://github.com/KwonKiHyeok/Do_it_Alogrithm_Coding_Test_with_Cpp

GitHub - KwonKiHyeok/Do_it_Alogrithm_Coding_Test_with_Cpp: Do it! 알고리즘 코딩 테스트: C++편

 

 

슬라이딩 윈도우 개념

• 윈도우 크기(길이)를 정한 후, 배열이나 문자열 위에서 윈도우를 한 칸씩 이동하면서 문제를 해결한다.
• 중복된 연산을 피하고, 이전 윈도우의 결과를 활용하여 시간을 절약한다.

 

 

1. 고정 크기 윈도우(Fixed Window)

• 윈도우 크기가 일정한 경우
• ex) 배열에서 연속된 K개의 숫자의 합을 구하는 문제

2. 가변 크기 윈도우(Variable Window)

• 윈도우 크기가 문제의 조건에 따라 변하는 경우
• ex) 합이 특정 값 이상이 되는 최소 길이의 부분 배열 찾기

// Baekjoon Online Judge Problem. 12891

#include <iostream>
#include <vector>
using namespace std;

int main() {

	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int S, P;
	cin >> S >> P;
	vector<char> v(S);

	for (int i = 0; i < S; i++) {
		cin >> v[i];
	}

	int A, C, G, T, answer = 0;
	int a = 0, c = 0, g = 0, t = 0;
	cin >> A >> C >> G >> T;

	for (int i = 0; i <= S - P; i++) {
		if (i == 0) {
			for (int j = 0; j < P; j++) {
				if (v[j] == 'A') a++;
				else if (v[j] == 'C') c++;
				else if (v[j] == 'G') g++;
				else if (v[j] == 'T') t++;
			}
		}
		else {
			if (v[i - 1] == 'A') a--;
			else if (v[i - 1] == 'C') c--;
			else if (v[i - 1] == 'G') g--;
			else if (v[i - 1] == 'T') t--;

			if (v[i + P - 1] == 'A') a++;
			else if (v[i + P - 1] == 'C') c++;
			else if (v[i + P - 1] == 'G') g++;
			else if (v[i + P - 1] == 'T') t++;
		}

		if (a >= A && c >= C && g >= G && t >= T) {
			answer++;
		}
	}

	cout << answer << '\n';

	return 0;
}

 

 

 

// Baekjoon Online Judge Problem. 11003

#include <iostream>
#include <deque>
using namespace std;
typedef pair<int, int> Node;

int main() {

	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int N, L;
	cin >> N >> L;
	deque<Node> A;

	for (int i = 0; i < N; i++) {
		int now;
		cin >> now;
		
		while (A.size() && A.back().first > now) {
			A.pop_back();
		}

		A.push_back(Node(now, i));

		if (A.front().second <= i - L) {
			A.pop_front();
		}
		cout << A.front().first << ' ';
	
	}

	return 0;
}

 

 일정 범위 안에서 최솟값을 구하는 문제이므로 슬라이딩 윈도우와 정렬을 사용해야한다. 하지만 최솟값을 찾기 위한 일반적인 정렬은 O(nlongn)의 시간 복잡도를 가지므로 N과 L의 최대 범위가 5,000,000인 문제에서는 정렬을 사용할 수 없다.

 다시 말해 O(n)의 시간 복잡도로 해결할 수 있어야 한다. 따라서 슬라이딩 윈도우를 덱으로 구현하여 정렬 효과를 만들어내도록 한다. 

 

1. 최초 Node( , )가 덱에 추가되면 비교 대상이 없고, 범위도 만족하므로 바로 답을 출력한다.

2. 다음 Node는 이전 Node와 숫자를 비교한다. 다음 Node의 숫자가 더 큰 경우에는 탐색을 멈추고 덱에  추가한다. 만약 다음 Node의 숫자가 더 작은 경우에는 이전 Node를 덱에서 제거한다. 이 비교는 덱의 size가 0 이상이고, 다음 Node의 숫자가 이전 Node의 숫자보다 더 작은 경우 계속 반복한다. 

3. L의 범위를 벗어난 값은 덱에서 제거한다.