[백준]가장 긴 증가하는 부분 수열

onyoo·2023년 10월 25일

알고리즘

목록 보기

21/39

개요

대표적인 DP 문제로 두가지 버전으로 문제를 해결할 수 있다.
기억해두어야하는 유형일것같아서 기록한다.

가장 긴 증가하는 부분수열 1

가장 긴 증가하는 부분수열 2

문제 해석

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.

예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.

처음에는 단순하게 DP테이블을 구성했다.
DP테이블은 1차원 배열을 이루고있고,해당 인덱스 번호까지 갔을때의 최대 수열 길이를 저장하는 것을 목표로 구성했다.

이전의 숫자보다 큰 숫자가 나올때마다 dp 테이블의 이전항 + 1을 저장했다.

하지만,이 풀이법은 틀렸다.

왜냐하면, 시작지점이 무조건 0번항이라고 생각하기 때문이다. 그리고 무조건 큰 수를 찾아가기 때문에 중간에 더 긴 부분 수열이 나올 수 있는 가능성을 배제하기 때문이다.

예시는 다음과 같다.
10 20 30 15 20 25

10 - 20 - 30 까지는 순조롭게 수열이 이루어지고있다.
15가 들어가게 되면 어떻게 될까?

10 - 20 - 30 - 15 로, 15는 이후에 들어갈 수 없게 되어버린다.

즉, 이 경우에서 나올 수 있는 수열은

10 - 20 - 30 으로 3개의 원소를 가진 수열이 된다.

이를 다르게 생각해보자,

10 - 15 로, 뒤에있는 20과 30을 탈락시킨다면?

10 - 15 - 20 - 50 4개의 원소를 가진 수열이 된다.

즉,숫자는 커지되, 숫자가 커지는 폭은 작아져야 긴 수열이 될 수 있다는 것이다.

이 로직을 이진탐색으로 구현한 방법은 O(nlogn)의 시간 복잡도를 가진다.

하지만 이 방법에 앞서 쉽게 해결할 수 있는 방법을 알아보자, 물론 이 방법은 O(n^2)의 시간복잡도를 가지기 때문에,N의 크기가 커지면 문제를 해결하기가 어렵다!

두가지 방법을 모두 살펴보자.

해결방법 1

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

/**
 * @author onyoo
 * @performance
 * @category
 * @note
 * DP : 1차원 배열 , 해당 인덱스 길이의 숫자까지 왔을 때 가장 긴 수열의 길이를 저장
 * @see https://www.acmicpc.net/problem/11053
 * @since 2023-10-25
 **/
public class Main {
    static int N;
    static int[] arr,dp;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        N = Integer.parseInt(br.readLine());
        arr = new int[N];
        dp = new int[N]; // dp table
        dp[0] = 1; // 초항

        st = new StringTokenizer(br.readLine()," ");
        for(int i=0;i<N;i++){
            arr[i] = Integer.parseInt(st.nextToken());
        }
        int answer = 0;
        for(int i=0;i<N;i++){
            int max = 0;
            for(int j=0;j<i;j++){
                if(arr[i] > arr[j]) max = Math.max(max,dp[j]);
            }
            // 현재 값 보다 큰 값을 가지면서, dp 테이블의 값이 가장 큰 (수열의 길이가 긴) 경우를 고른다
            // 값을 구하지 못할 경우 0이기 때문에 상관없다
            dp[i] = max + 1;
            answer = Math.max(dp[i],answer); // dp 테이블에서 가장 큰 값이 답이다 !
        }
        System.out.println(answer);
    }
}

이 코드는 현재 원소보다 큰 값을 가지면서 dp 테이블의 값이 가장 큰 경우를 고르는 코드이다.

10 20 10 30 20 50 이 있다고 가정해보자.

DP[0] = 1 이다.

max 값은 0으로 DP[i]를 계산할때마다 초기화를 한다.
DP[i]를 구하기 위하여 우리는 i번째 원소보다 작은 j번째 원소를 찾을 것이다. 단, i > j 이다. 왜냐하면,수열이 이어지기 위해서는 i번째의 원소값이 j번째 원소값보다 커야 이어질 수 있기 때문이다.

조건을 만족한 값들 중 DP[j] 값과 max 값을 비교하며 가장 큰 DP[j] 값을 찾는다. 그래야 긴 수열이 될 수 있기 때문이다.

만약, max값이 0이 아닌상태로 계속 있다면 가장 긴 수열의 값이 + 1 로 업데이트가 될 것이고. 그렇지 않다면 현재 원소를 포함하여 가장 긴 수열의 길이가 1이 될 것이다 (max의 초깃값이 0이기 때문에 가능하다)

해결방법 2

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.StringTokenizer;

/**
 * @author onyoo
 * @performance
 * @category
 * @note
 * DP : 1차원 배열 , 해당 인덱스 길이의 숫자까지 왔을 때 가장 긴 수열의 길이를 저장
 * N의 크기가 1,000,000 으로 크다 -> 최적화 필요함 O(logN)의 시간 복잡도를 가지는 방법을 사용해야한다
 * 배열의 끝점이 최소가 되도록 유지해야한다
 * 배열의 끝점이 최소가 된다 -> 이후로 더 많은 수를 받을 수 있다.
 * 끝점이 커져버리게 되면, 이것보다 작은 숫자들은 못받기 때문에 !
 * https://buyandpray.tistory.com/73 (참고)
 * @see https://www.acmicpc.net/problem/11053
 * @since 2023-10-25
 **/
public class Main {
    static int N;
    static int[] seq,lis;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        N = Integer.parseInt(br.readLine());

        seq = new int[N];
        lis = new int[N];


        st = new StringTokenizer(br.readLine()," ");

        for(int i=0;i<N;i++){
            seq[i] = Integer.parseInt(st.nextToken());
        }

        lis[0] = seq[0];
        int length = 1; // lis의 길이

        for(int i=1;i<N;i++){
            
            int key = seq[i];
            
            if(lis[length-1] < key){
                length++;
                lis[length-1] = key;
            }
            else{
                //이전것보다 더 작은게 나온다면
                int low = 0;
                int high = length;
                while(low < high){
                    int mid  = (low + high) >>> 1;
                    if(lis[mid] < key){
                        low = mid + 1;
                    }else{
                        high = mid;
                    }
                }
                lis[low] = key;
            }
        }

        System.out.println(length);

    }

}