안녕하세요? "태민"입니다.
오랜만에 티스토리에 글을 씁니다. 왜냐하면 주말에 코딩테스트 무려 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);
}
}
여담
이번 주말에 시간이 없어서 블로그포스팅을 할 시간이 없었습니다. 코딩테스트 보는 도중 제가 모르는 알고리즘방법으로 풀어야 한다는 이야기를 들었을 때, 좀 더 공부할 걸이라는 후회와 또 배울 것이 생겼다는 호기심이 생겼습니다. 언제나 사람이 완벽할 수 없다는 걸 인지하고, 배울 것이나 모르는 것이 있다면 좌절하지 말고, 하나하나 배워나가 다음에는 이런 실수를 반복하지 않도록 노력하려 합니다.
안녕하세요? "태민"입니다.
부족한 부분이나 추가하고 싶은 부분이 있으시다면 댓글로 남겨주세요!