컴공 일기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를 선물하세요.
-
새로사기 아까운데
-
경희대 소융 2
장학 아직도 있나요? 안그럼 정시 장학 기준있나요?
-
짝사랑~썸탈때 듣는얘긴 재밌는데 연애 성공한 뒤엔 듣기가 싫더라 염장질같아서
-
저번에 집에 누워있는데 갑자기 삼성카드에서 전화오더니 첫달 무료고, 월~~원에...
-
참고하시길
-
우웅
-
안녕하세요, 저는 청소년 창업동아리 연합회 운영진 이현준입니다. 저희 연합회는...
-
워낙 중요한 시설이라 외지인 입장에서는 김포공항부터 떠올리게 되는듯요
-
제발료ㅠㅠㅠ
-
인싸인 척 할 수 있음 ㄷㄷㄷ
-
아니 내가 며칠 후면 22살이라고?? 내가??
-
댓글로 어필해주시길
-
너가 성공하면 내가 만나줄게 이런 자기객관화못하고 능력남찾는 경우 많음
-
바쁠 수 있겠죠...?
-
4칸됐네... 0
죽어야하네...
이분탐색으로도 풀어보세요
넵 선생님!