컴공 일기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를 선물하세요.
-
LCK) Ep.1 이곳은 세상에서 가장 핫한 전장, 아레나입니다. | 아레나: 운명의 듀오 0
아니 치와와가 집밖을 나갔더니 순해졌요.. 평소에 보던 루시드가 아니야... 이건...
-
연대 언홍영 정시컷이 어느정도이려나요 올해는 다르겠지만 1
화작 미적 사탐 기준으로(한지사문) 미적 평백 98 그리고 영어1이라 했을때..?...
-
아니다 내일모레
-
대단하다
-
3등급정도로 만들면 기분 진짜 좋을듯 ㅋㅋ
-
이거 재밌다고 화학으로 갈아타면 안되겠죠? 그냥물어보는거임
-
쉽다 8
이지하다 이지해
-
기출 문제 풀 때 마더텅 사요 아니면 인강 듣는 쌤들 기출문제집 사요? 어떤게 더...
-
진짜 진짜 진짜 쉽지 않은 듯 작수 10틀 이하 정도의 실력자가 아니라면. 나도...
-
2025년 3월 6일(유튜브 업로드 일자) 모 강사 "증원이 된 것은 계속 가는...
-
공부량이 몇배인데ㅋㅋ
-
개학하고 숙제 다 쳐낼만 한가요?
-
다 잊 어 야만 해 요호오오
-
흠 왜 나만 이럴까
-
매삼문 매삼비랑 검더텅? 얘네 다 기출문제집인가요? 좀 더 괜찮은게 있을까요?
-
다들 샤인미 물어보시길래 아닛.. 전 기출도 이제 시작했는데...
-
뭐가 더 어려울까요?
-
-
나일어남뇨 4
-
존맛탱 배에서 꼬르륵 소리 나서 해주신거 같은데 다음엔 아침 든든하게 먹고 가아겠다..
-
발걸음이 가볍당 오늘 대충 해야지 불만있으면 짜르던가 에베베베
-
시@봉방거 11
몸 듸지게 아프네
-
23수능 확통3이고 26수능 확통1등급 목표입니다 3월까지 시발점이랑 수분감...
-
이건 왜이렇게 많이뜨는거고 내 글에 달린 댓글보려고 탑피드누르면 나오지도않고 나만이럼, ???
-
프세카)랭크매치 2
마스터입갤 히히
-
1 일하면서 과외 뛸수 있다 vs 2 그시간에 운동이나 더해라 1
돈벌이 급함 미국주식 사놓은거 요새 개같이 처박고 있어서
-
그래서 여자 과외쌤이라고 봐야함
-
학교다니니깐 공부하기시렁 ㅜㅜ
-
김범준 한번 들어보고 싶었는데 그냥 스블에서 문풀만 발췌수강해야하나
-
올해는 기대해도 되는 거지?
-
이렇게 하시나요 보통 국어도 주2회 2시간 하나?
-
애 책상에 앉혀놓기 <= 성적 무관 여자 과외쌤 선호 닥치고 성적 올리기 <= 성적...
-
선지 보다보면 띠용하는 선지가 있잖아.... 혼자서 헛소리하는 선지 찍으면 되는데....
-
대성 사려했는데 12월 종강 강의를 지금까지 밀렸다갈래 취소 ㅎ
-
아~ 알바하고싶다 10
-
님들 계약학과 어떤가요 19
메디컬보단 계약학과 합격하는게 더 가능성이 높을듯해서..
-
질문이 잇음 5
?
-
유씨면 안 됨 ㅋㅋㅋㅋㅋㅋ 유기범
-
호감도 max +1 달성
-
어렵다 0
어려운건 아닌데 어려운게 어려ㅇ러ㅓ러ㅕㅇ령령러ㅕㅇ로ㅓㅕㅇ러ㅕ
-
다시 맞팔구 8
젭알
-
영독연이랑 영어 이렇게 샀더니 엔제 한권값임 ㅆㅃ
-
작년에 학고 반수했는데 망했고, 쌩삼수/삼반수 생각하는데 성적대가 높지 않아...
-
키워드 지시어 로직 이 3개로만 푸는건가요? 키스로직 듣고있는데 순삽 지문은 뭔가...
-
핑계 이거 약간 핑크 닭이잖음 핑크닭 왜케 야함
-
항셍 치고올라가던데 흠...
-
종강해야지 0
곧이야
-
날씨 화창하다 0
봄이야
-
앞부분 뒤지게 까먹었네ㅋㅋㅋㅋ 앞부분 뇌절 오는 거랑 해서 개념 다 다시 복습하고 엠스킬 들어야지
-
잘 모름
이분탐색으로도 풀어보세요
넵 선생님!