BOJ 12015 가장 긴 증가하는 부분 수열 2(Java, Python)

문제 탐색하기

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열의 길이를 구하는 프로그램을 작성하라.

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

• 첫째 줄에 수열의 크기 N (1 ≤ N ≤ 1,000,000)
• 둘째 줄에 수열의 원소 A_i (1 ≤ A_i ≤ 1,000,000)

코드 설계하기

구현 방법

Python에서 bisect_left를 활용한 LIS 구현

1. 이분 탐색을 활용한 LIS(Longest Increasing Subsequence) 구현
   • res 배열은 현재까지 찾은 가장 긴 증가하는 부분 수열을 저장
   • 초기값으로 0을 넣어 시작 (인덱스 계산을 위해)
2. 입력받은 수열의 각 원소에 대해:
   • 현재 원소가 res 배열의 마지막 값보다 크면:
     • res 배열에 해당 원소를 추가 (부분 수열의 길이가 증가)
   • 현재 원소가 res 배열의 마지막 값보다 작거나 같으면:
     • bisect_left를 사용하여 해당 원소가 들어갈 적절한 위치를 찾음
     • 해당 위치의 값을 현재 원소로 교체
     • 이는 더 긴 부분 수열을 만들 수 있는 가능성을 보존하기 위함
3. 최종적으로 res 배열의 길이에서 1을 뺀 값이 가장 긴 증가하는 부분 수열의 길이
   • 1을 빼는 이유는 초기에 넣은 0을 제외하기 위함

Java에서 이분 탐색을 활용한 LIS 구현

1. 이분 탐색을 활용한 LIS(Longest Increasing Subsequence) 구현
   • res 배열은 현재까지 찾은 가장 긴 증가하는 부분 수열을 저장
   • 초기값으로 0을 넣어 시작 (인덱스 계산을 위해)
2. 입력받은 수열의 각 원소에 대해:
   • 현재 원소가 res 배열의 마지막 값보다 크면:
     • res 배열에 해당 원소를 추가 (부분 수열의 길이가 증가)
   • 현재 원소가 res 배열의 마지막 값보다 작거나 같으면:
     • res 배열에서 이분 탐색을 통해 해당 원소가 들어갈 적절한 위치를 찾음
     • 해당 위치의 값을 현재 원소로 교체
3. 최종적으로 res 배열의 길이에서 1을 뺀 값이 가장 긴 증가하는 부분 수열의 길이
   • 1을 빼는 이유는 초기에 넣은 0을 제외하기 위함

혹은 이진 탐색을 직접 구현하지 않고 Arrays.binarySearch 함수를 사용할 수 있다.

근데 그냥 직접 구현해보면서 이해하자 연습해보는게 좋으니깐… -_-;;

시간 복잡도

• 각 원소마다 이분 탐색을 수행: O(log N)
• 전체 원소 N개에 대해 수행: O(N log N)
• 전체 시간 복잡도: O(N log N)

정답 코드 (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)); 
        int N = Integer.parseInt(br.readLine());
        int[] arr = new int[N];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        } 

        int[] res = new int[N + 1];  // 초기값 0을 포함하기 위해 크기를 N+1로 설정
        res[0] = 0;  // 초기값 0 설정
        int len = 1;  // 초기값 0이 들어있으므로 길이를 1부터 시작

        for (int i = 0; i < N; i++) {
            if (res[len - 1] < arr[i]) {
                // 현재 원소가 res 배열의 마지막 값보다 크면 추가
                res[len] = arr[i];
                len++;
            } else {
                // 이진 탐색으로 적절한 위치 찾기
                int left = 0;
                int right = len;
                
                while (left < right) {
                    int mid = (left + right) / 2;
                    if (res[mid] < arr[i]) {
                        left = mid + 1;
                    } else {
                        right = mid;
                    }
                }
                
                // 찾은 위치에 현재 값 삽입
                res[right] = arr[i];
            }
        }

        System.out.println(len - 1);  // 초기값 0을 제외한 길이 출력
    }
}

정답 코드 (Python)

import sys
from bisect import bisect_left
r = sys.stdin.readline

N = int(r())
A = list(map(int, r().rstrip().split()))
res = [0]

for i in A:
    if res[-1] < i:
        res.append(i)
    else:
        res[bisect_left(res, i)] = i

print(len(res)-1)