산 넘어 산 개발일지

풀이 키워드 DP 이분 탐색 LIS LIS(최장 증가 부분 수열) 이분탐색에서 주로 나오는 LIS문제였다. DP랑 같이 합해져서 나오는 문제 중 자주 나오는 유형인 것 같다. 이런 LIS의 경우 방식은 다음과 같다. 1. List를 만들고 첫 번째 원소를 넣는다. 2. 다음 원소(Next)부터는 list의 맨 마지막 원소(Last)와 비교하며 조건마다 특정한 작업을 수행한다. (조건 1) Last = Next list 원소 중 Next와 같거나 Next보다 작으면서 가장 비슷한 원소의 바로 다음 원소를 삭제하고 그 자리에 Next를 넣는다. (가령, Last = 3 이고 List = [1, 2, 4]였다면 4자..