LIS 알고리즘 (1)

LIS는 제목에서도 명시해놨듯이 수열중 증가하는 가장 긴 부분수열을 찾는 문제이다.

{1, 6, 2, 5, 7, 3 ,5}라는 수열의 Increasing Subsequece는 {1, 2}, {2, 5, 7}, {1, 2, 3, 5}... 등이 될 수 있다. 이 중에서 가장 긴 수열을 찾는 문제이다.

증가하는 수열을 찾기위해서는 앞에서부터 탐색후 값을 저장하여 누적시키는 방식으로 한다.

각각의 최장수열길이를 DP[n]에 저장한다.

#include <cstdio> #define max(a,b) ((a>b)?a:b) int main(){     int N;     int arr[1001];     int DP[1001] = { 1 };     int ans = 1;     scanf("%d", &N);     for (int n = 0; n < N; n++)         scanf("%d", &arr[n]);     for (int i = 1; i <= N; i++){         DP[i] = 1;         for (int j = 0; j < i; j++){             if (arr[i] > arr[j] && DP[i] < DP[j] + 1){                 DP[i] = DP[j] + 1;                 ans = max(ans, DP[i]);             }         }     }      printf("%d\n", ans);     return 0; } Colored by Color Scripter

cs

백준 11055 가장 큰 증가하는 부분 수열 https://www.acmicpc.net/problem/11055

       1965  상자 넣기                        https://www.acmicpc.net/problem/1965

       11053 가장 긴 증가하는 부분 수열 https://www.acmicpc.net/problem/11053

       1937  욕심쟁에 판다                   https://www.acmicpc.net/problem/1937
       2352  반도체 설계                      https://www.acmicpc.net/problem/2352
       11722 가장 긴 감소하는 부분 수열 https://www.acmicpc.net/problem/11722
       2643 색종이 올려놓기                 https://www.acmicpc.net/problem/2643
       11568 민준이의 계략                 https://www.acmicpc.net/problem/11568