백준 11053( 가장 긴 증가하는 수열 ) - Python(파이썬),Java(자바)- 다이나믹(LIS)

참고 링크 : https://www.youtube.com/watch?v=5Lu34WIx2Us

11053번: 가장 긴 증가하는 부분 수열

---

LIS(Longest Increasing Subsequence)

D[i] = array[i]를 마지막 원소로 가지는 부분 수열의 최대 수열의 길이 

-> 점화식 : 모든 0<= j < i 에 대하여 D[i] = max( D[i] , D[i-1]+1) if array[ j  ]<array[ i ]

ex ]

array 배열

4

2

5

8

4

11

15

i=0

array	4	2	5	8	4	11	15
D[i]	1	1	1	1	1	1	1

i=1 (array[1]=2)

-> 4와 비교했을 때 2가 4보가 크므로 

array	4	2	5	8	4	11	15
D[i]	1	1	1	1	1	1	1

i=2 (array[2]=5)

-> 4와 비교했을 때 5가 4보다 크므로 4의 값이 1(D[0]) +1=2가 최댓값으로 들어간다.2 또한 5가 2보다 크므로 2의 값 1(D[1])+1 =2이다.  하지만 앞에서 4를 통해 먼저 2라는 값이 들어가기 때문에 2번째 원소인 2에 대해서는 업데이트가 이루어지지 않는다.

array	4	2	5	8	4	11	15
D[i]	1	1	2	1	1	1	1

i=3 (array[3]=8 )

-> 4와 비교했을 때 8이 4보다 크므로 4의 값 1(D[0])+1= 2 가 최댓값으로 들어간다. 2 또한 8이 2보다 크므로 2의 값 1(D[1])+1 =2이다. 하지만 앞에서 4를 통해 먼저 2라는 값이 들어갔기 때문에 2번째 원소인 2에 대해서는 업데이트가 이루어지지 않는다. 5와 비교했을 때 8이 5보다 크므로 5의 값 2(D[2])+1 = 3 으로 나와서 최댓값으로 최종적으로 들어간다.

array	4	2	5	8	4	11	15
D[i]	1	1	2	1-> 2 -> 3	1	1	1

i=4 (array[4]=4 )

-> 4와 비교했을 때 4이 4보다 크지 않으므로 업데이트가 이루어지지 않는다. 2는 4가 2보다 크므로 2의 값 1(D[1])+1 =2 최댓값은 2

로 변경된다. 5와 비교했을 때 4이 5보다 작으므로 업데이트가 이루어지지 않는다. 8과 비교했을 때 4가 8보다 작으므로 업데이트가 이루어지지 않는다. 따라서 최종적으로  2 이다.

array	4	2	5	8	4	11	15
D[i]	1	1	2	3	1 ->2	1	1

i=5 (array[5]=11 )

-> 4와 비교했을 때 11이 4보다 크므로 4의 값 1(D[0])+1= 2 가 최댓값으로 들어간다. 2 또한 11이 2보다 크므로 2의 값 1(D[1])+1 =2이다. 하지만 앞에서 4를 통해 먼저 2라는 값이 들어갔기 때문에 2번째 원소인 2에 대해서는 업데이트가 이루어지지 않는다. 5와 비교했을 때 11이 5보다 크므로 5의 값 2(D[2])+1 = 3 으로 나와서 최댓값으로  들어간다. 8과 비교했을 때 11이 8보다 크므로 3(D[3])+1= 4 최댓값으로 들어간다.  4와 비교했을 때 11이 4보다 크므로 2(D[4])+1=3이 나오지만 이미 최댓값 4가 들어갔으므로 최종적으로 4 이다.

array	4	2	5	8	4	11	15
D[i]	1	1	2	3	2	1->2->3->4	1

i= 6 (array[6]=15 )

