백준 12738번: 가장 긴 증가하는 부분 수열 3

문제 설명

• https://www.acmicpc.net/problem/12738
• 가장 긴 증가하는 부분 수열이란 다음과 같습니다.
  • 부분 수열: 수열 A의 원소를 활용해 만든 수열을 말합니다.
  • 증가하는: i<j일때 i번째 값< j번째 값이 성립함을 의미합니다.
  • 가장 긴: 만들어진 부분 수열의 길이가 가장 긴 걸 찾아야 합니다.
• 이때 부분 수열의 순서는 기존과 동일하게 유지되어야 합니다.

접근법

• N이 1,000,000이기 때문에 O(N^2)으로는 문제를 풀 수 없습니다.
• Ai의 범위가 음수를 포함하며 예제를 통해 중복된 값이 존재할 수 있음을 발견할 수 있습니다.
• 길이 n을 만족하는 부분 수열은 여러 개 존재할 수 있지만, 가장 기대값이 큰 수열은 여러개 중 하나밖에 없습니다.
  • 기대값은 제가 임의로 붙인 용어입니다. 추가로 원소가 붙을 가능성이 큰 정도를 나타냅니다.
    • 1~100사이 원소로 이루어진 A가 있을 때 길이가 2인 부분집합은 매우 많습니다.
      그 중 {1,98},{98,99}보다는 {1,2}를 선택하는 게 더 긴 수열을 만들 가능성이 큽니다.
  • 기대값이 가장 큰 부분수열은 조건을 만족하는 부분수열 중 마지막 원소의 크기가 가장 작은 부분수열입니다.
• 부분수열의 크기가 1일 때, 2일 때, ... 로 늘려가면서 기대값이 큰 수열을 만들면 그 속에는 어떤 규칙이 존재합니다.

  {8,2,4,3,1,6}수열로 확인해 보겠습니다.
  부분수열의 크기가 1일 때 기대값이 가장 큰 수열은 {1} 입니다.
  부분수열의 크기가 2일 때 기대값이 가장 큰 수열은 {2,3} 입니다.
  부분수열의 크기가 3일 때 기대값이 가장 큰 수열은 {2,3,6} 입니다.
  부분수열의 크기가 4인 수열은 존재하지 않습니다. 그러므로 가장 긴 증가하는 부분 수열의 길이는 3 입니다.

기대값은 수열의 가장 마지막 원소에 따라 정해집니다. 위 예시를 보면 이러한 수열의 마지막 원소가 증가하고 있다는 걸 알 수 있습니다. arr[i] = 수열의 크기가 i일 때 가장 기댓값이 큰 수열의 마지막 원소를 표현하는 배열을 만들면, i+1번째 값을 채우지 못하면 우리의 가장 긴 증가하는 부분수열의 길이가 i라는 걸 알 수 있습니다.

이러한 arr[i]배열을 만드는 이유는 시간복잡도를 낮추기 위해서 입니다. 수열의 마지막 원소가 증가하고 있기 때문에 arr배열은 오름차순으로 정렬됩니다. 즉, 배열이 정렬된 상태에서 기존의 배열 원소가 어떤 위치에 들어가야 하는지를 확인하면 됩니다. 정렬된 배열에서 어떠한 원소의 위치를 찾는 건 이분탐색을 진행하면 logN시간만에 해결할 수 있습니다.

• 이분탐색
  • 자바 함수: Arrays.binarySearch(배열,원소);
  • 리턴: 해당 원소가 배열에 존재하지 않으면 음수를 반환
    • 해당 원소가 배열에 존재할 때
      • 해당 원소가 하나면 해당 원소의 인덱스를 리턴
        • Arrays.binarySearch({1,2,3},2) -> 1를 리턴
      • 해당 원소가 여럿이면 왼쪽부터 binarySearch해서 처음 찾은 해당 원소의 인덱스를 리턴
        • 여기서는 아무튼 양수(횩은 0)를 리턴한다는 게 중요하기 때문에 자세한 설명은 생략하겠습니다.
        • 궁금하신 분들은 {1,1,2,1}, {1,1,2,1,1}, {1,2,1,1} 배열에서 1을 찾아보시면 감을 잡으실 수 있을 겁니다.
    • 해당 원소가 배열에 존재하지 않으면 -1x해당 원소가 존재했다면 있어야 할 인덱스+1을 리턴
      • Arrays.binarySearch({1,2,4},3) -> 3이 배열에 있었다면 2와4사이(2번째 idx)에 있었을 겁니다. -> -(2+1)인 3을 리턴합니다.

