알고리즘
[알고리즘 문제해결전략] LIS - Longest Increasing Sequence
LIS 문제를 해결하는 방법은 두 가지가 있다. 1. 수열 중 LIS를 만족하는 모든 경우의 수 확인 + 메모이제이션 / 시간복잡도 (N^2) 2. LIS가 항상 순증가 한다는 특성을 활용한 방법 (길이가 i인 LIS 중 가장 유리한 LIS는 마지막 값이 최소인 LIS) / 시간복잡도 (NlogN) 1번 방식 [생각의 흐름] 1. 재귀 함수를 통해 모든 경우의 수를 구한다. 2. 부분문제로 정의 할 때 현재 수열에서(subsequence[startPosition]) LIS값을 구하는게 최적의 값 3. 메모이제이션을 통해 중복 된 계산을 제거 /* https://www.algospot.com/judge/problem/read/LIS */ #include #include #include using names..
