[BOJ/Java] 12015. 가장 긴 증가하는 부분 수열 2

[BOJ/Java] 12015. 가장 긴 증가하는 부분 수열 2

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

---

문제 해석

주어진 수열에서 가장 긴 증가하는 부분 수열의 길이를 찾는 고전적인 문제의 확장판이다. 이 문제는 수열의 길이가 매우 클 수 있기 때문에 𝑂(𝑁^2)의 시간 복잡도를 갖는 기본적인 동적 프로그래밍 방법으로는 효율적으로 해결할 수 없다. 대신, 이진 탐색을 활용한 𝑂(𝑁log⁡𝑁) 시간 복잡도의 풀이가 필요하다.

풀이 과정

1. 입력 받기: 수열의 크기 N과 수열 A를 입력 받는다.
2. DP 배열 초기화 및 탐색: 각 요소를 순차적으로 처리하면서, 현재 요소가 마지막 요소보다 클 경우 배열에 추가하고, 그렇지 않을 경우 이진 탐색을 통해 적절한 위치를 찾아 요소를 업데이트한다.
3. 이진 탐색 함수 구현: lowerBound 함수를 사용하여, 삽입할 수의 위치를 찾아내는 이진 탐색 로직을 구현한다.
4. 결과 반환: DP 배열에서 유효한 요소의 개수(즉, 수열의 길이)를 반환한다.

코드

import java.io.*;
import java.util.*;

public class Main {
    private static int N; // 수열의 크기
    private static int[] A, dp; // 원 수열 A와 동적 프로그래밍을 위한 배열 dp

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();

        N = Integer.parseInt(br.readLine()); // 수열의 크기 입력

        A = new int[N]; // 수열 A 초기화
        StringTokenizer st = new StringTokenizer(br.readLine()); // 수열 A의 원소들 입력
        for (int i = 0; i < N; i++) {
            A[i] = Integer.parseInt(st.nextToken());
        }

        sb.append(sol()); // 가장 긴 증가하는 부분 수열의 길이를 계산하고 결과를 StringBuilder에 추가
        bw.write(sb.toString()); // 결과 출력
        bw.flush();
        bw.close();
    }

    private static int sol() {
        dp = new int[N]; // dp 배열 초기화
        dp[0] = A[0]; // 첫 번째 요소로 초기화
        int cursor = 1; // dp 배열의 유효한 길이
        for (int i = 1; i < N; i++) {
            if (dp[cursor - 1] < A[i]) dp[cursor++] = A[i]; // 현재 값이 dp 배열의 마지막 값보다 크면 추가
            else dp[lowerBound(A[i], 0, cursor - 1)] = A[i]; // 이진 탐색을 통해 적절한 위치 업데이트
        }
        return cursor; // dp 배열의 유효한 길이 반환
    }

    private static int lowerBound(int target, int start, int end) {
        int mid;
        while (start < end) {
            mid = (start + end) >>> 1;
            if (dp[mid] < target) start = mid + 1; // 중간 값보다 타겟이 크면 오른쪽 탐색
            else end = mid; // 그렇지 않으면 왼쪽 탐색
        }
        return start; // 적절한 위치 반환
    }
}

시간 복잡도 분석

이 문제의 시간 복잡도는 𝑂(𝑁log⁡𝑁)이다. 각 원소에 대해 이진 탐색을 수행하여 적절한 위치를 찾는 과정이 log⁡𝑁의 시간을 요구하고, 이 과정을 N번 반복하기 때문이다.

느낀점

가장 긴 증가하는 부분 수열을 찾는 이 문제는 이진 탐색을 활용하여 효율적으로 해결할 수 있다는 점이 매우 흥미롭다. 이진 탐색을 통해 삽입 위치를 결정함으로써 동적 프로그래밍의 갱신 과정을 최적화할 수 있으며, 이는 다양한 문제에 적용 가능한 테크닉이다. 이를 통해 더 복잡한 문제에 대한 해결 능력을 향상시킬 수 있다.