12015

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

이번에는 진짜 너무 어려웠다. 정답비율이 40%문제인데 다들 대단한거 같다. 물론 문제 자체가 기본적인 LIS유형중 한개로 쉽게 풀리지만 알지 못하는 상태에서 생각해 내기 굉장히 어려운거 같다. 따라서 나도 LIS를 공부하고 기본 코드로 풀이를 할 수 있었다. 우선 문제를 보자 문제는 간단하다. 수열이 주어지고 여기서 "최장 증가 부분 수열"을 구하면 된다. 내가 풀이를 쓰는 것보다 더 좋은 풀이가 있어서 고수님의 글을 참고하면 좋을것 같다. https://chanhuiseok.github.io/posts/algo-49/ 알고리즘 - 최장 증가 부분 수열(LIS) 알고리즘 컴퓨터/IT/알고리즘 정리 블로그 chanhuiseok.github.io 결론적으로 LIS의 풀이 방법은 2가지가 있다. 1. DP를..

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

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