Longest Increasing Subsequence 알고리즘

 

 

O(n^2) : https://www.youtube.com/watch?v=CE2b_-XfVDk

 

 

O(n log n) : https://www.youtube.com/watch?v=S9oUiVYEq7E

 

 

 

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

 

O(n^2) 방식으로 풀면 아래와 같은 java 코드를 얻을 수 있다.

timeout이 날 거라 생각했는데 의외로 안 나오고 통과가 되었다(?)

알고보니 n 이 1,000 까지밖에 없어서 O(n^2) 으로도 통과가 되었네.

만약 https://www.acmicpc.net/problem/12015 이 문제처럼 1,000,000 까지 주어진다면 아래 코드로는 통과 못 할 듯.

 

import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
		
		Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int val[] = new int[n+1];
        int memo[] = new int[n+1];
        for(int i=1; i<=n; i++){
        	val[i]=scan.nextInt();
        	memo[i]=1;
        }

        int max = 1;
        for(int i=2; i<=n; i++){
        	for(int j=1; j<i; j++){
        		int vi = val[i];
        		int vj = val[j];
        		if(vj<vi && memo[i]<memo[j]+1){
        			memo[i]=memo[j]+1;
        			if(max<memo[i]) max = memo[i];
        		}//if
        	}//for j
        }//for i
        System.out.println(max);
	}
}

 

코드 링크 : http://boj.kr/1f4024fc1efb49e5bd0f45b7098f44b0