컴공 일기255
게시글 주소: https://ui.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를 선물하세요.
-
근데 난 플레에 가고 싶다고 말했지
-
39점이면 4등급인데 물리39점 받으려면 공부 상당히 많이해야함
-
[고려대학교 25학번 합격] 합격자를 위한 고려대 25 단톡방을 소개합니다. 0
고려대 25학번 합격자를 위한 고려대 클루x노크 오픈채팅방을 소개합니다. 24학번...
-
08년생은 수시재수도 안락사 당한듯
-
과탐 과외하다 보면 여름방학 시즌에 연락 많이 오는데 1
그때마다 일찍 연락할껄 후회돼요.. 하는 애들 보면 너무 안타까움
-
광역자사고 졸업이라 내신이 6등급대인데 이건 수능을 거의 만점 받아도 못 넣을...
-
최원태햄 3
1.5회전에 무너지는 경우는 크게 없지만 페이스 좋아도 6,7회까지 끌고가기는...
-
방t는 강의가 한가지라 배t커리를 섞을까하거든요 배t로 가는분들 계신가요??? 어떤가요???
-
애매한 재능이 2
꿈이랑 걘 한패 널 죽일 enemy
-
성대랑 한양대식 변표 뜬거 이득인가요 손해인가요?
-
사탐가도 아 ㅆㅂ 하나 실수햇네+아 의문사!!!하고 수능때 개같이 2등급, 3등급...
-
다들 기를 쓰고 1지망 의대 쓰는게 신기하긴 함뇨 ㅋㅋ 25는 다를거 같아?
-
ㅇㄴ
-
제목그대로 수학 쉬운거 말고 4점부터 해서 킬러까지 옛날꺼 포함 다 있는 시중...
-
뭐 기수열외라도 시킴? 지들이 뭔데
-
N제가 왜 필요한지 바로 깨달았음요 디카프 사러감요...
-
그냥 내년엔 의평원 인증 탈락하는게 의대입장에선 유리할수도 있어 3
의평원 인증 탈락해버리면 아무리 정부에서 지랄지랄 해봤자 26학번 의대정원...
-
당신은 화석입니다 거기 아레나 10 호그마운틴으로 바뀐지 오래됨
-
생1기준 근수축 막전위 개념문제를제외한유전(14,15,17,18,19) 다틀려도...
-
여러분이라면 가나다 어케 써여?ㅜㅜ
-
찝찝해..
-
경북대 합격생을 위한 노크선배 꿀팁 [경북대 25] [교내식당안내] 0
대학커뮤니티 노크에서 선발한 경북대 선배가 오르비에 있는 예비 경북대학생, 경북대...
-
ㅈㄱㄴ
-
지방러는 잘가르치는 과탐 과외쌤 못구함
-
야잘알분들 컴온 5
최원태햄 장단점이 머임?
-
제발 고12 모의고사 수학 100 받고 내신 다 맞고 이랬다고 자기가 머리 좋다고...
-
6모 56233->12212 로올림 걍 그냥그냥 갈랬는데 막상 수능 이렇게 나오니까...
-
수리논술 전범위여도 거의 수1,2,미적만 나오는 학교도 있나요? 1
제곧내입니다~~
-
난 왜 몰랐지
-
휴학해서 바로 군대가실꺼면 어디로갈꺼임 ?? 카투사는 끝났고 공군은 나이때문에 좀...
-
투표 ㄱㄱ
-
스토브때 심우준 50억왜삼? 수비를잘해서?
-
화작 4 확통 5 영어 3 한지 3 사문 3 농어촌 정시로 인천대 독어나 불어 가능한가요?
-
칸수야 버텨라 1
롯데리아에서 하는 기도
-
오랜만에 왔는데 3
싸움이 한바탕 났었군뇨
-
근데 요즘은 자전이라는게 있어서..
-
조온나게 고이게 될 것 같아서 발작하는 건가
-
교대 아니면 쓸거 없고, 부모님은 교대 아니면 대학 안보내겠다고 하시는데.. 진짜...
-
십일워 중복조합 문제풀이 (3) 확률14강~17강 ※직접나열해보고 벤) 그려서...
-
현우진 드릴 4
드릴 수1,수2 일주일 안에 끝내는거 불가능일까요…?? 일주일 동안은 하루에 수학...
-
스초생멱구싶다 2
ㅜㅜㅜㅜ
-
50분정도 걸리는 거면 적당함?
-
* 자세한 문의는 아래의 링크를 통해 연락 바랍니다....
-
ㅅㅂ 수하 너무 노베라 쎈 해야하는데 4일동안쎈벅벅해야지
-
이유도 한번씩만 부탁드려요
-
헬스장 피티 4
등록 상담해볼까 뭔가 떨린다
-
오래된 생각이다.
-
참고로 고2 모고 4 시발점 수1 44일, 수2 56일 완강 예정 (Step1, 2...
-
그림 끼적이니 재밌어서 몇 개 더 만듦 히히
-
초등과외문의 들어왓는데 거절해야되나 애들이 싫은건 아닌데 어케 가르칠지 감도 안옴
이분탐색으로도 풀어보세요
넵 선생님!