[백준/java]11053. 가장 긴 증가하는 부분 수열

문제 링크 - https://www.acmicpc.net/problem/11053

🌱 문제

🌱 풀이과정

• 싸피 알고리즘 강의중 LIS 관련 내용을 복습하면서 풀어보았다.

LIS 알고리즘 - DB 이용

• 시간복잡도: 약 O(N^2)
  (정확히 따지자면 1+2+3+...+N = (N-1)*N/2의 시간복잡도를 가진다.)
• 자세한 풀이는 주석 참고

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

// 11053.가장 긴 증가하는 부분수열 
public class Main {
	static int N;
	static int arr[];
	static int cnt[];
	static int answer;
	public static void main(String[] args) throws IOException{
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		
		N=Integer.parseInt(br.readLine());
		arr=new int[N]; // 수열 입력받는 배열
		cnt=new int[N]; // cnt[i]: i번째 수 까지 고려하였을때 가장 긴 증가하는 부분수열의 길이
		
		st = new StringTokenizer(br.readLine());
		for(int i=0; i<N; i++) {
			arr[i]=Integer.parseInt(st.nextToken());
		}
		
		int temp=0;
		
		for(int i=0; i<N; i++) {
			cnt[i]=1;
			for(int j=0; j<i; j++) {
				if(arr[j]<arr[i] && cnt[i]<cnt[j]+1)// 현재 확인한 증가하는 부분수열의 뒤에 올 수 있는 경우
					cnt[i]=cnt[j]+1; // 길이 갱신 
			}
			answer=Math.max(answer, cnt[i]); // 결국 구하고자 하는것은 cnt[]의 최댓값이므로 for문도는김에 한번에 찾기
		}
		
//		System.out.println(Arrays.toString(cnt));
		System.out.println(answer);
	}

}

DP와 이분탐색 이용

• 시간복잡도: O(NlogN)
• 자세한 풀이는 주석 참고

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
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());
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		int[] arr= new int[n];
		int[] dp = new int[n];
		
		for(int i=0; i<n; i++) {
			arr[i]=Integer.parseInt(st.nextToken());
		}
		
		int size=0;
		for(int i=0; i<n; i++) {
			int x= Arrays.binarySearch(dp, 0, size, arr[i]);
     		// Arrays.binarySearch: dp배열의 0번째부터 size(이전)인덱스까지 중에서 arr[i]가 있는 위치를 리턴해준다. 
            // 만약 해당 배열에 찾으려는 숫자가 없다면 원래 들어가야하는 위치에 +1한 값에 마이너스를 붙여서 리턴한다.
//			System.out.println("x: " +x);
			if(x>=0) continue; // 찾으려는 수가 존재하는 경우 넘어감
			
			int index=Math.abs(x)-1; // 맨뒤 또는 기존 원소 대체 자리 
			dp[index]=arr[i]; // 더 작은수로 대체되어야 최장 증가수열을 얻을 수 있는 방향으로 나아가게 된다.
			if(index==size) size++;
		}
		System.out.println(size);
	
	}

}