백준 11053, 가장 긴 증가하는 부분 수열

1. 문제

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

11053번: 가장 긴 증가하는 부분 수열

 

2. 문제요약

1. 수열 A가 주어졌을때 가장 긴 증가하는 부분 수열의 길이 값을 구하시오.
2. 수열의 크기 N, 1<=1000
3. 수열의 구성 요소 값 arr_i, 1<=arr_i<=1000

3. 문제풀이

3.1 첫번째 알고리즘 : O(N^2)

문제를 해결하기 위해서 새로운 배열 D를 정의합니다. D의 정의는 다음과 같습니다.

D[i] : arr[i]를 마지막 값으로 가지는 가장 긴 증가부분 수열의 길이

 

arr[i]가 어떤 증가부분수열의 마지막 값이 되기 위해서는 arr[i]가 추가되기 전 증가부분수열의 마지막 값이 arr[i]보다 작은 값이어야 합니다. 따라서 arr[i]를 마지막 값으로 가지는 '가장 긴' 증가부분수열의 길이는 arr[i]가 추가될 수 있는 증가부분 수열 중 가장 긴 수열의 길이에 1을 더한 값이 됩니다.

위와 같이 배열 D가 완성되었습니다. D의 값들 중 가장 큰 값(D[4]=D[8]=4)이 수열 arr = 3 5 7 9 2 1 4 8의 가장 긴 증가부분수열의 길이입니다. 이 알고리즘은 N개의 수들에 대해 자기 자신 전(arr[0]~arr[i-1])의 모든 수를 다 훓어봐야 하므로 O(N^2)의 시간복잡도를 가지는 알고리즘이 됩니다.

 

소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;


public class Main {
	
	public static int solution(int n, int[] arr, int[] d)
	{
		for(int i=1;i<=n;i++)
		{
			int max = arr[i];
			for(int j=0;j<i;j++)
			{
				if(arr[j]<max && d[i]<=d[j])
				{
					d[i] = d[j] + 1;
				}
			}
		}
		
		return Arrays.stream(d).max().getAsInt();
	}
	
	public static void main(String args[]) throws IOException
	{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		String[] str = br.readLine().split(" ");
		int[] arr = new int[n+1];
		int[] d = new int[n+1];
		
		for(int i=1;i<=n;i++)
		{
			arr[i] = Integer.parseInt(str[i-1]);
		}
		
		System.out.println(solution(n, arr,d));
	}
}

 

3.2 두번째 알고리즘 : O(N log N)

두번째 알고리즘은 첫번째 알고리즘을 개량한 형태입니다. 두번째 알고리즘은 다음과 같은 의문에서 시작합니다.

D[i]를 계산하기 위해 arr[0]~arr[i-1]을 전부 훓어봐야 하는가?

첫번째 알고리즘에서 arr[0]~arr[i-1]을 전부 훓어본 이유는 arr[i]의 값보다 작은 값(arr[0]~arr[i-1]값들 중 몇몇)들의 위치인덱스(j라 정의)를 찾기 위해서이다. 그 위치 인덱스(arr[i]값보다 작은 값을 가지는 arr 위치)들을 D[i]에 대입하고 그 값들 중 가장 큰 D[j] 값을 찾습니다. 

그래서 만약 D[j] = k를 만족하는 j 중 arr[j]의 값이 가장 작은 j만 어딘가에 저장해 놓으면, 나중에 D[i] ( i > j )을 계산할때 그 값들만 참조하면 D[i]의 값을 쉽게 알 수 있습니다.

 

 

소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;


public class Main {
	
	public static int bSearch(List<Integer> B, int val, int first, int last)
	{
		if(first>last)
		{
			return first-1;
		}
		int mid = (first+last)/2;
		if(val <= B.get(mid))
		{
			return bSearch(B, val, first, mid-1); 
		}
		else
		{
			return bSearch(B, val, mid+1, last);
		}
	}
	
	public static int solution2(int n, int[] arr, int[] d)
	{
		List<Integer> D_list = new ArrayList<>();
		List<Integer> B = new ArrayList<>();
		D_list.add(0);
		B.add(0);
		
		for(int i=1;i<=n;i++)
		{
			int val = arr[i];
			int idx = bSearch(B, val, 0, B.size()-1); 
			d[i] = D_list.get(idx);
			
			if(B.size()-1==idx)
			{
				D_list.add(d[i]+1);
				B.add(val);
			}else {
				B.set(idx+1, val);
			}
		}
		
		System.out.println("arr : " + Arrays.toString(arr));
		System.out.println("d : " + Arrays.toString(d));
		System.out.println("D_list : " + D_list);
		System.out.println("B : " + B);
		
		return D_list.get(D_list.size()-1);
	}
	
	
	public static void main(String args[]) throws IOException
	{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		String[] str = br.readLine().split(" ");
		int[] arr = new int[n+1];
		int[] d = new int[n+1];
		
		for(int i=1;i<=n;i++)
		{
			arr[i] = Integer.parseInt(str[i-1]);
		}
		
		System.out.println(solution2(n, arr,d));
	}
}

위의 사진에서 아래쪽 제출이 첫번째 알고리즘( O(N^2) )이고 위 제출이 두번째 알고리즘( O(N log N) ) 제출입니다. 위 테스트 결과의 시간을 보면 별로 차이가 안나 보이지만 이는 데이터의 수(N)이 1000이하이기 때문입니다. 아래의 테스트 결과는 N=100000으로 설정하고 첫번째 알고리즘과 두번째 알고리즘을 테스트 시간을 측정한 결과입니다.

첫번째 알고리즘을 적용한 test1()은 5초정도 걸린것을 알수 있고 두번째 알고리즘을 적용한 test2()은 1초정도 걸린 것을 알 수 있습니다. 즉, 백준의 문제에서는 N의 최댓값이 1000이기 때문에 속도가 비슷하지만 N=100000 부터는 두 알고리즘 간에 속도 차이가 발생한 것을 알 수 있습니다.

 

References

최장 증가 부분 수열, 나무위키 : https://namu.wiki/w/%EC%B5%9C%EC%9E%A5%20%EC%A6%9D%EA%B0%80%20%EB%B6%80%EB%B6%84%20%EC%88%98%EC%97%B4