컴공 일기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를 선물하세요.
-
글 하나 쓰는데 1시간은 고민하고 씀 매우 큰 정성이 들어갔으므로 뻘글이 아님
-
본문에 두 질점(질량을 가진점)이 서로 끌어당기는 힘이 만유인력이다. 여기서 사실상...
-
내년봄에는나도연애를하면서이봄기운을즐기고싶구나
-
그립다 그리워 2
날 기하로 바꾸게한 요인 얘네가 사라짐
-
김범준이 수업중에 알려주는 수선 기울기로 길이 구하기나, 이차방정식 근의 차,...
-
낮술 ㅅㅂ 그만 멕여라 취한다…
-
아레나 ㄱㄱ 1
이따 한 1시쯤에
-
밀리면 ㅈ된다…!
-
은테달아볼래요
-
겐코 데나 아사다나~
-
조선 1호 트래퍼 문익점
-
해보자
-
누워있다 일어나보니까 제가 소가 됐어요 이를 어쩌죠?
-
저는 위켄드가 최애입니당 너무너무 띵곡도 많고 특유의 여운이 남는 느낌!?
-
병행 어떰? 한완수 끝내고 엔제 해야되나
-
미적분 문항 자유도가 확 올라가서 전범위를 구석구석 공부해야한다는 필요성을 학생에게...
-
쇼츠만 보던 동생이 결국 어휘력 독해력 싹다 박살나서 교과서를 못 읽는 것 보고...
-
금지어테스트 1
냥 쌤
-
고고
-
딩딩딩디리딩딩딩 how can i be homophobic 0
My bitxh is gay
-
네
-
근데 이해만 하면 안됨
-
설대상<<<일치률80퍼이상ㅇㅇ
-
전 별생각 없은데 금기시되는거 같아서 이미지가(인강아님) 긍금햐요
-
도와주세요
-
심지어 그때부터 영어가 너무 어려워서 돈주고 영어의 코드 사서 봤는데...
-
...
-
어떻게 푸시나요? 각거리로 푸시나요?
-
아니 요즘 3
사람들 피부 왜 이렇게 하얌?
-
정상화 1
-
한번도 경험해본적 없는 이질적인 이과풍 수행 너무 부담스럽군요
-
3옥도샵됐다싯팔 8
츠기노코이노 유쿠에와도코다잇
-
잇올 끝나고 폰 받았더니 삭제된 메시지 와있길래 물음표로 답장했더니 이틀째 안읽는...
-
시즌2 집모로 방금 했는데 독서론-언매-문학-독서 순으로 풀었는데 문학 겁나...
-
실전압축IQ 1
84
-
나시나요?? 다들
-
이유도 ㅇ알려주심 감사하겠습니다
-
수능이 끝난 뒤 놀아도 늦지 않아
-
공부글 안 올리는 이유 12
다 까먹음 데헷
-
포기.. 1
한번정도는 괜찮겠지..
-
나라 지킨 용사와 유족, 그 영웅들이 왜 숨죽여 살고 있나 1
[아무튼, 주말] 서해 수호의 날 실패한 취재기 “어렵네요.” “원하지...
-
연필통 ㄷ 본바탕 고민중인데 기출서 따로 있으면 연필통 안 사도 됨?
-
판에 인형들 쌓아 놓으면 밀려서 나오는 뽑기 기계? 그거 ㅈㄴ 쌓여있길래 했는데 좀...
-
날 향해 비웃은 사람들 23
꼭 강해져서 복수할거다 다음에 만날 땐 내가 비웃어주지 이 수모를 잊지 않을테다
-
조졌다 진짜 걍 한번만 안낼까
-
아오 2
이소라의 노래 쩔더라
-
내신 준비한다고 수특 본문 깜지하는데 소리 존나 나네;;
-
잔 원래 신체발모머시깽이 주의였는데 해보고 싶어졌음
-
무휴반수러인데, 아이디어 공통 들을라하거든요? 어느정도 기간동안 쳐내야하나요? 원래...
이분탐색으로도 풀어보세요
넵 선생님!