[알고스팟/ALGOSPOT] 15. LIS

안녕하세요~ 알고라파덕입니다~

이번 문제는 동적 계획법 관련 문제입니다.

동적 계획법은 처음 주어진 문제를 더 작은 문제들로 나눈 뒤 각 조각의 답을 계산하고, 이 답들로부터 원래 문제에 대한 답을 계산해 내는 방법입니다.

LIS 

문제

어떤 정수 수열에서 0개 이상의 숫자를 지우면 이 수열의 부분 수열 (subsequence) 를 얻을 수 있다. 예를 들어 10 7 4 9 의 부분 수열에는 7 4 9, 10 4, 10 9 등이 있다. 단, 10 4 7 은 원래 수열의 순서와 다르므로 10 7 4 9 의 부분 수열이 아니다.

어떤 부분 수열이 순증가할 때 이 부분 수열을 증가 부분 수열 (increasing subsequence) 라고 한다. 주어진 수열의 증가 부분 수열 중 가장 긴 것의 길이를 계산하는 프로그램을 작성하라.

어떤 수열의 각 수가 이전의 수보다 클 때, 이 수열을 순증가 한다고 한다.

입력

입력의 첫 줄에는 테스트 케이스의 수 C (<= 50) 가 주어진다. 각 테스트 케이스의 첫 줄에는 수열에 포함된 원소의 수 N (<= 500) 이 주어진다. 그 다음 줄에 수열이 N개의 정수가 주어진다. 각 정수는 1 이상 100,000 이하의 자연수이다.

출력

각 테스트케이스마다 한 줄씩, 주어진 수열의 가장 긴 증가 부분 수열의 길이를 출력한다.

예제 입력

3
4
1 2 3 4
8
5 4 3 2 1 6 7 8 
8
5 6 7 8 1 2 3 4

예제 출력

4
4
4

(출처 : https://algospot.com/judge/problem/read/LIS)

어떠한 수열이 주어졌을 때 부분 증가 수열 중에서 가장 긴 부분 증가 수열의 길이를 구해야하는 문제입니다. 

3 1 2 4 7 5 6 8 10 이라는 수열이 만약에 주어진다면 이 수열의 최대부분증가수열은

1 2 4 5 6 8 10이 됩니다. 

그렇다면 어떻게 이 문제를 동적계획법으로 해결을 해야 할까요??

먼저 이 LIS문제의 특성을 찾아봅시다. 

첫 번째 특징은 수열의 시작점이 어느 곳에서나 가능하고 수열의 마지막 또한 어느 곳에서나 가능합니다.

두 번째 특징은 수열의 어느 위치에서 최대 부분 증가수열을 구할 때 항상 그 전에서 현 위치까지의 최대부분 증가수열을 가지고 갈 수 있다는 것 입니다.

이 특징을 이용하여 2차원 배열로 그 전단계의 정보를 저장한다고 생각하면

     3  1  2  4  7  5  6  8  10

3   1  1  1  2  2  2  2  2  2    -> 3을 시작점으로 할 때 한 칸 이동 

1   1  1  2  2  2  2  2  2  2    -> 1을 시작점으로 할 때 한 칸 이동

2   1  1  2  3  3  3  3  3  3    -> 2을 시작점으로 할 때 한 칸 이동

4   1  1  2  3  4  4  4  4  4    -> 4을 시작점으로 할 때 한 칸 이동.

7   1  1  2  3  4  4  4  5  5

5   1  1  2  3  4  4  5  5  5

6   1  1  2  3  4  4  5  6  6

8   1  1  2  3  4  4  5  6  7

10 1  1  2  3  4  4  5  6  7  

점화식 : data[i] < data[j] -> if(sum[i][i] + 1 > sum[i-1][j])

sum[i][j] = sum[i][i] + 1;

else 

sum[i][j] = sum[i-1][j];

  else

     sum[i][j] =  sum[i-1][j];

맨 마지막 줄에서 가장 큰 값을 찾아낸다.