※개인 공부 목적의 정리글입니다.
이 글의 내용이 최선의 해답은 아닐 수 있습니다.
문제
수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.
예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.
입력
첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다.
둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000)
출력
첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다.
풀이
증가하는 각 수 들은 서로 연속되어 있지 않을 수도 있다. 이걸 어떻게 풀어야할까?
배열에서 어떤 수가 있으면 일단 현재 수가 증가하는 배열이 되려면 수열에 속한 이전에 나온 수가 현재 수 미만이어야 한다. 증가하여야 하므로 같은것도 안된다. 예시를 들면…
10 20 10 30 20 50: 증가 수열에 속하는 수 중 30을 기준으로 볼 때 이전에 나온 수는 20처럼 30미만이어야 한다.
10 5 30 30 20 50: 이런 식으로 기준인 30과 같은 수는 이전에 올 수 없다. 증가하지 않기 때문이다.
이 문제를 풀기 위해서는 배열을 한 번 훑는 것으로는 안된다. 숫자를 차례대로 기준으로 두면서 현재 숫자 이전에 나온 숫자들 중 증가하면서 이어질 수 있는 것들을 찾아야한다.
일단 dp라는 배열을 하나 만들어서 값을 저장할 것이다. 여기에 저장되는 값(숫자)는 arr[i]의 숫자를 기준으로 둔다면 dp[i]에 해당하는 값은 arr[i] 및 이전에 가장 길게 이어지는 증가 수열의 길이를 의미한다.
int N = Integer.parseInt(br.readLine());
String[] inputs = br.readLine().split(" ");
int[] arr = new int[N];
int[] dp = new int[N];
for(int i=0; i<N; i++){
arr[i] = Integer.parseInt(inputs[i]);
}일단 필요한 값들을 입력 받는다. 배열 arr에 입력된 수열을 순서대로 저장하고, 배열 dp를 초기화 한다.
dp[0] = 1;dp 배열의 첫번째 값은 1로 지정한다. 어차피 첫번째 숫자는 이전에 나온 숫자가 없으므로 증가 수열의 길이는 무조건 1이다.
for(int i=1; i<N; i++){
dp[i] = 1;
for(int j=0; j<i; j++){
if(arr[j] < arr[i] && dp[i] <= dp[j]){
dp[i] = dp[j] + 1;
}
}
}문제 풀이의 핵심 파트이다. 하나씩 알아보자.
첫번째 값은 이미 길이가 1인것을 알고 있으므로 두번째 값부터 기준을 잡으면서 본다.
기준 값의 dp값은 일단 1로 지정한다. 그리고 수열의 첫번째 값부터 현재 기준값 이전까지의 값을 다시 순서대로 확인한다.
만약 이전 값이 현재값 미만이고 이전 값 까지의 증가 수열 최대 길이가 현재 까지의 증가 수열 최대 길이 이상이면, 현재 수열 까지의 증가 수열 최대 길이를 이전 값의 길이에 +1을 해준다.
이 말의 뜻은 곧 그 이전 값 다음에 현재 수가 오는 것으로 수열을 만들겠다는 뜻이다.
Arrays.sort(dp);
sb.append(dp[N]);위 반복문을 모두 돈 후에는 dp 배열에서 가장 큰 값을 출력하면 된다.
댓글