[알고리즘,JAVA] 백준 2003 수들의 합 2 , sliding window

안녕하세요? "태민"입니다.

오랜만에 티스토리에 글을 씁니다. 왜냐하면 주말에 코딩테스트 무려 3개나 봤기 때문입니다.

안타깝게도 못 푼 문제가 있었는데 그 문제를 어떤 식으로 풀어야 하는지 나중에 알아보니

슬라이딩 윈도우 알고리즘을 이용하면 쉽게 풀 수 있었던 문제였습니다...

아쉽게도 저는 슬라이딩 윈도우 알고리즘을 몰랐기에 오늘 포스트팅하며 배우고 하고자 합니다.

오늘은 슬라이딩 윈도우가 무엇인지 슬라이딩 윈도우를 이용해서 알고리즘 문제를 풀어보도록 하겠습니다.

1. 슬라이딩 윈도우

1-1. 도입

슬라이딩 윈도우는 원래는 TCP 통신 프로토콜 중 하나를 지칭하는 말입니다. 대충 살펴보자면

송신측은 윈도우의 크기를 수신자의 상태에 따라 자유자재로 조정하고 있습니다. TCP 통신에서는 상태방이 데이터를 잘 받았다는 신호를 보내면 보낸 것이 확인된 패킷은 윈도우에서 빼고, 다시 윈도우 크기를 늘려 데이터를 보내고 있습니다. 마찬가지로 알고리즘에서 사용될 슬라이딩 윈도우도 어떠한 상태에 따라 윈도우의 크기를 줄였다 늘렸다. 할 생각입니다.

1-2. 특징

연속된 배열의 특정한 조건이 주어진 경우 유용하다
O(n^2) 를 선형 형태의 O(N) 으로 계산이 가능하다

2. 윈도우 슬라이딩 적용

2-1. 문제

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

2003번: 수들의 합 2

첫째 줄에 N(1≤N≤10,000), M(1≤M≤300,000,000)이 주어진다. 다음 줄에는 A[1], A[2], …, A[N]이 공백으로 분리되어 주어진다. 각각의 A[x]는 30,000을 넘지 않는 자연수이다.

www.acmicpc.net

N개의 수로 된 수열 A[1], A[2], …, A[N] 이 있다. 이 수열의 i번째 수부터 j번째 수까지의 합 A[i]+A[i+1]+…+A[j-1]+A[j]가 M이 되는 경우의 수를 구하는 프로그램을 작성하시오.

2-2. 풀이

TCP 통신을 위한 슬라이딩 윈도우의 크기는 고정되어 있지만, 이 알고리즘에서는 고정되어 있지 않습니다. 다만, 합이 5인 조건에 따라 윈도우의 크기를 변화시킵니다.

2-3. 코드

import java.util.Scanner;

public class Main_2003 {

	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		
		int N = sc.nextInt();
		int M = sc.nextInt();
		int count = 0;
		int arr[] = new int[N];
		
		for (int i = 0; i < N; i++) {
			arr[i] = sc.nextInt();
		}
		
		int i = 0;
		int j = 0;
		int sum = 0;
		while(true) {
			if(sum >= M) {
				sum -= arr[i++];
			}else if(j > N-1) {
				break;
			}else if(sum < M) {
				sum += arr[j++];
			}
			if(sum == M)
				count++;
		}
		System.out.println(count);
	}
}

여담

이번 주말에 시간이 없어서 블로그포스팅을 할 시간이 없었습니다. 코딩테스트 보는 도중 제가 모르는 알고리즘방법으로 풀어야 한다는 이야기를 들었을 때, 좀 더 공부할 걸이라는 후회와 또 배울 것이 생겼다는 호기심이 생겼습니다. 언제나 사람이 완벽할 수 없다는 걸 인지하고, 배울 것이나 모르는 것이 있다면 좌절하지 말고, 하나하나 배워나가 다음에는 이런 실수를 반복하지 않도록 노력하려 합니다.