Baekjoon Online Judge

algorithm practice

- 단계별 문제풀기

27. 동적 계획법과 최단거리 역추적

지금까지는 최솟값, 최댓값, 최단거리만 찾았습니다. 이번에는 실제 최적해와 최단경로를 찾아 봅시다.

Java / Python

2. 가장 긴 증가하는 부분 수열 4

14002번

O(N^2) LIS를 출력하는 문제

이번 문제는 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하는 문제입니다. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4입니다.

• Java

list 배열에 수열을 입력받고, 먼저 dp배열에 현재 위치를 포함하여 만들 수 있는 가장 긴 증가하는 부분수열의 길이를 저장합니다.
tmp 배열을 사용하여 현재 위치에서 가장 긴 증가하는 부분 수열을 만들기 위해서 선택한 인덱스의 위치를 저장하고, dp 배열을 사용하여 수열 길이의 최대값, 수열 A에서 가장 긴 부분 수열이 끝나는 위치를 찾았습니다.
마지막으로, tmp 배열을 이용해서 선택을 역추적한 결과를 출력했습니다.

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

public class Main {  
	static int N;
	static int[] list; // 수열 입력받는 배열
	static int[] dp;
	static int[] tmp;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));   
        
		N = Integer.parseInt(br.readLine()); 
		list = new int[N + 1];
		dp = new int[N + 1];
		tmp = new int[N + 1];
        
		int result = 0;
		int resultIdx = 0;
        
		StringTokenizer st = new StringTokenizer(br.readLine());
		for(int i = 0; i < N; i++) {
			list[i] = Integer.parseInt(st.nextToken());
			dp[i] = 1;
			for(int j = 0; j < i; j++){
				if(list[i] > list[j] && dp[j]+1 > dp[i]){
					dp[i] = dp[j] + 1;
					tmp[i] = j;
				}
			}
			if(dp[i] > result){
				result = dp[i];
				resultIdx = i;
			}
		} 
        
		int[] answer = new int[result];
		int index = resultIdx;

		for(int i = result - 1; i >= 0; i--) {
			answer[i] = list[index];
			index = tmp[index]; 
		}
        
		bw.write(result + "\n");
        
		for(int i = 0; i < result; i++) {
			bw.write(answer[i] + " \n");
		}
        
		bw.flush();
		br.close();
		bw.close();
	}	
}

• Python

import sys

N = int(sys.stdin.readline())
num = list(map(int, sys.stdin.readline().split()))

dp = [1]*N

for i in range(1, N):
    for j in range(i):
        if num[i]>num[j]:
            dp[i] = max(dp[i], dp[j]+1)

print(max(dp))
order = max(dp)
arr = []
for i in range(N-1, -1, -1):
    if dp[i]==order:
        arr.append(num[i])
        order-=1
        
arr.reverse()
for i in arr:
    print(i, end=' ')