[Algorithm] 11053 - 가장 긴 증가하는 부분 수열(JAVA)

[Algorithm] 11053 - 가장 긴 증가하는 부분 수열(JAVA)

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

알고리즘

LIS(Longest Increasing Subsequence) 문제이다. 원소가 N개인 배열의 일부 원소를 골라내서 만든 부분 수열 중, 그 길이가 최대인 부분 수열을 최장 증가 부분 부분 수열(LIS)라고 한다. {10, 20, 10, 30, 20, 50 } 의 LIS 는 10,20,30,50이 최장이므로 4가 된다. LIS는 이분 탐색을 다루면 시간복잡도가 O(NlogN)을 가질 수 있으며, DP를 사용해도 O(N^2)이 나올 수 있다.

0 1 2 3 4 5 arr 10 20 10 30 20 50 dp 1 2 1 3 2 4

dp[0] = {10}, dp[1] = {10, 20}, dp[2] = {10}, dp[3] = {10, 20, 30}, dp[4] = {10, 20}, dp[5] = {10, 20, 30, 50} 와 같이 만들면된다. DP 알고리즘에는 Top-Down(재귀), Bottom-Up(반복문) 방식이 있다.

Top-Down 방식 (재귀)

private static int LIS(int N) { if (dp[N] == null) { // 수열의 최소 길이는 1 dp[N] = 1; // 이전 노드를 탐색하며 현재 원소보다 값이 작으면서 최댓값을 탐색 for (int i = N - 1; i >= 0; i--) { if (arr[i] < arr[N]) { dp[N] = Math.max(dp[N], dp[i]+1); } } } return dp[N]; }

DP 배열을 Integer(객체 배열)로 생성하여 초기값을 null로 만든다. 입력 받은 N의 값이 null 즉, 탐색하지 않은 원소이면 1로 만든다. 최소 길이는 1이기 때문. N 이전의 노드를 탐색해보며 현재 arr[N] 보다 작은 arr[i] 중 dp[i]가 가장 큰 원소를 찾아 dp[N]에 dp[i]+1을 넣어준 다음 dp[N]을 반환한다.

import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { static int[] arr; static Integer[] dp; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int N = Integer.parseInt(br.readLine()); dp = new Integer[N]; arr = new int[N]; StringTokenizer st = new StringTokenizer(br.readLine()); for (int i = 0; i < N; i++) arr[i] = Integer.parseInt(st.nextToken()); int result = 0; for (int i=0; i= 0; i--) { if (arr[i] < arr[N]) { dp[N] = Math.max(dp[N], dp[i]+1); } } } return dp[N]; } }

Bottom-Up (반복문)

for (int i=0; i

TopDown 방식의 재귀 방법을 for문으로 풀어낸 방법이다.

import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; import java.util.StringTokenizer; public class Main { static int[] arr; static Integer[] dp; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int N = Integer.parseInt(br.readLine()); dp = new Integer[N]; arr = new int[N]; StringTokenizer st = new StringTokenizer(br.readLine()); for (int i = 0; i < N; i++) arr[i] = Integer.parseInt(st.nextToken()); Arrays.fill(dp, 1); for (int i = 0; i < N; i++) { // 현재 for (int j= 0; j < i; j++) { // 비교 if (arr[i] > arr[j] && dp[i] < dp[j] + 1) { dp[i] = dp[j]+1; } } } int result = Integer.MIN_VALUE; for (int i=0; i

from http://sasca37.tistory.com/129 by ccl(A) rewrite - 2021-12-30 16:26:38