99클럽 코테 스터디 27일차 TIL

백준 - 11722번

LDS - 최장 감소 부분 수열

주어진 수열에서 요소들이 감소하는 순서대로 선택되는 가장 긴 부분 수열을 말한다.

수열의 원래 순서를 유지하면서 순서대로 감소하는 숫자들을 선택하여 만들 수 있는 가장 긴 부분 수열을 찾아야 한다.

---

DP

반복문을 돌면서 감소하는 부분 수열의 최대 길이를 배열에 저장하는 메모이제이션 방식으로 문제를 풀어야 한다.

 

최대 길이가 저장되는 배열을 dp라고 할 때, dp는 모두 1로 초기화한다.

감소하는 부분 수열이 없다면 자기 자신만 가지게 되기 때문이다.

 

감소하는 부분 수열이기 때문에 자신보다 왼쪽에 있는 값이 더 커야 한다.

먼저 기준 값(A [I])을 정하고, 왼쪽의 값(A [J])들을 모두 비교한다.

A [J]가 A[I] 보다 크다면 A [J]가 가진 길이에서 +1 하여 A [I]의 길이와 비교하고, 그중 최댓값을 찾아 A [I] 값을 초기화한다.

for (int i = 0; i < N; i++) { // 기준 값
    for (int j = 0; j < i; j++) { // 왼쪽 값 순회
        if (A[j] > A[i]) {
            dp[i] = Math.max(dp[i], dp[j] + 1);
        }
    }
}

최댓값을 찾는 이유

만약 70 60 80 90 30 10 배열이 주어졌다면, 가장 긴 부분 수열의 길이는 4이다.

최댓값을 찾지 않고 dp[i] = dp [j] + 1 만 해준다면 3이 반환된다.

 

dp[i] = dp [j] + 1

70	60	80	90	30	10
1	2	1	1	2	3

30이 기준 값이 될 때 값이 꼬이기 시작하는데, 90 > 30 조건으로 인해 90의 길이 값에서 + 1을 하게 된다.

 

dp[i] = Math.max(dp [i], dp [j] + 1)

70	60	80	90	30	10
1	2	1	1	3	4

최댓값으로 비교한다면 80과 90 조건이 true여도, 60의 길이 값인 2에서 변하지 않기 때문에

기준 값이 30일 때도 정상적으로 초기화 된다.

 

구현 1

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

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[] A = new int[N];
        int[] dp = new int[N];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            A[i] = Integer.parseInt(st.nextToken());
            dp[i] = 1;
        }

        int result = 0;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < i; j++) {
                if (A[j] > A[i]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            result = Math.max(result, dp[i]);
        }

        System.out.println(result);
        br.close();
    }
}

---

이분 탐색

DP 방식의 코드는 기준 값과 왼쪽 값을 비교하기 위해, 기준 값의 인덱스만큼 순회를 돌고 있다.

그리고 최대 길이 값을 저장하기 위해 메모이제이션 방식을 사용해 메모리를 소모하고 있다.

주어지는 수열의 길이가 길어질수록 시간 O(n^2)과 메모리 소모가 늘어난다.

 

최대 길이 값 저장이 아닌 조건에 맞는 수열의 요소들을 저장하여 그 크기를 반환해 보는 방법도 있다.

• 수열의 요소가 저장될 수 있는 list를 선언한다.
• list의 마지막 요소가 현재 요소(current) 보다 크면 list.add(current) 한다.
• 크거나 같다면 current 가 들어갈 수 있는 위치를 이분 탐색으로 찾는다.
• 이분 탐색으로 찾은 인덱스에 current를 저장한다.

구현 2

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

        int result = lds(arr);
        System.out.println(result);
        br.close();
    }

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

        for (int i = 1; i < arr.length; i++) {
            int current = arr[i];
            if (list.get(list.size() - 1) > current) {
                list.add(current);
            } else {
                int idx = binarySearch(list, current);
                list.set(idx, current);
            }
        }

        return list.size();
    }

    private static int binarySearch(ArrayList<Integer> list, int current) {
        int left = 0;
        int right = list.size() - 1;

        while (left <= right) {
            int mid = (left + right) / 2;
            if (list.get(mid) == current) {
                return mid;
            } else if (list.get(mid) > current) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        return left;
    }
}

조건에 해당하는 수열 값만 list에 저장되고, 이분 탐색으로 시간 복잡도가 O(NlogN)으로 줄었다.

---

백준 11722번 - 가장 긴 감소하는 부분 수열

https://www.acmicpc.net/problem/11722

 

참고

https://superohinsung.tistory.com/199