가장 긴 증가 부분 수열 2

백준 12015 풀이 (가장 긴 증가하는 부분 수열 2, LIS, 이분탐색)

이 문제는 어떻게 접근해야하나 LIS를 찾다가 거의 정답을 알게되서 거의 꽁으로 푼 문제다. 그러나 이해하는데에 상당히 어려웠기 때문에 내 수준에서 이해한 풀이를 적어보겠다. 이전에 LIS문제가 있었는데 그건 다이나믹 프로그래밍으로 풀었던 문제였다. guccin.tistory.com/38 백준 11053 풀이 (가장 긴 증가하는 부분 수열, LIS) 요것은 머랄까 LIS인데, 나도 처음 들어봤다. 애당초 알고리즘 수업도 들어본 기억이 없기 때문에 무엇을 듣던지 생소하다. 그래서 맘편히 구글링을 해보았다. LIS는 최장 증가 수열을 의미한다. L guccin.tistory.com 당시의 풀이 방법은 처음부터 i번째 시점에서 가장 많이 몇번째인지 정하는 방식으로 풀이를 진행한다. 이렇게 설명하려니 상당히 어..