컴공 일기255
게시글 주소: https://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)
유익한 글을 읽었다면 작성자에게 XDK를 선물하세요.
-
물화를 선택했다는거부터가 사탐 알래르기가 있을 확률이 있음
-
3칸부턴 스나인걸로 아는데 4칸 어떻나요? 많이 붙는 편인가요
-
걍 아이들이 너무 귀여워서 주변에 아가야들이 있으면 귀여워할수밖에 없는 병 걸림
-
의무병 질받 12
자대 배치 전임
-
오사카의 아침 10
나름 따뜻
-
-
얼버기 4
ㅈㄴ 잘 잤디 ㅋㅋㅋㅋ 개운하노
-
명지대식 837 이과중 낮은 과 ㄱㄴ? ㅈㅂ요
-
수리논술 전범위여도 거의 수1,2,미적만 나오는 학교도 있나요? 1
제곧내입니다~~
-
난 왜 몰랐지
이분탐색으로도 풀어보세요
넵 선생님!