컴공 일기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를 선물하세요.
-
ㅈㄱㄴ
-
메가스터디 물화생지. 배기범. 고석용 백호. 한종철. 오지훈. 들을 생각인데....
-
과를 그쪽으로 가보는것도 나쁘지않을지도..? 라는 생각이 들어요
-
점장인지 미친인지 최저시급도안주면서 원하는건 더럽게많네 아 최저도 못쓸거면 걍...
-
경영학과 가능한가 ㅠ 진학사에 추합권떠서 더 내려갈거 생각하면 불안한데
-
진짜 고민되네요 ㅠㅠ
-
근데 아직 0
학교별로 26정시모집요강 안나오지않았나? 과탐 가산점이 3퍼인지 5퍼인지 어케알아여...
-
진학사에서 1,2번 둘 다 5칸 뜨는데 이 정도면 무조건 추합이라고 봐도 될까요?...
-
눈오리좀 만들게 눈 5센치만 plz
-
도란도란 란도 최현준네 막내딸 최모닝 공주님의 생일입니다 많은 축하바랍니다 귀여우니까요
-
피자 먹을까 0
피자는 만들어먹기도 애매함
이분탐색으로도 풀어보세요
넵 선생님!