bottom up 최대 부분 증가수열 (1) 썸네일형 리스트형 [인프런 자바/java] 3. 최대 부분 증가수열 _디버깅의 눈물 체크 포인트 1. 다이나믹 프로그래밍(Dynamic Programming, 동적계획법)을 이용 -큰 문제를 여러 가지 작은 문제로 나누어 해결해보는 DP를 이용했다. 예를 들어, 예시 1의 경우 1)첫 번째 값의 부분증가수열의 최대길이 = 1 2)두 번째 값의 부분증가수열의 최대길이 = 1 2)세 번째 값의 부분증가수열의 최대길이 = 2 ... 8)8 번째 값의 부분증가수열의 최대길이 = 2 를 가장 작은 경우의 수부터 구해보며 연산 과정을 추론하였다. 2. 부분증가수열의 최대길이를 구하는 로직 예시 1의 경우, 아래와 같이 표현할 수 있다. // index = 1 2 3 4 5 6 7 8 // arr[N] = 5 3 7 8 6 2 9 4 (입력된 숫자) // dp[N] = 1 1 2 3 2 1 4 2 .. 이전 1 다음
