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

문제

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열(LIS, Longest Increasing Subsequence)을 구하는 프로그램을 작성하는 문제입니다. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우, 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4입니다.

• 입력: 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어집니다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어집니다.
• 출력: 첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력합니다.

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

풀이: 다이나믹 프로그래밍(DP)을 활용한 O(N^2) 탐색

가장 긴 증가하는 부분 수열(LIS)은 다이나믹 프로그래밍의 대표적인 기본 유형입니다. 현재 위치의 원소를 마지막으로 하는 LIS의 길이를 DP 배열에 기록하며 탐색해 나가는 방식입니다.

• 상태 정의: d[i]를 i번째 원소를 마지막으로 하는 가장 긴 증가하는 부분 수열의 길이로 정의합니다.
• 초기화: 모든 원소는 그 자체만으로 길이 1인 부분 수열이 될 수 있습니다. 따라서 탐색을 진행할 때 기본 길이를 d[i] = 1로 초기화합니다.
• 점화식 도출: $i$번째 원소에 대해, 그보다 앞에 있는 모든 원소(j, 0 < j < i)를 순회합니다. 만약 앞선 원소보다 현재 원소가 더 크다면 (a[j] < a[i]), 앞선 원소까지의 증가 부분 수열 뒤에 현재 원소를 이어 붙일 수 있습니다. 따라서 점화식은 d[i] = Math.max(d[i], d[j] + 1)이 됩니다.
• 최댓값 갱신: 배열을 순회하며 각 d[i]가 구해질 때마다 전체 최댓값 ans를 갱신합니다. N이 1인 경우 반복문이 돌지 않으므로 ans의 초기값은 1로 설정하는 것이 안전합니다.

코드

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));
       BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

       int n = Integer.parseInt(br.readLine());
       int[] a = new int[n];
       StringTokenizer st = new StringTokenizer(br.readLine());
       for (int i = 0; i < n; i++) {
          a[i] = Integer.parseInt(st.nextToken());
       }

       int[] d = new int[n];
       d[0] = 1;
       
       // N이 1일 때를 대비하여 ans의 초기값을 1로 설정
       int ans = 1; 
       
       for (int i = 1; i < n; i++) {
          d[i] = 1;
          for (int j = 0; j < i; j++) {
             // 현재 수(a[i])가 이전 수(a[j])보다 크면 부분 수열 연장 가능
             if (a[j] < a[i]) {
                d[i] = Math.max(d[i], d[j] + 1);
             }
          }
          ans = Math.max(ans, d[i]);
       }

       bw.write(ans + "");

       bw.flush();
    }
}

알고리즘 분류

다이나믹 프로그래밍 (Dynamic Programming)