컴공 일기255
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를 선물하세요.
-
이것때문에 머리가 너무 아파서 잠이 안옴 살려달라노
-
맞춰봥><
-
오랜만에 롤 켰는데 10
현타오고 우울해짐 잘하는 게 롤밖에 없는 인생.. 재수하면 괜찮겠죠..
-
헤헤헤헤헤ㅔㅔ 2
개마싯겟따
-
서로 마음만 맞으면요 진지하게 궁금해요..
-
자그마치 완두찹쌀떡빵임
-
자자 1
들어가라
-
올해 사범대 2
경쟁률 어떻게 될까요? 넣을 생각이 있는데 교육공학과나 교육학부가 인기 많을까 걱정…
-
문득 5
풀지못한 수학문제들이 아른거릴때
-
개꿀
-
가 아닌 거 아시나요? 요즘 애들은 뱃길따가 87k로 배운답니다 네
-
잠이 안와.. 5
야식이나 먹자..
-
감사합니다
-
이게 뭐 하는 인생이냐
-
걍 시간대를 생활패턴에 맞추기로함 5월에도 생활패턴 개망한 상태로 유럽갔다왔는데 그...
-
한양대에리카 비메이저공대 (전과) vs 중앙대다빈치 원하는과 전자는 교통이 매우...
-
수면패턴 망함요 4
4시에 눕고 뒤척이다 6시 숙면 무한반복
-
막날에 넣어야지
-
-
진학사 3칸 0
지거국 3칸 뜨면 가능성 거의 없는건가요?..ㅠㅠ
-
연경은 조금 불안한데 여러분이라면 어디까지 써보시겠어요 가나다군 다 추천해주시면...
-
잘자 16
진짜잠뇨
-
하다못해 똥이라는 주제만으로 하루종일 똥글 싸시는 분도 있는데 재밌는 인생은...
-
휴릅 15
고마웠던 사람들에게 덕코주고 물러남 ㅂㅂ
-
10 10
9…8….7….
-
스나할 곳 좀 찾아봤는데 도무지 각이 안 나오네용
-
갑자기 이과지만 로스쿨 염두에 두고 원서 쓰고 싶은데 한양대는 공대 못쓰는...
-
선생님 얼굴 뒤에 저거 구찌 아닌가
-
진학사 3칸 0
대형과이고 표본상 최초합선인데 불안/3칸 뜨네요 작년 지원자 수 감안하면 표본이...
-
난 사실 음악을 해보고 싶은데 재능이 없는 관계로…
-
사람도 많겠져…?
-
메디컬은(의치한) 아무리 펑나도 차이가 별로 안나는데 설대는 펑크나면 확 나나요?...
-
섹스하지마 2
섹스하지말고 싸워!!!
-
-
그냥 접을까 두 번 연속으로 8등 박으니까 현타 씨게오네
-
썰1 3
너무 졸려영
-
닉 번역기돌려본적 있으심?
-
아 잠 존나 안 오네 시발
-
난 아직도 올해 다녔던 독재 사감쌤을 잊지 못함 너무 내스탈이심 나이는 40대...
-
프사를 바꿨어요 0
누군가가 프사 바꾸면 밥 사주신댔어요 뭔지 알아보시는 분께 1000덬
-
궁그매요
-
고조원관건 다 그냥 어 끝자락 의대 갔네 싶은데 제주의 가면 그렇게 의대가...
-
자야되는데 0
생활패턴이 너무 이상해졌어요
-
좆됐다
-
저 재수못해요 진짜 여기 올해 꼭 가고싶어요 제발 지금 이틀째여섯칸이라 손발이...
이분탐색으로도 풀어보세요
넵 선생님!