sunapollon 님의 블로그

최장 증가 부분 수열(LIS, Longest Increasing Subsequence)이란 말 그대로 원소가 n개인 배열의 일부 원소를 골라내서 만든 수열 중 증가 수열이면서 가장 긴 것을 의미한다. (각 원소가 연속일 필요는 없다) LIS와 관련된 백준 문제는 매우 많고, 다양한데 14003번 문제를 보면서 nlogn의 시간 복잡도를 가지는 LIS의 길이와 LIS 원본을 추출해내는 작업을 하는 코드를 만들어 볼 것이다.https://www.acmicpc.net/problem/14003 가장 간단하게 LIS의 길이가 얼마인지 풀기 위해선 DP를 이용해 n ** 2의 완전탐색을 하면 된다.dp = [1 for _ in range(N)] #이 dp는 수열의 길이를 담음, 수열의 길이는 최소가 1이므로 초기값..

https://jungol.co.kr/problem/1137https://www.acmicpc.net/problem/3487백준 사이트에선 문제가 영어로 되어 있지만 정올 사이트에선 한글로 문제를 볼 수 있다.위 문제는 2613 숫자구슬과 비슷한 아이디어를 가지고 있는 문제로 숫자구슬을 안 풀었다면 먼저 푸는 것을 권장한다. 문제에서 우리가 중요하게 봐야 할 것은 "연속된 권을 베껴써야 한다" 와 "답이 두 개 이상 있다면, 첫 번째 서기공이 할 일이 가장 작은 답을 출력한다. 그래도 두 개 이상 있다면, 두 번째 서기공이 할 일이 가장 작은 답을 출력하며, 그래도 두 개 이상 있을 경우 이런 식으로 반복한다" 이다.  만약 가능한 모든 페이지를 수를 하나씩 다 탐색한다면 시간이 매우 오래 걸릴 것이 명..