컴공 일기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를 선물하세요.
-
-
-
대성 19패스 1
지금 사는게 제일 이득인가요?
-
시대인재 수학은 7월 후부터는 모든 선생님들 다 공통,미적합쳐서 수업하시나요? 만약...
-
그래 죽어도 과탐 하라는거지 슈발
-
너무 고민되어 글을 써봐요ㅠㅠ 의료산업경영은 가천대 문과이구 저는 현재 가천대생...
-
성대야 믿는다 6
-
집은 수원근교 님들같으면 어디감?
-
물2 시작했는데 2
너무 재밌어서 공부비율 씹창남요….ㅋㅋㅋ
-
본인 고2 모고 32332 목표 인서울공대
-
이벤트 5
지금 머구 러셀 설명회에서 대문범 특정 가능
-
이걸 안다는 건 틀딱이라는 것
-
궁금
-
국어 못하면 약대가는거보다 연대 문돌이 되는게 훨씬 어려움
-
학벌로 만족을 살 수 없는 이유랑 같다 누구는 중경외시만 가도 뛸듯이 기뻐하는데...
-
독서는 김동욱 들을 건데 문학은 강민철 김승리 둘 중 누구 들을지 고민돼서요...
이분탐색으로도 풀어보세요
넵 선생님!