-> 4와 비교했을 때 15가 4보다 크므로 4의 값 1(D[0])+1= 2 가 최댓값으로 들어간다. 2 또한 15가 2보다 크므로 2의 값 1(D[1])+1 =2이다. 하지만 앞에서 4를 통해 먼저 2라는 값이 들어갔기 때문에 2번째 원소인 2에 대해서는 업데이트가 이루어지지 않는다. 5와 비교했을 때 15가 5보다 크므로 5의 값 2(D[2])+1 = 3 으로 나와서 최댓값으로  들어간다. 8과 비교했을 때 15가 8보다 크므로 3(D[3])+1= 4 최댓값으로 들어간다.  4와 비교했을 때 15가 4보다 크므로 2(D[4])+1=3이 나오지만 이미 최댓값 4가 들어갔으므로 업데이트가 이루어지지 않는다. 11과 비교했을 때 15가 11보다 크므로 4(D[5])+1= 5 이므로 최댓값은 최종적으로 5 이다.

array	4	2	5	8	4	11	15
D[i]	1	1	2	3	2	4	1->2->3->4->5

 

이후에 D[i]테이블에 가장 큰 값을 출력하도록 할 경우 가장 긴 수열의 길이를 찾은 것이다.

---

풀이방법
① dp[i] 테이블을 생성한다 ( array[i]를 마지막 원소로 가지는 부분 수열의 최대 수열의 길이 )
② 점화식을 생성하면 모든 0<= j < i 에 대하여 D[i] = max( D[i] , D[i-1]+1) if array[ j  ] < array[ i ] 
③ 위 점화식을 활용하여서 for문으로 0부터 i-1까지 비교

Python으로 푼 경우 :

import sys
n=int(sys.stdin.readline())
#수열 A
A = list(map(int,sys.stdin.readline().split()))
dp=[1]*n

for i in range(1,n):
    for j in range(0,i):
        if A[j]<A[i]:
            dp[i]=max(dp[i],dp[j]+1)

print(max(dp))

Java로 푼 경우 :

1) Math.max로 최댓값 구하기 + 마지막에 Arrays.sort를 통해 max값 구하기

import java.util.*;
import java.io.*;

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[] array = new int[N];
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        for(int i=0;i<N;i++){
            array[i]=Integer.parseInt(st.nextToken());
        }
        int[] dp=new int[N];
        for(int i=1;i<N;i++){
            for(int j=0;j<i;j++){
                if(array[j]<array[i]){
                    dp[i]=Math.max(dp[i],dp[j]+1);
                }
            }
        }
        Arrays.sort(dp);
        System.out.println(dp[dp.length-1]+1);
    }
}

2) 비교시 if(dp[i]<dp[j]+1)를 통해 비교하기 + 마지막에 Arrays.sort를 통해 max값 구하기

package s17_dynamic;

import java.util.*;
import java.io.*;

public class s01_11053 {
    public static void main(String[] args) throws IOException{
        BufferedReader br =new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int[] array = new int[N];
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        for(int i=0;i<N;i++){
            array[i]=Integer.parseInt(st.nextToken());
        }
        int[] dp=new int[N];
        for(int i=1;i<N;i++){
            for(int j=0;j<i;j++){
                if(array[j]<array[i] && dp[i]<dp[j]+1){
                    dp[i]=dp[j]+1;
                }
            }
        }
        Arrays.sort(dp);
        System.out.println(dp[dp.length-1]+1);
    }
}

3) 비교시 if(dp[i]<dp[j]+1)를 통해 비교하기 + dp 최댓값을 하나씩 비교해서 업데이트하기

import java.util.*;
import java.io.*;

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[] array = new int[N];
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        for(int i=0;i<N;i++){
            array[i]=Integer.parseInt(st.nextToken());
        }
        int[] dp=new int[N];
        for(int i=1;i<N;i++){
            for(int j=0;j<i;j++){
                if(array[j]<array[i] && dp[i]<dp[j]+1){
                    dp[i]=dp[j]+1;
                }
            }
        }
        //dp의 최댓값 찾기
        int max = -1;
        for(int i = 0; i < N; i++) {
            max = dp[i] > max ? dp[i] : max;
        }
        System.out.println(max+1);
    }
}

---

이와 비슷한 문제

18353번: 병사 배치하기

 

백준 18353(병사 배치하기) - Python(파이썬) - LIS,다이나믹