LIS

[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번째 시점에서 가장 많이 몇번째인지 정하는 방식으로 풀이를 진행한다. 이렇게 설명하려니 상당히 어..

백준 2565 풀이 (전깃줄, 다이나믹 프로그래밍, LIS)

이번 문제는 코드를 다 짜서 돌렸는데 잘나오길래 고렇게 했더니 하도 안나와서 LIS를 다시 적용해서 풀게된 문제이다. 다음과 같은 그림이 존재하는 경우 겹치는 선을 제거하여 몇개의 선을 최소로 제거해야 겹치지 않게 되는지 구하는 문제였다. 처음에는 각 연결별로 겹치는 부분을 구하고 가장 겹치는 선이 많은 줄을 하나씩 제거하여 제거되는 선을 찾으려고 했다. 1. 각 라인별로 겹치는 선을 찾는다. 2. 최댓값을 구하고 해당 인덱스를 찾는다. 3. 해당 인덱스를 제거하는 경우 다른 라인들과의 겹치는 선을 갱신한다. 4. 만약 모든 값이 0이하인 경우, 몇개의 라인을 없앴는지 확인한다. line 1,8 3,9 2,2 4,1 6,4 10,10 9,7 7,6 cross 5 4 2 3 2 0 2 2 x 4 1 2 1..

백준 11053 풀이 (가장 긴 증가하는 부분 수열, LIS)

요것은 머랄까 LIS인데, 나도 처음 들어봤다. 애당초 알고리즘 수업도 들어본 기억이 없기 때문에 무엇을 듣던지 생소하다. 그래서 맘편히 구글링을 해보았다. LIS는 최장 증가 수열을 의미한다. Longest increasing Subsequence 라고 하는데 A = {10, 20, 10, 30, 20, 50} 가 존재하면 10, 20, 30, 50 이 가장 긴 수열로 존재한다. 그래서 이렇게 긴 수열이 무엇인지 찾아내는 알고리즘이다. dp로 푸는 방법과 다른 방법도 존재한다고 하는데 나는 다이나믹 프로그래밍인 DP를 연습하고 있기 때문에 DP로 풀어보았다. 10, 20, 10, 30, 20, 50 이 존재한다면 각 항목별로 dp를 저장해서 누적시키는 느낌으로 풀어야 한다고 생각했다. number 10..