블로그 이사 중입니다 >> gumgood.github.io

C++11 다이아몬드의 가치를 기준으로 LIS의 길이를 구하면 된다. 가치의 비교에 대한 해석이 이해하기 어렵다.요약하면, 무게도 작고 선명도도 높아야 가치가 높다.

- LIS(Longest Increasing Subsequence) : 최대 부분 증가수열- 수열에서 증가하는 순으로 고를 떄, 최대 길이를 갖는 수열을 말한다. (not unique) 설명이 굉장히 잘 되어있는 블로그가 있다. 여기도 괜찮다. 'LIS의 길이를 구하는 여러가지 방법이 있다. 시간 복잡도, 구현이 간단한지 등을 고려하여 문제에 맞는 알고리즘을 써야한다. 1. Dynamic Programming 구현과 역추적이 쉽다. 1차원 DP로 $(O^2)$에 해결할 수 있다. C++11 2. Binary Search 구현은 간단한 편이다. 다음과 같은 수행과정을 따른다. ① vector 하나를 생성한다. ② 수열 arr를 처음부터 돌면서 vector의 마지막 원소보다 - 큰 경우, vector에 pu..

C++11 LIS이긴 한데 1식 증가하는 Incresing Sequence를 찾아야 한다.해당 LIS를 찾으면 나머지 애들은 앞뒤로 순서에 맞게 보내주면 되기 때문이다. 1식 증가하는 LIS를 찾는 문제로서 O(n)에 쉽게 구현가능하다.무턱대고 LIS를 짜면 당황할 수도 있다.

C++11 [0 ,n-1] 열차에서 i번째 열차를 기준으로, [0, i-1]의 열차는 무시하면, [i+1,n]에서 - 작은 차들은 i번째 기차 뒤에 - 큰 차들으 i번째 기차 앞에올 수 있다. 이 경우, 추가 되는 순서는 Decreasing Sequence, Increasing Sequence이다. 즉, i로 시작하는 LDS, LIS를 구하는 문제가 된다. lower_bound로는 i로 시작하는 LIS 길이를정확하게 알 수 없으므로 DP를 n-1 ~ i순으로 채워나가면 알 수 있다.

C++11 LIS + 역추적n이 최대 100000이기 때문에 lower_bound로 LIS를 O(nlogn)만에 구한다.LIS문제로 바꿔주기 위해 입출력할 때 코드가 길어졌다. A와 B사이 위치가 주어지는데 이를 A기준으로 정렬하면 B의 LIS를 구하는 문제가 된다.여기서 다시 LIS에 속하지 않는 선을 골라 출력해야하기 때문에 코드가 더럽(?)다.

C++11 LIS 연습하기 좋은 날씨다