컴공 일기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를 선물하세요.
-
50억 갖기vs연대의대 24
둘중 택하라고 하면 어디? 전 전자ㅋㅋ
-
언매 94 미적 88,.. 영어 95 국사 33.. 물리 50 지구는 32분에 45...
-
재밋겟다
-
캬오오오오오오오오오오 크르르르르르르르르르르
-
링크트리같은 미니 랜딩페이지 만들고 있는데 투표좀 부탁드립니다 (투표기능 붙여서...
-
2025 3월 학평 1번은 지수법칙 그냥 계산만 해주면 답이 5네요 2번은...
-
올해 고2입니다 고1때는 꿈도 없었고 부모님이 이과 진학을 희망해서 선택과목을...
-
시설 어떤가요.. 화장실 깨끗한가요??
-
근데 걍 아무것도 열심히 안해가지고, 딱히 울 일이 없는 것이엿음
-
맛있나...? 술담배 거의 안 하는 대신 커피는 좋아하는듯
-
오르비 안녕 잘있어 10
이러면 사람들이 댓글에 가지마 ㅠㅠㅠ 이렇게 써줌?
-
말랑P 5수선언문 씹 ㅋㅋㅋㅋ
-
오케이 3
오르비 빙고 '휴릅하거나 탈릅한적 있음' 채웠고 ㅋㅋ
-
흠..
-
눈치보이네 10
일상글 뻘글 쓰고싶은데 잘못한게 있어서
-
힘들어서 돌아옴 10
나도 허리찌짐하면서 돈 벌고 싶다
-
더어 울어라~~ 2
젊은 인생아~~
-
오르비 안녕히계세요 12
짧은 시간이었지만 정말 많은 분들과 좋은 이야기 나누었습니다 입시 하다가 힘들면...
-
진짜 어디가셨지
-
수능경제 질문 5
기업의 이윤 -> 총수입 - 총비용 가계의 이윤 -> 경영을 대가로 받는 소득이며...
-
기하하하학 글이 다 없어졌네..
-
소신발언은 사회적 지위가 있는 사람들이 하는거기때문에 소심합니다..
-
어떻게 해야 저 사람의 마음을 나에게 향하게 만들 수 있을까 으흐흐으악악
-
. 4
-
아~ 사람은 괘씸해
-
통사 이다지 인강을 들을지 말지 고민입니다 제가 09라서 수능 과목도 통사다보니.....
-
플래너 올리기 2
좋은분들이 관심가져주셔서 작심삼일인 제가 벌써 공부기록 올린거 연속 20일됐어요...
-
먼가 맛이 보장 되는 느낌임
-
명령이다
-
지2가 더 쉽다 ㅅㅂ
-
근데 그렇게 되면, 수험생 커뮤니티인 오르비의 존재 의의는 어떻게 되는 것임
-
이제 그만 손 내려도 될까요 여러분 저 반성 많이 했습니다 미워도 기회 힌번 더 주세요
-
첫 칼럼 많관부 1
[칼럼] 국어 노베이스를 위한 독서 읽기 https://orbi.kr/00072564482
-
기출문제집 추천 3
지금 스블이랑 4규 시즌1 끝나가고. 기출책을 버려서 다시 사야될 거 같아서 그런데...
-
대치동 맛집 2
그냥 한티옥이라고 아 ㅋㅋㅋㅋ
-
자꾸 문제에서 한두개 틀리네요 하…..뭐가문제지
-
누구나. 자유롭게활동하는. 오루비. 괜히. 설래는맘. 품고.여사님들괴롭히지맙시다....
-
작년(고3 때)엔 오르비 등 온갖 수험생 커뮤니티 돌아다니면서 자작 수학 문제나...
-
~가 뒷북 아니다 주장하는 사람한테 내가 헤당 문제 변형해서 던져주면 대부분 세련되게 못풂
-
[2014 예비 A형 21번] t=2에서의 미분가능성을 정의로 풀면 insight가...
-
시간이 없다.. 3
1년만에 학부 과정을 떡쳐버리고 싶은데 시간이 없네ㅡㅡ
-
오르비 지겹다 8
더는 설레지 않는다
-
고1인데 수학말고는 뭐 사야할지 모르겠네요 전부 다 독학으로 합니다
-
메타 돌려야지
-
이성한테서 나면 좋겠는 향 그런 거.. 저는 머스크 좋아해요!
-
넷플도안돼…… …. ㅜㅜ
-
ㅋㅌㅋㅋㅋㅋ
-
상위권 코스가 박광일 강윤구 오채은 이 있긴하네 국어 보강이 컸다 하지만
-
지금 고딩이면 미리미리 라인 따는 연습하셈 친커튼만 유지해도 굉장한 매력이 될 수...
이분탐색으로도 풀어보세요
넵 선생님!