알고리즘
[알고리즘 문제해결전략] JLIS - 합친 LIS
[생각의 흐름] - 오답 1. 수열A와 수열B의 LIS를 구해 더한다 -> 위와 같은 로직이면 예제 {10, 20, 30, 1, 2} {10, 20, 30} 일 때 정답은 {10, 20, 30}으로 JLIS의 길이는 3이됨 (정답은 5) 2. 수열A와 수열B의 중복 된 수를 한 쪽 수열에서 제거 한 뒤 각각 LIS를 구해 더한다. -> 문제의 예제에서 정답은 나오나 코드 제출 시 오답나옴 -> 중복이 제거되어도 1과 같은 수열 케이스가 나오면 오답 [생각의 흐름] - 정답 1. 수열A와 수열B의 모든 수를 따지면서 LIS를 구한다. -> "수열A의 수를 선택하거나 수열B의 수를 선택하거나"의 부분문제로 정의한다. 2. cache사용을 위해 계산의 중복이 있는지 찾아본다. -> 예를들어 {1, 5, 9, ..
