오늘 풀어볼 문제는 백준 11053번 문제 "가장 긴 증가하는 부분 수열" 이다.
문제
수열 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의 가장 긴 증가하는 부분 수열의 길이를 출력한다.📌첫 번째 시도📌
그냥 간단하게 for문 2개를 넣고 배열 안에 값들은 하나씩 비교를 해서 증가를 한다면 카운트를 계속 1씩 올려서 최종적으로 가장 큰 값을 출력하는 방향으로 코드를 작성했다.
package sliver2.b11053;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt(); // 개수 입력 받기
int[] array = new int[N]; // 배열
for (int i = 0; i < array.length; i++) {
array[i] = sc.nextInt(); // 베열 입력 받기
}
int resultMax = 0; // 최종 큰 값
for (int i = 0; i < array.length; i++) {
int subMax = 1; // for문에서 부분적으로 큰 값
int indexValue = array[i]; // i번째 인덱스 값
for (int j = i + 1; j < array.length; j++) {
if(indexValue < array[j]) {
subMax++;
indexValue = array[j];
}
}
if(subMax > resultMax) {
resultMax = subMax;
}
}
System.out.println("resultMax = " + resultMax);
}
}
예제에서 제출한 문제에선 정상적인 값이 나왔는데.. 답은 틀렸다고 한다...🥹
예제 문제가 하나 뿐이라서 어디서 문제가 생긴지 찾을 수가 없어서.. 구글링을 해보았다.
일단 이 문제는 DP로 접근해야 한다는 것을 깨달았다.
코드를 다 지우고 다시 DP 방식으로 짜보겠다..🥹
📌두 번째 시도📌
package sliver2.b11053;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt(); // 개수 입력 받기
int[] array = new int[N+1]; // 배열
int[] dp = new int[N+1]; // DP
for(int i=1; i<N+1; i++) {
array[i] = sc.nextInt();
dp[i] = 1; // dp 초기화
}
int resultMax = 1;
for(int i=1; i<N+1; i++) {
for(int j=1; j<i; j++) {
if(array[i] > array[j]) {
dp[i] = Math.max(dp[i], dp[j]+1);
}
}
resultMax = Math.max(dp[i], resultMax);
}
System.out.println(resultMax);
}
}성공했다..
오로지 내 힘으로 성공한 것은 아니지만.. 아직 알고리즘 입문하는 단계니깐 문제 유형별로 어떤 알고리즘을 써야하는 지 판단이 안 설 때가 많다.
그래서 일단은 구글의 힘을 당분간은 빌려서 알고리즘 문제에 익숙해지는 데에 초점을 둬야겠다.
두 번째 시도 방식 또 간단하게 풀긴 했다.
dp라는 배열을 만들어서 일단 가장 긴 수열은 최소 각각 인덱스마다 "1"이므로 dp를 모두 1로 초기화를 해주었다.
그 후 이중 for문을 통해 돌리면서 dp[i] 기준으로 array[i] > arrary[j] 가 성립된다면 dp[i] = Math.max(dp[i], dp[j]+1); 라는 결론을 지어주었다.
여기서 하지만 문제가 더 있다..
Scanner를 사용해서 그런지 컴파일 속도가 너무 느리다..
그래서 속도 향상을 해주는 코드 또한 한 번 더 작성해 볼 것이다.
📌세 번째 시도📌
속도를 올리는 방법은 Scanner를 사용하지 않고 BufferedReader와 StringTokenizer를 사용해주면 된다.
package sliver2.b11053;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine()); // 개수 입력 받기
int[] array = new int[N+1]; // 배열
int[] dp = new int[N+1]; // DP
StringTokenizer st = new StringTokenizer(br.readLine());
for(int i=1; i<N+1; i++) {
array[i] = Integer.parseInt(st.nextToken());
dp[i] = 1; // dp 초기화
}
int resultMax = 1;
for(int i=1; i<N+1; i++) {
for(int j=1; j<i; j++) {
if(array[i] > array[j]) {
dp[i] = Math.max(dp[i], dp[j]+1);
}
}
resultMax = Math.max(dp[i], resultMax);
}
System.out.println(resultMax);
}
}정상적으로 코드가 작동하고 아래 사진을 보면 시간이 반이나 줄은 것을 확인할 수 있다.
