[인프런 자바/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 (부분증가수열 최대 길이)
문제의 답에 해당하는 dp[N]을 구하는 로직은,
1)dp 배열의 첫 번째 값(arr배열 첫번째 값의 부분증가수열 최대길이)은 무조건 1이다.
2)dp 배열의 두 번째 값부터는
(1)arr 배열을 왼쪽 방향으로 모두 탐색하면서,
(2)해당 arr[j]가 arr[i]보다 작은 숫자인 경우,
(3)arr[j]에 해당하는 dp[j]의 값 중에서 가장 큰 길이 + 1이 dp[i]의 값이 된다.
자세히 설명하자면,
dp[5]값을 구하기 위해서,
(1)arr[4], arr[3], arr[2], arr[1]을 모두 탐색하면서(arr[5] 기준 왼쪽 방향),
(2)해당 arr배열 값이 arr[5]보다 작다면(arr[2]=3, arr[1]=5는 arr[5]=6보다 작기 때문에 탐색 실시!) ,
(3)해당 dp배열 값 중에서 가장 큰 길이(dp[2]=1, dp[1]=1이므로, 1)에 1을 더한 값이 dp[5]의 값(2)이 된다.
마찬가지로 dp[7]의 경우,
(1)arr[6]부터 arr[1]까지 탐색하며,
(2)arr[7]인 9보다 작은 값을 가진 배열에 대한 dp배열 값 중,
(3)최대길이가 가장 큰 수(dp[4]=3)에 1을 더한 4가 dp[7]이 된다.
풀이
Bottom-up(바텀업)으로 해결
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
// 입력되는 숫자를 담아주는 배열
static int[] arr;
// 동적 계획법 활용 배열
static int[] dp;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
// 입력되는 데이터의 수 N(3≤N≤1,000, 자연수)
int N = Integer.parseInt(st.nextToken());
// 배열 초기화
arr = new int[N+1];
dp = new int[N+1];
// 첫번째 값 초기화
// 하나의 값인 경우, 무조건 부분증가수열의 최대길이는 1이다.
dp[1] = 1;
st = new StringTokenizer(br.readLine(), " ");
// 받아온 숫자를 배열에 입력
for(int i=1; i<=N; i++){
arr[i] = Integer.parseInt(st.nextToken());
}
// 예시 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 (부분증가수열 최대 길이)
System.out.println(solution(N));
} // end of Main
static int solution(int N) {
// bottom-up(바텀업) 방식 구현
// 정답 변수
int answer = 0;
// i는 2번째부터 N번째까지 탐색
// 예시 1의 경우, 3부터 7, 8, 6, 2, 9, 4까지 탐색을 의미
for(int i=2; i<=N; i++){
// 최대값을 담는 변수
int max = 0;
// i번째 배열의 왼쪽 탐색
for(int j=i-1; j>=1; j--){
// 탐색조건 1)i번째 배열의 값이 j번째 배열보다 큰수인 경우
if(arr[j]<arr[i]){
// 탐색조건 2)j번째 부분증가수열의 최대길이가 현재의 최대값 보다 큰 경우,
if(max < dp[j]){
max = dp[j];
}
}
// i번째 부분증가수열의 최대값은,
// i번째보다 왼쪽에 있는 arr 배열의 값 중에서,
// arr배열의 숫자값이 arr[i]보다 작고,
// 부분증가수열의 최대값(dp배열값)이 가장 큰 경우보다 +1이다.
dp[i] = max + 1;
// 현재까지 부분증가수열의 최대값 중, 가장 길이가 긴 값을 answer에 넣는다.
answer = Math.max(answer, dp[i]);
}
}
return answer;
} // end of solution
} // end of Main