[백준] 11053번 가장 긴 증가하는 부분 수열 JAVA (자바) 풀이

문제 11053번 

 :  수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성

    예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우, 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.

 

https://st-lab.tistory.com/137

 

각 dp[] 의 길이들은 다음 부분 수열을 의미하는 것이다

 

출처 https://st-lab.tistory.com/137

 

 

• dp[0] = 10
  이제 나온 것 {10} 중에 가장 길다 = 1
  
  
• dp[1] = 20
  이제 나온 것 {10, 20} 중에 가장 길다 = 2
  
  
• dp[2] = 10
  이제 나온 것 {10, 20} 중에 10까지는 길이가 1밖에 안된다
  
  
• dp[3] = 30
  이제 나온 것 {10, 20, 30} 중에 가장 길다 = 3
  
  
• dp[4] = 20
  이제 나온 것 {10, 20, 30} 중에 20까지는 길이가 2밖에 안된다
  
  
• dp[5] = 50
  이제 나온 것 {10, 20, 30, 50} 중에 가장 길다 = 4 

 

[입력]

 :  첫 줄에 수열 크기 N (1 ≤ N ≤ 1,000)

    둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000)

 

 

[출력]

 :  첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력

[설명]

 

DP 알고리즘

: 이미 계산된 결과는 별도의 메모리 영역에 저장하여 다시 계산하지 않음으로서 수행 시간 단축시키는 방법

  DP 구현 방법은 일반적으로 Top-down(하향식)과 Bottom-up(상향식)으로 구성된다

 

1) Top-down(하향식)

     하위 문제를 재귀적으로 호출하여 해결함으로서 상위 문제를 해결하는 방식
     이 때 해결해놓은 하위 문제를 저장해 놓기 위해 Memoization사용

 

public class Topdown {
	static int[] dp;
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		dp  = new int[n+1];
		System.out.println(fibo(n));
		
	}
	
    // Top-down
	static int fibo(int x) {
		if( x ==1 || x==2) return 1;
		if(dp[x] != 0) return dp[x];
		dp[x] = fibo(x-1) + fibo(x-2);
		return dp[x];
	}
}

 

2) Bottom-up(상향식)

 

    하위에서부터 문제를 먼저 해결하고 얻어진 값들을 이용해서 상위 문제를 해결해나가는 방식

    반복문을 사용해서 구현하고 문제의 결과 값을 저장하는 리스트는 DP 테이블이라 부른다

    

public class Bottomup {

	static int[] dp;
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		dp  = new int[n+1];
		
		System.out.println(fibo(n));
	}
	
    // Bottom-up
	static int fibo(int x) {
		dp[1] =1;
		dp[2] =1;
		for(int i=3; i<x+1; i++) {
			dp[i] = dp[i-1] + dp[i-2];
		}
		return dp[x];
	}

 

 

 [코드]

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
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[] seq = new int[N];
		int[] dp = new int[N];
		
		StringTokenizer st = new StringTokenizer(br.readLine()," ");
		
		for(int i = 0; i < N; i++) {
			seq[i] = Integer.parseInt(st.nextToken());
		}
		
		for(int i = 0; i < N; i++) {
			dp[i] = 1;
            
			for(int j = 0; j < i; j++) {
		    
				if(seq[j] < seq[i] && dp[i] < dp[j] + 1) {
					dp[i] = dp[j] + 1;	
				}
			}
		}
		
		int max = -1;
		for(int i = 0; i < N; i++) {
			max = dp[i] > max ? dp[i] : max;
		}
		System.out.println(max);
		
	}
 
}

 

 

 [해설]
     

 :  int N = Integer.parseInt(br.readLine()); 첫째줄 수열크기 N 입력
    int[] seq = new int[N];  둘째줄 수열 입력
    int[] dp = new int[N];  dp 설정 

 :  for(int i = 0; i < N; i++) {
         seq[i] = Integer.parseInt(st.nextToken());  수열 차례로 입력받기
    }

 :  for(int i = 0; i < N; i++) {  dp 배열 공간 만들기
         dp[i] = 1;  무조건 1부터 길이가 측정되므로 1로 모두 초기화
     

         for(int j = 0; j < i; j++) {  0 ~ i 이전 원소들 탐색
             

             if(seq[j] < seq[i] && dp[i] < dp[j] + 1) { 
                  dp[i] = dp[j] + 1; // j번째 원소의 +1 값이 i번째 dp가 된다.
             }

         }

   }

  :  int max = -1;  max값 초기화
     for(int i = 0; i < N; i++) {  최대길이 탐색
           max = dp[i] > max ? dp[i] : max;  dp[i]가 max보다 크다면 max를 해당 dp값으로 변경
     }

 

 :  System.out.println(max);  출력

 

 

 

 

이제 풀어보러 갈께요 :)

 

 

https://www.acmicpc.net/problem/11053

11053번: 가장 긴 증가하는 부분 수열

 

* 독학으로 익히는 코딩이라 틀린 것이 있을 수 있습니다. 오류가 있다면 댓글을 통해 알려주세요. 감사합니다. *