백준 11053 가장 긴 증가하는 부분 수열

 수열 문제라 접근이 쉬워서 생각 난대로 했지만 역시나 실패.. 구글링 통해 이것이 다이내믹 프로그래밍(DP) 문제라는 걸 알았습니다.

 

DP 알고리즘 기법이란?

DP 알고리즘 기법은 이미 계산된 결과는 별도의 메모리 영역에 저장하여 다시 계산하지 않도록 설계함으로써 메모리를 적절히 사용하여 수행 시간 효율성을 비약적으로 향상하는 방법이다..

고로 재귀호출코드보다 높은 효율을 갖는 코드라고 한다. 그래서 나는 상향식 방법을 사용해서 접근하는 걸 깨달았다.

 

package codetest;

import java.util.*;
import java.io.*;

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); // Scanner 대신 사용 사용이유 앞 블로그에서 설명함

		int n = Integer.parseInt(br.readLine()); // bufferreder는 string형태로 받아오기때문에 int형으로 변환
		int arr[] = new int[n];// n크기만큼의 배열 생성
		int dp[] = new int[n];//dp 테이블

		StringTokenizer st = new StringTokenizer(br.readLine());

		for (int i = 0; i < n; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}

		dp[0] = 1; // 처음 껀 1임 첫빠따니깐

		for (int i = 1; i < n; i++) {
			dp[i] = 1; //1 로 초기화
			for (int j = 0; j < i; j++) {
				if (arr[j] < arr[i] && dp[i] <= dp[j]) {
					dp[i] = dp[j] + 1;//이전에 제일 큰값을 +1한 값을 넣는다 즉 i번쨰 수열일때 가장 긴 증가하는 부분 수열의 길이
				}
			}
		}

		int max = 0;
		   for(int i=0; i<n; i++)  {
			max = Math.max(dp[i],max ); // 두 인자를 비교하여 큰 값을 리턴함
		}

		System.out.println(max);
	}
}

그리고 Math max라는 걸 사용하기 전엔 쉘 정렬을 이용해서 max값을 구했었는데 시간 초과가 떠서.. Math 클래스에 있는 max 함수를 사용하여 max값을 구했더니 시간 안에 잘 되었다..ㅎㅎ 알고리즘은 자주 사용하는 클래스들이 정해져 있는 것 같다.. 잘 알아 놔야겠다