반응형
부분수열
-
백준 11053 - 가장 긴 증가하는 부분 수열백준 algorithm 2020. 5. 9. 12:42
=> DP 문제이다. => 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 문제이다. => 수열 A =[10, 20, 10, 30, 20 ,50] => 가장 긴 증가하는 부분 수열 A = [10, 20, 30, 50] => D[N] : A[i] 를 마지막으로 하는 가장 긴 증가하는 부분 수열의 길이 => D[i]는 A[i]를 반드시 포함하여야 한다. => 위의 그림을 보면 어떤 방식으로 이루어지는지 알 수 있다. **가장 긴 증가하는 부분 수열 구하는 알고리즘 for(int i=0; i N; for(int i=0; i> A[i]; } int D[N]; for(int i=0; i