[Java+Python]12015번, 가장 긴 증가하는 부분 수열 2

목차

이진 탐색

 

[Java+Python]1920번, 수 찾기

[Java+Python]1654번, 랜선 자르기

[Java+Python]2805번, 나무 자르기

[Java+Python]2110번, 공유기 설치

[Java+Python]2805번, K번째 수

문제

 

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.

예를 들어, 수열 A = {10, 20, 10, 30, 20, 50}인 경우에 

가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50}이고, 길이는 4이다.

 

입력

 

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다.

둘째 줄에는 수열 A를 이루고 있는 $A_i$가 주어진다. ($1 ≤ A_i ≤ 1,000,000$)

 

출력

 

첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다.

 

풀이

 

전에 동적계획법으로 푼 적이 있는 LIS(Longest Incresing Subsequence) 문제이다.

 

솔직하게 말하자면 동적계획법으로 풀었던 것도 가물가물한데.. 이 문제를 이진 탐색으로 어떻게 풀어야 하나

 

방법 자체가 떠오르지 않아 시간을 꽤 사용했다.

 

그러다 여전히 잘 모르겠어서 여기저기 검색 해보고, 다른 사람의 풀이를 보고 그제야 이해를 했는데,

 

이 문제를 이진 탐색으로 푸는 핵심 아이디어는

 

배열의 각 요소를 순회하며 해당 요소가 LIS의 마지막 원소보다 크면 추가하고,

 

그렇지 않다면 LIS에서 해당 요소보다 큰 요소 중 가장 작은 것을 빼고 해당 요소를 넣어주는 것이다.

 

이 과정, 즉 주어진 요소의 위치를 찾는데 이진 탐색을 사용하면 된다!

 

구체적인 알고리즘은 아래와 같다.

 

1. 입력받은 요소를 수열의 크기 n과 배열 numbers에 넣어 초기화해 준다.
2. 답을 저장할 배열 lis와 lis의 길이를 저장할 length를 빈 배열과 0으로 초기화해 준다.
3. numbers의 각 요소를 순회하며 이진 탐색을 한다. 그 과정은 아래와 같다.
   
   
   1. left = 0, right = length로 초기화한다.
      이 조건 덕분에 처음 숫자는 일단 lis에 들어가고 시작한다.
   2. left가 right보다 작은 경우에 한해 다음의 과정을 반복한다.
      
      
      1. mid = (left + right) / 2로 설정한다.
      2. lis[mid]가 해당 순서의 numbers[i]보다 작다면 left = mid + 1로, 그렇지 않다면 right = mid로 갱신한다.
      3. 이런 식으로 해당 숫자보다 크거나 같은 수 중 가장 작은 수의 위치를 찾는다.
      4. lis[left] = numbers[i]로 갱신해 주고, 삽입된 위치가 현재 길이와 같다면 길이를 1 늘려준다.
4. n까지 모두 순회하고 나면 lis는 완성되고 length에는 해당 배열의 크기가 담기므로, 출력해 준다.

 

 

Java

 

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

public class Prob12015 {

	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int n = Integer.parseInt(br.readLine());
		int[] numbers =
			Arrays.stream(br.readLine().split(" "))
				.mapToInt(Integer::parseInt)
				.toArray();

		int[] lis = new int[n];
		int length = 0;

		for (int i = 0; i < n; i++) {
			int left = 0;
			int right = length;

			while (left < right) {
				int mid = (left + right) / 2;

				if (lis[mid] < numbers[i]) {
					left = mid + 1;
				} else {
					right = mid;
				}
			}

			lis[left] = numbers[i];

			if (left == length) {
				length++;
			}
		}

		System.out.println(length);
	}
}

 

Python

 

import sys

n = int(sys.stdin.readline().rstrip())
numbers = list(map(int, sys.stdin.readline().rstrip().split(' ')))

lis = [0] * n
result = 0

for i in range(n):
    left = 0
    right = result

    while left < right:
        mid = (left + right) // 2

        if lis[mid] < numbers[i]:
            left = mid + 1
        else:
            right = mid

    lis[left] = numbers[i]

    if left == result:
        result += 1

print(result)

 

Performance