{3,2,6,4,5,1}이고, arr[i] =x일 때 x는 길이가 (i+1)인 수열을 만들 때 가장 기댓값이 큰 마지막 수라고 할 때
원소 3을 고려: 3으로 길이가 1인 수열을 만들 수 있음 -> arr = [3]
원소 2를 추가로 고려: 3으로 길이가 1인 수열을 만드는 것보다 2로 길이가 1인 수열을 만드는 게 더 유리 -> arr = [2]
원소 6을 추가로 고려: 길이가 1인 수열은 여전히 [2]가 더 유리, 대신 길이가 2인 수열을 만들 수 있고 그때 마지막 값은 6이 가장 유리 -> [2,6]
원소 4를 추가로 고려: 길이가 1인 수열은 2가 유리, 길이가 2인 수열은 6보다 4가 더 유리 -> [2,4]
원소 5를 추가로 고려: 길이가 1,2인 수열은 그대로, 대신 길이가 3인 수열을 만들 수 있음 -> [2,4,5]
원소 1을 추가로 고려: 길이가 1인 수열은 2보다 1이 유리, 길이가 2,3인 수열은 변경사항 없음 -> [1,4,5]
결론: 가장 긴 증가하는 부분수열의 길이는 3이다. // 이 때 그 수열이 [1,4,5]라는 얘기는 아님
방법론:
원소x가 arr속 어떤 원소보다 더 작다 -> 해당 원소의 자리에 x가 들어감.
원소x가 지금까지의 모든 arr원소보다 크다 -> arr에 새롭게 원소x를 추가.

pseudocode

정답배열을 큰 값으로 초기화 시켜둠.
for(원래 수열의 원소를 처음부터 순회하면서){
	if(현재 원소가 이미 정답배열에 들어있다면) continue; // [1,2,1,4]일 때 두번째 1보다 첫번째 1을 쓰는게 무조건 유리
    // 정답배열이 오름차순으로 정렬될려면 현재 원소가 정답배열의 어디에 들어가야 하는지를 고민해야 함
    현재 원소가 정답배열에 있는 값보다 크다면 새롭게 현재원소를 추가 // 정답배열을 최대값으로 초기화했기 때문에 이러한 경우는 불가능
    a<현재원소<b 또는 현재원소<b 인 경우 b값을 현재원소로 갱신 // 길이변화 없음
}

정답

import java.util.*;

class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int[] arr = new int[N];
		for (int i = 0; i < arr.length; i++) {
			arr[i] = sc.nextInt();
		}
		int[] result = new int[N];
		Arrays.fill(result, Integer.MAX_VALUE);
		int answer = 0;
		for (int i = 0; i < N; i++) {
			if(Arrays.binarySearch(result,arr[i])>=0)continue; // arr[i]원소가 이미 result에 들어있는 상태
			int idx = Math.abs(Arrays.binarySearch(result,arr[i]))-1;
			result[idx] = arr[i]; // 해당 위치에 이미 원소가 존재한다면 그 원소를 덮어씌움
			answer = Math.max(answer, idx+1); // 그 위치가 새로운 곳이라면 LSI의 길이가 갱신
		}
		System.out.println(answer);
	}
}

기타

가장 긴 증가하는 부분 수열은 유명한 알고리즘 문제로 아래와 같이 효율성을 높일 수 있습니다.
1. 완전탐색으로 모든 경우의 수를 다 점검한다. O(2^N)
2. 이중반복문으로 수열을 구한다. (a[i] = max(a[1],a[2],...a[n-1])+1) O(N^2)
3. 이분탐색을 이용한다. O(NlogN)