가장 긴 증가하는 부분 수열(LIS)과 역추적

• 관련 문제
  • BOJ 가장 긴 증가하는 부분 수열 4

 

 

가장 긴 증가하는 부분 수열 (LIS)

 

• 가장 긴 증가하는 부분 수열 : 수열의 원소를 순서대로 선택할 때 가장 긴 오름차순인 수열
• 코드로 구현하기

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

public class Main {
	
	static int N;
	static int[] A;
	static int[] dp;
	
    public static void main(String[] args) throws IOException {
    	
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	N = Integer.parseInt(br.readLine());
    	
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	A = new int[N];
    	for (int i=0; i<N; i++) {
    		A[i] = Integer.parseInt(st.nextToken());
    	}
    	dp = new int[N];
    	Arrays.fill(dp, 1);
    	
    	for (int i=0; i<N; i++) {
    		for (int j=0; j<i; j++) {
    			if (A[j] < A[i]) {
    				if (dp[i] < dp[j] + 1) {
    					dp[i] = dp[j] + 1;
    				}
    			}
    		}
    	}
    	
    	StringBuilder sb = new StringBuilder();
    	int max = -1;
    	for (int i=0; i<N; i++) {
    		if (max < dp[i]) {
    			max = dp[i];
    		}
    	}
    	sb.append(max);
    	
    	System.out.print(sb);
    }
    
};

 

• 수열의 i번째 원소로 끝나는 가장 긴 부분 증가 수열
  • i번째 이전의 j(0 <= j < i)번째 원소 중, i번째 원소보다 작으면서 선택했을 때 dp[i]를 갱신할 수 있는 값이 있으면 선택 및 갱신

 

 

역추적

 

• dp를 갱신할 때, 이전 값의 인덱스를 prev 배열에 저장
• 코드로 구현하기

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

public class Main {
	
	static int N;
	static int[] A;
	static int[] prev;
	static int[] dp;
	
    public static void main(String[] args) throws IOException {
    	
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	N = Integer.parseInt(br.readLine());
    	
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	A = new int[N];
    	for (int i=0; i<N; i++) {
    		A[i] = Integer.parseInt(st.nextToken());
    	}
    	dp = new int[N];
    	Arrays.fill(dp, 1);
    	prev = new int[N];
    	Arrays.fill(prev, -1);
    	
    	for (int i=0; i<N; i++) {
    		for (int j=0; j<i; j++) {
    			if (A[j] < A[i]) {
    				if (dp[i] < dp[j] + 1) {
    					dp[i]= dp[j] + 1;
    					prev[i] = j;
    				}
    			}
    		}
    	}
    	
    	StringBuilder sb = new StringBuilder();
    	int max = -1;
    	int idx = 0;
    	for (int i=0; i<N; i++) {
    		if (max < dp[i]) {
    			max = dp[i];
    			idx = i; // 역추적을 시작할 값의 idx를 찾기
    		}
    	}
    	sb.append(max);
    	sb.append("\n");
    	List<Integer> lst = new ArrayList<>();
    	
    	while (idx != -1) {
    		lst.add(A[idx]);
    		idx = prev[idx];
    	}
    	
    	Collections.reverse(lst);
    	for (int l : lst) {
    		sb.append(l);
    		sb.append(" ");
    	}
    	
    	System.out.print(sb);
    }
    
};

• prev를 선언할 때, -1로 초기화
• dp를 갱신할 때, prev를 갱신
• dp max값을 구하면서 LIS의 마지막 값의 인덱스 idx를 구함
• prev 테이블을 이용하여 idx부터 역추적하여 list에 담고, 이를 reverse