백준 11053번
https://www.acmicpc.net/problem/11053

문제

---

생각하기

---

• LIS (최장 증가 부분 수열을 구하는 문제이다)

  • 원본 수열에서 연속적이지는 않지만, 증가하는 순서는 유지를 한다.

• memoization또는 binarySearch를 통해서 최적화 할 수 있다.
  

동작

        int ans = 1;
        for (int i = 0; i < N; i++) {
            ans = Math.max(ans, LIS(i));
        }

최대 길이를 각 i 부터 시작해서 계산한다. i 부터 시작해서 자기 보다 큰 값이 있는지 하나씩 계산

    private static int LIS(int n) {
        if (memo[n] != -1) return memo[n];

        // 최소 길이는 자기 자신
        int max = 1;

        for (int i = n + 1; i < N; i++) {
            if (arr[i] > arr[n]) {
                int listLen = LIS(i) + 1;
                max = Math.max(max, listLen);
            }
        }

        memo[n] = max;
        return memo[n];
    } // End of LIS()

각자의 위치에서 시작하기 때문에 최대값이 이미 저장되어 있는 memo[] 배열의 값을 계속해서 최대값으로 갱신해야 한다.

for (int i = n + 1; i < N; i++) {
이미 자신은 포함해서 max=1 이므로 n + 1에서 시작하면 된다.

결과

코드

---

binarySearch

import java.io.*;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class Main {

    // input
    private static BufferedReader br;

    // variables
    private static int N;
    private static int[] memo, arr;

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

        input();

        bw.write(solve());
        bw.close();
    } // End of main()

    private static String solve() {
        StringBuilder sb = new StringBuilder();

        sb.append(LIS());
        return sb.toString();
    } // End of solve()

    private static int LIS() {
        List<Integer> list = new ArrayList<>();
        list.add(arr[0]);

        for (int i = 1; i < N; i++) {
            if (list.get(list.size() - 1) < arr[i]) {
                list.add(arr[i]);
            } else {
                int idx = binarySearch(list, arr[i], 0, list.size() - 1);
                if (idx < 0) {
                    idx = -idx - 1;  // 삽입 지점을 찾기 위한 변환
                }
                list.set(idx, arr[i]);
            }
        }

        return list.size();
    } // End of LIS()

    private static int binarySearch(List<Integer> list, int target, int low, int high) {
        if (low == high) {
            if (list.get(low) < target) return low + 1;
            return low;
        }

        int mid = low + (high - low) / 2;
        if (list.get(mid) >= target) {
            return binarySearch(list, target, low, mid);
        } else {
            return binarySearch(list, target, mid + 1, high);
        }
    } // End of binarySearch()

    private static void input() throws IOException {
        N = Integer.parseInt(br.readLine());
        
        memo = new int[N + 1];
        arr = new int[N + 1];

        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
            memo[i] = -1;
        }
    } // End of input()
} // End of Main class

Memoization + 재귀

import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {

    // input
    private static BufferedReader br;

    // variables
    private static int N;
    private static int[] arr;
    private static int[] memo;

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

        input();

        bw.write(solve());
        bw.close();
    } // End of main()

    private static String solve() {
        StringBuilder sb = new StringBuilder();

        int ans = 1;
        for (int i = 0; i < N; i++) {
            ans = Math.max(ans, LIS(i));
        }

        sb.append(ans);
        return sb.toString();
    } // End of solve()

    private static int LIS(int n) {
        if (memo[n] != -1) return memo[n];

        // 최소 길이는 자기 자신
        int max = 1;

        for (int i = n + 1; i < N; i++) {
            if (arr[i] > arr[n]) {
                int listLen = LIS(i) + 1;
                max = Math.max(max, listLen);
            }
        }

        memo[n] = max;
        return memo[n];
    } // End of LIS()

    private static void input() throws IOException {
        N = Integer.parseInt(br.readLine());

        arr = new int[N];
        memo = new int[N];

        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
            memo[i] = -1;
        }

    } // End of input()
} // End of Main class