[백준 11053] 가장 긴 증가하는 부분 수열
https://www.acmicpc.net/problem/11053 해설 이번 문제는 흔히 LIS 라고 불리는 가장 긴 증가하는 부분 수열 문제이다. 예제인 10, 20, 10, 30, 20, 50으로 풀이를 해보겠다. 일단, 여기서의 답은 10,20,30,50 으로 4이다. 10 20 10 30 20 50 1번 1 2 " 1 2 3 " 1 2 1 4 " 1 2 1 3 5 " 1 2 1 3 2 6 " 1 2 1 3 2 4 이것만 보면 이해가 되겠는 가? 이제 천천히 설명해보겠다. 1번은 첫번째인 10까지의 부분 수열이 얼마나 나오는 지 구하는 건데, 1번은 10만 비교하니 1이다. 2번은 20까지 부분 수열을 구해보는 건데, 10, 20 총 2이다. 3번은 10까지 부분 수열을 구하는 건데, 10 총 1..
2020. 3. 30.
