[알고리즘] 슬라이딩 윈도우 개념 및 문제

 

 

 

 슬라이딩 윈도우 

사용하는 이유

예를 들어, { 1, 2, 3, 4, 5 } 라는 수열이 주어졌다고 봅시다.

여기서 부분 문자열 3씩 끊어 해당 부분 문자열 들 중에서 어느 부분이 제일 합이 큰지 알고 싶습니다.

그러면 두 개의 반복문을 이용하여 구할 수 있을 것입니다.

package day220805.practice;


public class Test {
	// 최댓값을 찾으려는 주어진 수열
	static int[] arr = { 1, 2, 3, 4, 5 };
	// 부분 문자열의 길이
	static int P = 3;


	public static void main(String[] args) {
		// 최댓값 초기화
		int max = Integer.MIN_VALUE;

		// 전체 인덱스를 돈다.
		for (int i = 0; i < arr.length - P + 1; i++) {
			int sum = 0;

			// 부분 문자열을 끊어 sum 을 구한다.
			for (int j = i; j < i + P; j++) {
				System.out.print(arr[j] + " ");
				sum += arr[j];
			}

			System.out.println("의 sum: " + sum);

			// 최댓값을 갱신한다.
			max = Math.max(max, sum);

		}

		System.out.println("max 값: " + max);

	}
}

출력

3, 4, 5 일 때 합이 제일 큰 것을 알 수 있습니다.

 

하지만 만약에 주어진 수열의 크기가 엄청 크다면 어떻게 될까요?

입력의 크기가 100000 (십만) = 10^5 이라고 해봅시다.

그렇게 되면 반복문을 두번 도는 것만으로도 대략 10^10 이 되어 100 억의 값이 나오게 됩니다.

1억번의 연산을 1초라고 친다면 100억의 값은 100초가 걸리게 됩니다.

 

알고리즘을 풀 때 보통 시간 제한이 1, 2 초에 해당합니다.

이것과 비교해보았을 때 100초는 엄청 큰 시간이 아닐 수가 없습니다. 문제를 풀었을 때 시간초과가 나오는 이유도 이와 같습니다.

그렇다면 어떻게 풀어야 할까요?

 

시간복잡도 그래프

우리는 O(N^2) 에 해당하는 값을 적어도 O(NlogN) 혹은 O(N) 으로 바꿀 수 있다면 성공한 것입니다.

(여담이지만 수중에 있는 빠른 정렬들이 다 O(NlogN) 에 해당합니다.)

 

이런식으로 부분 문자열을 구할 때 시간 복잡도의 크기를 줄이기 위해서 슬라이딩 윈도우 라는 기법을 사용합니다.

 

개념

슬라이딩 윈도우

두 개의 반복문을 돌아 우리는 부분 문자열을 끊었습니다.

이와 마찬가지로 구간을 끊으면 되는데 반복문을 하나만 돌아서 이를 구현할 수 있습니다.

하나씩 옮기게 되면 새로 나타난 요소를 제외하고는 반복이 되게 됩니다. 슬라이딩 윈도우는 이러한 특징을 이용합니다.

마치 모양이 문을 옆으로 밀어 닫는 것과 비슷합니다.

 

package day220805.practice;


public class Test {
	// 최댓값을 찾으려는 주어진 수열
	static int[] arr = { 1, 2, 3, 4, 5 };
	// 부분 문자열의 길이
	static int P = 3;


	public static void main(String[] args) {
		// 최댓값 초기화
		int max = Integer.MIN_VALUE;

		int sum = 0;

		// 부분 문자열의 길이만큼 돈다.
		System.out.print("초기 배열: ");
		for (int i = 0; i < P; i++) {
			System.out.print(arr[i] + " ");
			sum += arr[i];
		}

		System.out.println("의 합 => " + sum);

		// 하나씩 밀면서 더해간다.
		for (int i = P; i < arr.length; i++) {
			// 제일 처음에 있는 요소는 빼준다.
			// 왜냐하면 다음으로 밀어졌으니 이전 값은 제외가 된다.
			sum -= arr[i - P];
			System.out.print("제외하는 요소: " + arr[i - P] + ", ");

			// 밀어졌으니 새로운 값을 하나 더해준다.
			sum += arr[i];
			System.out.print("새롭게 더해지는 요소: " + arr[i] + " => " + sum + "\n");

			// 최댓값 갱신
			max = Math.max(max, sum);

		}

		System.out.println("max 값: " + max);

	}
}

출력

이렇게 슬라이딩 윈도우 기법으로 O(N) 의 크기만으로도 해당 문제를 풀 수 있게 됩니다.

 

 

 

 문제 

백준 블로그 문제

https://www.acmicpc.net/problem/21921

21921번: 블로그

2022.08.08 - [✏️ 𝗔𝗹𝗴𝗼𝗿𝗶𝘁𝗵𝗺/백준 알고리즘] - [BJ21921] 블로그

[BJ21921] 블로그

 

백준 DNA 비밀번호 문제

https://www.acmicpc.net/problem/12891

12891번: DNA 비밀번호

2022.08.08 - [✏️ 𝗔𝗹𝗴𝗼𝗿𝗶𝘁𝗵𝗺/백준 알고리즘] - [BJ12891] DNA 비밀번호

[BJ12891] DNA 비밀번호

 

 

 

 

 

 

 

 

# 알고리즘 슬라이딩 윈도우 # sliding window # 슬라이딩 윈도우 java

---