개발일지

개념 LIS(Longest Increasing Subsequence)는 배열이 있을 때 일부 원소를 고른 부분 순열 중, 각 원소가 이전 원소보다 크고 그 순열의 길이가 가장 큰 순열을 LIS라 하고 최장 증가 부분 순열이라고 한다. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다. 변형 문제로 LDS, 최장 감소 부분 순열이 있다. 작동원리 1. LIS라는 List를 만든다. 2. List가 EMPTY거나 제일 마지막 원소가 검사하는 원소보다 작은 경우 List뒤에 추가한다. 3. 검사하는 원소가 List 마지막 원소보다 작은 경우 lower_bound를 사용하여 찾은..