동적계획법 (Dynamic Programming) - (4) 지그재그 문제

신찬수 교수님의 
알고리즘 동적계획법 - zigzag 문제 영상을 정리했습니다.

 

수열 [1,7,4,9,2,5] 가 있을 때, 이를 지그재그 수열이라고 한다.

 

크기가 큰 것과 작은 것이 번갈아 나오는 수열을 지그재그 수열이라고 한다.

수열 [1,5,3,2,7] 은 3 다음의 원소가 3보다 작은 2 이기 때문에 지그재그 수열이 아니다.

 

수열이 주어졌을 때, n개를 뽑아서 지그재그 수열을 만든다. 

예를 들어, [3,2,0,7,1,4,5,8,3]에선 [2,7,1,4,3]을 뽑아서 길이가 5인 지그재그 수열을 만들 수 있다.

만들 수 있는 지그재그 수열 중, 가장 길이가 긴 지그재그 수열을 구하는 것이 문제이다.

 

수열 [3,-1,2, 5, 7, 4, 5, 9, 8]에서, 5 (인덱스 6) 로 끝나는 지그재그 수열 두가지로 구분될 수가 있다.

5의 앞의 수가 5보다 큰 경우, 앞의 수가 5보다 작은 경우이다. 앞의 수열은 M모양, 뒤의 수열은 W모양의 지그재그 수열이 된다.

앞의 수가 5보다 작은 5로 끝나는 지그재그 수열은 [3, -1, 5, 4, 5] 가 된다.

앞의 수가 5보다 큰 5로 끝나는 지그재그 수열은 [3,2,7,5]가 된다.

 

해당 수보다 앞의 수가 작은 경우를 high 상태라고 하고, 큰 경우를 low라고 한다.

[3, -1, 5, 4, 5]의 경우 high, [3,2,7,5]는 low가 된다.

수열 [3,2,7,5] 에서, 7로 끝나는 수열은 [3,2,7]이 되고 high 상태인 수열이 된다.

수열 [3, -1, 5, 4, 5] 에서, 4로 끝나는 수열은 [3, -1, 5, 4]이 되고 low 상태인 수열이 된다.

 

DP 테이블을 생성한다.

low[k] = A[k]가 low인 상태로 끝나는 가장 긴 지그재그 수열의 길이

high[k] = A[k]가 high인 상태로 끝나는 가장 긴 지그재그 수열의 길이

A[k]로 끝나는 가장 긴 지그재그 수열의 길이 = max(low[k], high[k])

 

# j는 0부터 k-1까지
for k in range(n):
	for j in range(k):
		if A[j] > A[k]:
    			low[k] = max(low[k], high[j] +1)
    		if A[j] < A[k]:
    			high[k] = max(high[k], low[j] + 1)
for k in range(n):
	max(low[k], high[k])

 

두 개의 1차원 DP 테이블(low, high)이 등장하고 채워야한다. 알고리즘의 수행 시간은 O(N^2)가 된다.

 

[3,-1,2, 5, 7, 4, 5, 9, 8]의 경우

 

초기값은 모두 1로 초기화해준다. (low, high 테이블)

 

low 테이블

0	1	2	3	4	5	6	7	8
1	2	2	1	1	4	4	1	6

 

high 테이블

0	1	2	3	4	5	6	7	8
1	1	3	3	3	3	5	5	5

 

가장 긴 지그재그 수열의 길이

0	1	2	3	4	5	6	7	8
1	2	3	3	3	4	5	5	6

 

가장 길이가 긴 지그재그 수열의 길이는 6이된다. (아마도 [3, 2, 7, 5, 9, 8])

 

직접 구현한 코드 (JAVA)

(백준 13750번 Zigzag)

http://boj.kr/857394262d4347eba9bd8b4ef6c26799

공유 소스 보기

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int [] A = new int[N];
        int [] low = new int[N];
        int [] high = new int[N];
        for (int i = 0; i < N; i++) {
            A[i] = Integer.parseInt(br.readLine());
            low[i] = 1;
            high[i] = 1;
        }
        for (int k = 0; k < N; k++) {
            for (int j = 0; j < k; j++) {
                if (A[j] > A[k])
                    low[k] = Math.max(low[k], high[j] + 1);
                if (A[j] < A[k])
                    high[k] = Math.max(high[k], low[j] + 1);
            }
        }
        System.out.println(Math.max(low[N-1], high[N-1]));
    }
}

 

솔직히 답은 맞았는데 내가 잘 구현한지는..모르겠다..맞겠지..?

low배열도 high배열도 1로초기화하는것도맞는걸까..ㅠ_ㅠ