Baekjoon Online Judge

algorithm practice

- 단계별 문제풀기

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

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

Java / Python

3. 가장 긴 증가하는 부분 수열 5

14003번

O(NlogN) LIS를 출력하는 문제

이번 문제는 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하는 문제입니다.

• Java

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

public class Main {  

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out)); 
		StringBuilder sb = new StringBuilder();
        
		int N = Integer.parseInt(br.readLine()); 
		ArrayList<Integer> list = new ArrayList<>();
		list.add(Integer.MIN_VALUE);
        
		int[] arr = new int[N]; // 수열 저장
		int[] tmp = new int[N]; // 수열 위치 저장
        
		StringTokenizer st = new StringTokenizer(br.readLine());        
		// 이분 탐색을 이용한 LIS 구하기
		for(int i = 0; i < N; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
			int num = arr[i];
			int start = 1;
			int end = list.size() - 1;
            
			if(num > list.get(list.size() - 1)){
				list.add(num);
				tmp[i] = list.size() - 1;
			}else{
				while(start < end){
					int mid = (start + end) / 2;

					if(list.get(mid) >= num) end = mid;
					else start = mid + 1;
				}
				list.set(end, num);
				tmp[i] = end;
			}
		} 
        
		sb.append(list.size() - 1 + "\n");
		Stack<Integer> stack = new Stack<>();
        
		int idx = list.size() - 1;
        
		for(int i = N - 1; i >= 0; i--) {
			if(tmp[i] == idx){
				idx--;
				stack.push(arr[i]);
			}
		}
        
		while(!stack.isEmpty()) {
			sb.append(stack.pop() + " ");
		}
        
		bw.write(sb.toString());        
		bw.flush();
		br.close();
		bw.close();
	}	
}

• Python

import sys
from bisect import bisect_left

N = int(sys.stdin.readline())
num = [0] + list(map(int, sys.stdin.readline().split()))

dp = [0] * (N+1)
tmp = [-1000000001]
maxvalue = 0

for i in range(1, N+1):
    if tmp[-1] < num[i]:
        tmp.append(num[i])
        dp[i] = len(tmp) - 1
        maxvalue = dp[i]
    else:
        dp[i] = bisect_left(tmp, num[i]) 
        tmp[dp[i]] = num[i] 
print(maxvalue) 

result = []
for i in range(N, 0, -1):
    if dp[i] == maxvalue:
        result.append(num[i])
        maxvalue -= 1
        
result.reverse()
print(*result)