컴공 일기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를 선물하세요.
-
나름 성공한듯 ㅠㅠㅠㅠ 행복하군뇨
-
가족 다 불교인데 가톨릭대는 안된다.... 제발 과기대 살려주세요....ㅠ
-
고해성사 합니다 14
사실 치킨한마리에 치즈볼 두개씩이었습니다
-
아직 컨설팅도 안받았는데
-
지리덕후 올수 세지 집수능 41점 3등급 현장 올수 지2 47점 1등급
-
과제물 : 다음 두 요구사항에 대해 생각해 볼 것. 검사는 따로 안함. 1....
-
???:여고생의 봉긋한 엉덩이 모양의 그래프다(지수함수 그래프와 로그함수 그래프를...
-
300명 선발에 0
140등까지 최초합이면 뭐 어쩌란거니.................... 계속 4칸이네 진짜 하
-
야식 ㅁㅌㅊ 9
삼양라면에 햄 넣음
-
오사카교토제외 유명관광지도 같이 추천해줘
-
삼반수할말 0
올해 처음 수능공부 시작 올해 14112 언확생윤사문 국영탐은 자신있는데 .....
-
일단 물리 화학 생명 선택했는데 화학은 내신때만 할거 같고 물리 생명은 수능까지...
-
낮반 예정인데 허허..ㅠ
-
한완수 패키지 2
이거 1/20일 입고 예정이라던데… 그때까지 기다려야하는건가요..?
-
사문은 1개월 50 가능한데, 물리,지는 어떤가요? 4
50하려면 최소 몇달은 해야한다~ 이런거 잇나요?
-
ky라인은 특히
이분탐색으로도 풀어보세요
넵 선생님!