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

 

관련글

 

Dynamic Programming 관련 포스팅은 여기를 참조
LIS 관련 포스팅은 여기를 참조

 

 

1. 개요

 

문제 링크는 여기를 참조

 

문제의 내용을 보려면 아래 더보기 클릭

 

이 문제는 LIS의 길이를 구하는 문제이다.

 

 

2. 풀이

 

이 문제는 상단의 관련글에서 표기한 LIS 포스팅을 보는 것이 더 낫다.
간단히 이야기하여 순차적으로 저장된 데이터가 있는 배열의 부분 배열 중 증가하면서 가장 긴 부분 배열을 구하는 문제이다.

 

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

 

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

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

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

 

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

 

제일 중요한 점화식을 알아보자. LIS의 특성에 따라 점화식은 다음과 같이 지정할 수 있다.
점화식 : 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[] 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];
        
        String line[] = br.readLine().split(" ");
        for(int i=0; i < N; i++){
            arr[i] = Integer.parseInt(line[i]);
        }
        
        int result = bottomUp(N);
        
        bw.write(String.valueOf(result));
        br.close();
        bw.flush();
    }
    
    // Bottom-up 방식
    public static int bottomUp(int n){
        lis = new int[n];
        
        // 최대 lis 길이 값
        int max_lis = 1;
        
        // 반복문을 통해 점화식을 구성하여 최소값을 채워나감
        for(int i=0; i < n; i++){
            lis[i] = 1; // 각 위치를 1로 우선 초기화, 기저 상태 lis[0]도 초기화됨
            for(int j=i-1; j >= 0; j--){
                // 이전 값이 더 작으면서 lis 길이 값은 같거나 큰 경우
                if(arr[i] > arr[j] && lis[j] >= lis[i]){
                    lis[i] = lis[j]+1;
                }
                if(max_lis < lis[i]){
                    max_lis = lis[i];
                }
            }
        }
        return max_lis;
    }
}

 

2) Top-Down 방식

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]; lis[0] = 1;
        
        String line[] = br.readLine().split(" ");
        for(int i=0; i < N; i++){
            arr[i] = Integer.parseInt(line[i]);
        }
        
        int result = 0;
        for(int i=0; i < lis.length; i++){
            int temp = topDown(i);
            if(lis[result] < lis[temp]){
                result = temp;
            }
        }
        
        bw.write(String.valueOf(lis[result]));
        br.close();
        bw.flush();
    }
    
    // Top-Down 방식으로 해결하는 DP
    public static int topDown(int n){
        if(n == 0 || lis[n] > 0) return n; // 기저상태 또는 이미 이전의 값이 있는 경우
        lis[n] = 1; // 우선 1로 초기화
        
        // 자신보다 이전의 값들과 비교해야함. 그 중 가장 큰 값으로!
        for(int i=n-1; i >= 0; i--){
            int temp = -1;
            if(arr[i] < arr[n]){
                temp = topDown(i);
            }
            if(temp != -1 && lis[temp] >= lis[n]){
                lis[n] = lis[temp] + 1;
            }
        }
        return 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.MAX_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){
                start = mid + 1;
            } else {
                end = mid-1;
            }
        }
        // 일치값을 찾지 못했을 때, -1이 아니라 그 적절한 위치를 반환해야 함
        return start;
    }
}

 

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