알고리즘 풀이 - 백준 11722(가장 긴 감소하는 부분 수열, DP)

 

관련글

 

Dynamic Programming 관련 포스팅은 여기를 참조
LIS 관련 포스팅은 여기를 참조
관련 문제인 11053번(가장 긴 증가하는 부분 수열) 포스팅은 여기를 참조
관련 문제인 14002번(가장 긴 증가하는 부분 수열 4) 포스팅은 여기를 참조
관련 문제인 11055번(가장 큰 증가 부분 수열) 포스팅은 여기를 참조

 

 

1. 개요

 

문제의 링크는 여기를 참조

 

 

이 문제는 LIS의 반대로 LDS의 길이를 구하는 문제이다.

 

 

2. 풀이

 

이 문제는 상단의 관련글에서 표기한 LIS 포스팅을 참고하면 쉽다. LIS의 반대인 LDS의 길이를 구하는 문제이지만 단순한 응용이기 때문이다.

 

이 문제는 기본적으로 DP로 풀 수 있고, 그 보다 더 개선된 시간복잡도를 갖는 방식으로 풀어내는 것도 가능하다. 해당 내용 또한 상단의 LIS 포스팅에 있으니 참고하자.

 

간단히 문제의 정의, 기저 상태, 점화식을 알아보자.

정의 : 길이 N의 배열에서 LDS의 길이를 구하기.

길이 N이라는 값 자체가 State이므로 배열의 길이에 따른 결과값만 저장하는 배열을 별도로 생성한다. DP의 결과를 저장할 배열을 lis[]라고 부르자. 그 크기는 기존 배열과 같게 생성하면 될 것이다.

 

그렇다면, 기저 상태는 어떻게 되나? 배열의 길이가 1일 때이다. 즉 N=1, index로는 0일 때, 그 자체로만 LIS가 되므로 그 상태 지정을 할 수 있다.
기저 상태 : lis[0] = 1

 

제일 중요한 점화식을 알아보자. LDS의 특성에 따라 점화식은 다음과 같이 지정할 수 있다.
점화식 : lis[i] = lis[j] + 1 (단, j < i and arr[j] > arr[i])

 

 

3. 코드

 

아래의 코드를 통해 정답을 알아보자.

 

1) Bottom-up 방식

import java.io.*;

public class Main{
    static int[] arr;
    static int[] dp;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        int N = Integer.parseInt(br.readLine());
        arr = new int[N];
        dp = new int[N];
        
        String line[] = br.readLine().split(" ");
        
        int result = 0;
        for(int i=0; i < N; i++){
            arr[i] = Integer.parseInt(line[i]);
            dp[i] = 1;
            for(int j=i-1; j >= 0; j--){
                if(arr[i] < arr[j] && dp[i] <= dp[j]){
                    dp[i] = dp[j] + 1;
                }
            }
            result = Math.max(result, dp[i]);
        }
        
        bw.write(String.valueOf(result));
        br.close();
        bw.flush();
    }
}

 

2) Top-Down 방식

import java.io.*;
public class Main{
    static int[] arr;
    static int[] dp;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        int N = Integer.parseInt(br.readLine());
        arr = new int[N];
        dp = new int[N]; dp[0] = 1;
        
        String line[] = br.readLine().split(" ");
        for(int i=0; i < N; i++){
            arr[i] = Integer.parseInt(line[i]);
        }
        
        topDown(N-1);
        
        int result = 0;
        for(int i=0; i < N; i++){
            result = Math.max(result, dp[i]);
        }
        
        bw.write(String.valueOf(result));
        br.close();
        bw.flush();
    }
    
    // Top-Down 방식으로 해결하는 DP
    public static int topDown(int n){
        // 기저상태 또는 이미 이전의 값이 있는 경우
        if(n == 0) return dp[n] = 1;
        if(dp[n] > 0) return dp[n]; 
        
        dp[n] = 1;
        // 자신보다 이전의 값들과 비교해야함. 그 중 가장 큰 값으로!
        for(int i=n-1; i >= 0; i--){
            int temp = topDown(i);
            if(arr[i] > arr[n] && dp[n] <= temp){
                dp[n] = temp + 1;
            }
        }
        return dp[n];
    }
}

 

3) 개선된 방식(O(nlogn))

import java.io.*;
public class Main{
    static int[] arr;
    static int[] lis;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        int N = Integer.parseInt(br.readLine());
        arr = new int[N];
        lis = new int[N];
        
        String line[] = br.readLine().split(" ");
        for(int i=0; i < N; i++){
            arr[i] = Integer.parseInt(line[i]);
            lis[i] = Integer.MIN_VALUE; // 최소값으로 우선 설정
        }
        
        lis[0] = arr[0]; // 최초의 index 0의 값은 arr[0]이 된다.
        
        int idx = 0;
        for(int i=1; i < arr.length; i++){
            // 만약 원 배열이 탐색 중 더 작은 숫자라면 그대로 이어서 붙인다.
            if(lis[idx] > arr[i]){
                lis[++idx] = arr[i];
            // 그렇지 않고 크다면 이진 탐색(Binary Search)를 통해 교체를 수행한다.
            } else {
                int target_index = binarySearch(lis, arr[i]);
                lis[target_index] = arr[i];
            }
        }
        
        bw.write(String.valueOf(idx+1));
        br.close();
        bw.flush();
    }
    
    // 반복문을 이용한 이진 탐색 방식
    public static int binarySearch(int[] arr, int x){
        int start = 0;
        int end = arr.length-1;

        // 현재 탐색한 위치가 찾고자 하는 값보다 크냐 작냐에 따라 중간 index 계산을 위한 start / end 값을 변경함
        // <= 와 같이 부등호로 쓰지 않으면 잘못된 위치가 됨. 이 경우는 현재 비교 위치가 start == end여도 성립된다.
        while(start <= end){
            int mid = (start + end) / 2;
            if(arr[mid] == x){
                return mid;
            } else if(arr[mid] < x){
                end = mid - 1;
            } else {
                start = mid + 1;
            }
        }
        // 일치값을 찾지 못했을 때, -1이 아니라 그 적절한 위치를 반환해야 함
        return start;
    }
}

 

 

 

읽어주셔서 감사합니다. 오류가 있으면 지적해주시면 반영하겠습니다.