✨컴공주✨ [1052682] · MS 2021 · 쪽지

2024-12-20 23:27:03
조회수 177

컴공 일기255

게시글 주소: https://io.orbi.kr/00070728465


LIS(Longest Increasing Subsequence), 최장 증가 부분 수열의 길이를  


Dynamic Programming(dp) 관점에서 구할 때 짜본 코드입니다.

오랜만에 알고리즘을 다시 공부하니, 기본부터 복습하고 있네요.


예를 들면

100 2 50 60 7 8 9 12 13


이란 수열에서 최장 증가 부분 수열의 길이가 얼마가 되는가를 따지는 겁니다.


모르긴 몰라도 2, 7, 8, 9, 12, 13을 택하면 되겠군요. Length는 6인 것 같구요.


수열 내의 부분수열을 탐색해야 하는데, 이걸 “완전-탐색”하겠다고 하면 Dynamic Programming이 적법한

솔루션일 수 있습니다. 데이터의 개수가 더더욱 많아지게 된다면, DP로는 충분한 효율이 안나올 수 있는데, 그런 경우

이분 탐색기법을 응용합니다.

0 XDK (+0)

  1. 유익한 글을 읽었다면 작성자에게 XDK를 선물하세요.