'Do it! 알고리즘 코딩테스트 자바 편' 교재로 공부한 내용을 정리했습니다
슬라이딩 윈도우
슬라이딩 윈도우 알고리즘은 2개의 포인터로 범위를 지정한 다음 범위(window) 을 유지한 채로 이동(sliding) 하면서 문제를 해결한다.
위 문장만 읽어봐도 투 포인터 알고리즘과 매우 비슷하다는 것을 알 수 있을 겁니다! 원리도 간단하므로 바로 백준 문제 2개를 풀어보면서 윈도우 알고리즘의 개념과 원리를 공부해 봅시다!
백준 12891 번
https://www.acmicpc.net/problem/12891
12891번: DNA 비밀번호
평소에 문자열을 가지고 노는 것을 좋아하는 민호는 DNA 문자열을 알게 되었다. DNA 문자열은 모든 문자열에 등장하는 문자가 {‘A’, ‘C’, ‘G’, ‘T’} 인 문자열을 말한다. 예를 들어 “ACKA”
www.acmicpc.net
1. 문제 분석
DNA 문자열 길이 S. 부분 문자열의 길이 P. P 와 S 의 길이는 최대 1,000,000 개로 매우 크다. 이는 O(n) 으로 해결해야 한다.
부분 문자열의 길이가 P인 것을 슬라이딩 윈도우의 개념을 이용한다.
2. 손으로 풀기
1. S 배열과 비밀번호 체크 배열을 입력받고 저장한다.
2. 윈도우에 포함된 문자로 현재 상태 배열을 만든다.
3. 윈도우를 한 칸씩 이동하며 현재 상태 배열을 업데이트한다.
업데이트한 이후, 또 비밀번호 체크 배열과 비교하여 비밀번호 유효성을 판단한다.
현재 상태 배열을 업데이트할 때는 윈도우에서 빠지는 문자열과 추가되는 신규 문자열만 보고 업데이트를 하면된다.
이 문제에서는 슬라이딩 윈도우 원리 이외에도 '실제 문자열과 관련된 배열 처리를 어떻게 할 것인가?' , '비밀번호 유효성 검사를 보다 빠르게 할 수 있는 방법이 있을까?' 등 코드 레벨에서의 고민이 필요하다. 슈도 코드를 작성하면서 이를 어느정도 고안해봅시다.
3. 슈도 코드
문자열 크기 S, 부분 문자열(윈도우) 크기 P 입력받고 저장.
문자열 데이터 A 입력받고 저장
비밀번호 체크 배열 checkArr
현재 상태 배열 myArr
몇개의 문자 조건을 충족했는지 판단하는 변수 checkEachChar
P 범위 (0 ~ P - 1) 만큼 S 배열에 적용하고 유효한 비밀번호인지 판단.
for(i 를 P 에서 S 까지 반복) {
j 선언. (i - P) // j 는 윈도우의 첫번째 문자열의 인덱스.
한 칸씩 이동하면서 제거되는 문자열과 새로 들어오는 신규 문자열 처리.
유효한 비밀번호인지 ( if checkEachChar == 4 ) 인지 판단. 결과값 업데이트.
}
결과값 출력.
4. 구현
public class BaekJoon12891 {
static int[] checkArr = new int[4]; // 비밀번호 체크
static int[] myArr = new int[4]; // 현재 상태
static int checkEachChar = 0;
public static void main(String[] args) throws IOException {
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(bf.readLine());
int S = Integer.parseInt(st.nextToken());
int P = Integer.parseInt(st.nextToken());
int result = 0;
char[] A = new char[S];
A = bf.readLine().toCharArray();
st = new StringTokenizer(bf.readLine());
// 비밀번호 체크 배열 저장
for (int i = 0; i < 4; i++) {
checkArr[i] = Integer.parseInt(st.nextToken());
// 부분문자열 P 에 필요없는 문자가 있으면 1 증가.
if (checkArr[i] == 0) {
checkEachChar++;
}
}
// 부분 문자열 P 처음 처리.
for (int i = 0; i < P; i++) {
char c = A[i];
addNewChar(c);
}
if (checkEachChar == 4) {
result++;
}
// sliding window
for (int i = P; i < S; i++) {
int j = i - P;
char c = A[i];
addNewChar(c);
char c2 = A[j];
removeOldChar(c2);
if (checkEachChar == 4) {
result++;
}
}
System.out.println(result);
}
private static void removeOldChar(char c2) {
switch (c2) {
case 'A':
if (myArr[0] == checkArr[0]) {
checkEachChar--;
}
myArr[0]--;
break;
case 'C':
if (myArr[1] == checkArr[1]) {
checkEachChar--;
}
myArr[1]--;
break;
case 'G':
if (myArr[2] == checkArr[2]) {
checkEachChar--;
}
myArr[2]--;
break;
case 'T':
if (myArr[3] == checkArr[3]) {
checkEachChar--;
}
myArr[3]--;
break;
}
}
private static void addNewChar(char c) {
switch (c) {
case 'A':
myArr[0]++;
if (myArr[0] == checkArr[0]) {
checkEachChar++;
}
break;
case 'C':
myArr[1]++;
if (myArr[1] == checkArr[1]) {
checkEachChar++;
}
break;
case 'G':
myArr[2]++;
if (myArr[2] == checkArr[2]) {
checkEachChar++;
}
break;
case 'T':
myArr[3]++;
if (myArr[3] == checkArr[3]) {
checkEachChar++;
}
break;
}
}
}
백준 11003 번
https://www.acmicpc.net/problem/11003
11003번: 최솟값 찾기
N개의 수 A1, A2, ..., AN과 L이 주어진다. Di = Ai-L+1 ~ Ai 중의 최솟값이라고 할 때, D에 저장된 수를 출력하는 프로그램을 작성하시오. 이때, i ≤ 0 인 Ai는 무시하고 D를 구해야 한다.
www.acmicpc.net
1. 문제분석
일단 문제를 읽었는데 잘 이해가 되지 않았습니다...
그래서 입력과 출력의 예시로 주어진 것으로 문제를 먼저 이해했습니다.
예제 입력 1
12 3
1 5 2 3 6 2 3 7 3 5 2 6
예제 출력 1
1 1 1 2 2 2 2 2 3 3 2 2
그러니까 출력에서는 순서대로
(A1), (A1 ~ A2 에서 최소값), (A1 ~ A3 에서 최소값), (A2 ~ A4 에서 최소값) ....... 이렇게 되는 것이네요.
일점 범위 안에서 최소값을 구하는 문제입니다. 슬라이딩 윈도우와 정렬을 사용합니다.
윈도우의 크기는 문제에서 최소값을 구하는 범위가 i-L+1 부터 i 까지이므로 L 로 생각하면 됩니다.
i - (i - L + 1) + 1 = L
일반적으로 정렬은 n㏒(n) 의 시간 복잡도를 가지므로 N 과 L 의 최대 범위가 5,000,000 인 이 문제에서는 정렬을 사용할 수 없습니다. 즉, O(n) 의 시간 복잡도로 해결해야 하지요. 하지만 슬라이딩 윈도우를 덱(deque) 으로 구현하여 정렬 효과를 볼 수 있습니다.
덱의 구조는 아래와 같습니다.
덱은 양 끝에서 데이터를 삽입/삭제할 수 있는 자료구조입니다.
2. 손으로 풀기
1. 덱에서는 (인덱스, 숫자) 형태의 노드라는 클래스로 구현하여 저장합니다.
설명은 예제 입력 1 과 예제 출력 1 을 기준으로 하겠습니다. 먼저 제일 처음 노드 두 개가 덱에 잇다고 합시다.
2. 이 상태에서 새 노드 (3, 2) 가 덱에 저장됩니다. 이 때부터 기존 덱에 있던 노드가 제거되어야 합니다.
새 노드 (3, 2) 가 저장될 때 덱 뒤에서부터 비교를 시작합니다.
(2, 5)는 (3, 2)보다 숫자가 크므로 (2, 5)는 덱에서 제거합니다.
이어서 (1, 1)은 (3, 2)보다 숫자가 작으므로 탐색을 멈추고 (3, 2)를 덱에 저장합니다.
결과를 보면 덱에는 (1, 1), (3,2) 순서로 노드가 오름차순 정렬되어 있습니다.이것이 덱을 이용하여 정렬 효과를 보는 방법입니다.
정리를 끝마친 상태의 덱을 보면 인덱스의 범위는 1 ~ 3 이므로 여기서 최소값을 찾으면 세번째 출력(D₃) 의 결과이죠!!
그리고 덱에서 최소값은 결국 첫번째 노드의 숫자인 1이 됩니다.
3. 계속해서 새 노드를 추가합니다. 이번에는 인덱스 범위가 슬라이딩 윈도우를 벗어날 것입니다.
새 노드 (4, 3) 은 덱 뒤에서부터 비교했을 때 (3, 2) 보다 숫자가 더 크므로 덱에 저장됩니다. 그런데 첫번재 노드의 인덱스는 1이고 마지막 노드의 인덱스는 4입니다. 즉, 인덱스의 범위는 1 ~ 4 인 4가 되어서 슬라이딩 윈도우보다 크게 됩니다.
이렇게 되면 문제의 조건에 맞지 않습니다. 우리는 인덱스 범위가 2 ~ 4 에서 최소값을 찾아야 합니다.
그러므로 첫번재 노드 (1,1) 을 덱에서 제거합니다.
그 후 덱에서 최소값은 첫번째 노드의 숫자인 2 입니다.
4.이렇게 숫자 비교를 하여 덱에 노드를 넣고 윈도우 범위를 계산하여 노드를 삭제하는 것까지 완료한 덱에서 최소값을 찾기만 하면 됩니다.
3. 슈도코드
N , L (데이터 개수, 최소값을 구하는 범위) 입력받고 저장
Deque<Node> mydeque (데이터를 담을 덱 자료구조)
for (N 만큼 반복){
nowNode 을 선언한다. (i 번째 노드)
덱의 rear 에서부터 nowNode 보다 큰 값은 덱에서 제거
덱의 rear 에 nowNode 삽입.
덱의 front 에서부터 L 의 범위를 벗어난 노드를 덱에서 제거
덱의 front Node 의 숫자 출력
}
덱에 저장할 노드 클래스 생성. (노드 클래스는 인덱스와 숫자를 값으로 가짐)
4. 구현
public class BaekJoon11003 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// 출력을 버퍼에 넣고 한번에 출력하기 위한 BufferedWriter.
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken()); // 데이터의 개수
int L = Integer.parseInt(st.nextToken()); // 최소값을 구하는 범위
st = new StringTokenizer(br.readLine()); // N 개의 수 A_i 입력받기
Deque<Node> myDeque = new LinkedList<>();
for (int i = 0; i < N; i++) {
int iNodeValue = Integer.parseInt(st.nextToken());
// rear 에서부터 비교
while (!myDeque.isEmpty() && myDeque.getLast().value > iNodeValue) {
myDeque.removeLast();
}
// 덱에 노드 추가
myDeque.addLast(new Node(i, iNodeValue));
// 윈도우의 크기 조건. -> 덱에 노드가 L 보다 더 많으면 front Node 삭제
if ((myDeque.getLast().index - myDeque.getFirst().index) >= L) {
myDeque.removeFirst();
}
bw.write(myDeque.getFirst().value + " ");
}
bw.flush();
}
static class Node {
public int index;
public int value;
public Node(int index, int value) {
this.index = index;
this.value = value;
}
}
}
이 문제의 핵심은 정렬 알고리즘을 사용하지 않고도 슬라이딩 윈도우와 덱을 이용하여 정렬 효과를 보는 것입니다.
다음 글에서는 자료 구조 중에서 핵심인 스택, 큐를 공부하도록 하겠습니다~
'Java > 코딩테스트' 카테고리의 다른 글
| [Java] 코딩테스트 BufferedReader, BufferedWriter 을 쓰는 이유 (0) | 2023.05.21 |
|---|---|
| 스택 & 큐 - 자바 백준 스택수열: 1874 오큰수: 17298 (0) | 2023.05.21 |
| 자바 코딩 테스트 - 투 포인터. 백준 2018, 1940, 1253 (0) | 2023.01.03 |
| 자바 코딩 테스트 - 구간 합. 백준 11659 , 11660, 10986 문제 (0) | 2023.01.02 |
| 자바 코딩 테스트 - 배열과 리스트, 백준 11720, 1546 문제 (0) | 2023.01.02 |