컴공 일기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를 선물하세요.
-
역시내
-
일단 끌리는 이유 1. 넉넉한 표본과 난이도 2. 만에하나 의대성적이 나온다면...
-
세츠나오 카와시테야이바스리누케 야츠라노 스키오츠케
-
다시 자야겠다
-
고딩때도 친구들이랑 일부러 친해질려고 안했음 그래도 고딩때는 계속 붙어있으니까...
-
친구랑놀면오르비안함
-
사랑이 느껴지는 프레임 수...
-
설경 3
내신 6점대인데 설경이 가고싶어요 가능함??
-
수능 전날 새르비가 더많을듯
-
뭔가 멋있어요 이시대 마지막 남은 낭만 느낌
-
그게 가능할 리가 없잖아
-
온세상이 나를 상대로 거짓말 하는 기분이야
-
나이로 사수생은 두명 봄
-
의대 갈 사람이면 사실 과탐해도 상관없는거 아니가? 목표를 정하고 탐구를 결정하자
-
살이너무쪄서돼지됨
-
일반과라 휴학도 안해서 학교 다니는데 친구가없어서 오르비에 왔어
-
ㅇㅇ…
-
왼팔 개같이 아프네 12
아니 컵 하나 들다가 전완근 쪽이 뒤지게 아픔 뼈에서 통증 느껴진 건 ㄹㅈㄷ네
-
과팅 설레요 7
1학기에는 과팅 5번만 해볼게요
-
웅야
-
누구 추천하시나요 2정도고 지금 김범준 스블 듣고잇어요 작년 서바시즌에 엄소연t...
-
이젠 연고 낮 서성한하고 겹치는 거??
-
젠지가 제일 예쁘다더라 아.. 내눈엔 다 예뻤는데 한화는 좀 거시기 하다더라..
-
한문이싫어요 0
-
갑자기 궁금한 게 부정적분으로 함수를 정의할 수 있나? 2
그럼 함수 자체가 부정이란 건데, 걍 적분상수 +c 가 붙고 조건 한 개더 던져주면...
-
대학만 높이고 아무과나 ㄱㄴ 언 확 사탐 94 92 2 70 69 면 어디까지 가눙함?
-
단치 960.3 0
단치 960.3정도 였으면 붙었나요?
-
투과목중 2초 2
물2 생2 뭐가 낫나요?
-
막상 보면 짧은 거 같기도 하고
-
색 2
연 필 연 색 연 필 연 색
-
닉언 ㄴㄴ 10
ㄴㄴ
-
언매 강사 0
언매 강사 골라주세요!
이분탐색으로도 풀어보세요
넵 선생님!