주어진 어떤 수열에서 순서대로 증가하면서 커지는 가장 긴 수열
LIS를 찾아내는 다양한 방법을 생각하고 만들어낼 수 있지만 재귀적 문제해결사고를 활
용할 수도 있다.
1. k번째 위치를 마지막으로 만들어질 수 있는 LIS의 길이를 solve(k)라고 하자.
2. 그렇다면 solve(k)는 그 이전의 solve(k-1), solve(k-2), solve(k-3), … , solve(3), solve(2), solve(1)들의 길이에 1을 더한 것이라고 생각할 수 있다.
'Algorithm > Etc' 카테고리의 다른 글
[DFS] 돌다리 건너기(p.239) (0) | 2020.08.31 |
---|---|
[DFS] 좋은 수열(p.226) (0) | 2020.08.31 |
[DFS] 저울 추 (0) | 2020.08.26 |
배낭 문제 (0) | 2020.08.10 |
오른편 절단 가능 소수 (0) | 2020.08.10 |