[백준][JAVA] 2631 - 줄세우기 - DP, 이진탐색

📌 문제

백준 | 줄세우기 | GOLD 4 | DP, 이진탐

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

 

📌 문제 탐색하기

• 일반적인 정렬 알고리즘은 최대 O(NlogN) ~ O(N^2) 까지 될 수 있어서… 비추하는 방법일 것 같은데
• 문제에서 N이 고작 200이하의 정수라고 주어졌고
• 시간제한이 1초라면, 최대 40000 즉, 1초도 안넘을 것임 ⇒ 그러므로 일반 정렬 사용해도 괜찮다.
• 근데 문제는,,, ‘정렬’을 하는 것이 아니라, ‘최소 몇 번으로 이동 가능’이므로 ‘DP’로 풀어야할 것.

• 3 7 5 2 6 1 4 - 3 5 6
• 3 7 4 5 2 6 1 (4번 이동) - 3456
• 3 4 5 2 6 1 7 (7번 이동) - 34567
• 1 3 4 5 2 6 7 (1번 이동) - 1 3 4 5 6 7
• 1 2 3 4 5 6 7 (2번 이동) - 1234567

⇒ 지금 문제를 보면, 총 4번의 이동에서 LIS (최장 증가 부분수열) 법칙이 쓰였음을 알 수 있음

 

📌 알고리즘

LIS

1️⃣ DP 활용 (O(n^2))

ARR[] = 3 7 5 2 6 1 4

DP = [1,1,1,1,1,1,1] : 최소 1개는 존재 (자기자신)

DP[1] =3< 7 : DP[1] = DP[1] + 1 = 2;

DP[2] = 3 < 5 , 7 < 5(X) = DP[2] + 1 = 2;

DP[3] = 아무것도 X = DP[3] = 1;

DP[4] = 3 < 6, 5 < 6, 2 < 6 = DP[4] + 3 = 4;

⇒ 여기서 이렇게 생각했는데 이러면 3, 5 2 이런식으로 되서 안됨 !!! 그래서 Math.max로 되는걸 확인해줘야함

 

⭐그렇다면 ? 

i = 4 (arr[4] = 6)

  - j = 0: arr[0] < arr[4] (3 < 6) → dp[4] = dp[0] + 1 = 2

  -  j = 1: arr[1] > arr[4] (7 > 6) → 갱신 X ⇒ dp[i] < dp[j] + 1

  -  j = 2: arr[2] < arr[4] (5 < 6) → dp[4] = dp[2] + 1 = 3

  -  j = 3: arr[3] < arr[4] (2 < 6) → dp[4] = dp[3] + 1 = 2 (이미 3이므로 갱신 X)

이 방식대로 계속 이어나가면 됨!!

 

2️⃣ 이진 탐색 활용 (Binary Search) (O(nlogn))

수열의 크기가 크게 주어진다면, 시간 초과가 발생할 수 있으므로 효율성을 올리기 위해서는 ‘이진탐색’으로 최적화 작업을 이뤄 시간복잡도를 줄인다.

근데,,, 이진탐색은 공식이 ‘오름차순 정렬’이 되어있는 수열에서 가능한데 어떻게 구현할까 ?

⇒ LIS의 형태를 유지하기 위해서 주어진 배열의 인덱스를 하나씩 살피며 숫자가 들어갈 위치를 이분탐색으로 탐색 !!

⇒ 단, 이진 탐색을 활용한 LIS는 ‘길이’에만 집중을 하는 것 (NOT 실제 답)

 

example

(1) LIS의 마지막 요소 < ARR[i] : LIS의 마지막에 부착

(2) LIS의 마지막 요소 > ARR[i] : 이분탐색을 활용해서 해당 요소가 어디 들어갈지 확인 & 대체

ARR[] = 3 7 5 2 6 1 4

LIS[] = 3

LIS[] = 3 7 → (1)

LIS[] = 3 5 (2) 이분탐색을 통해 해당 INDEX에 대체함

LIS[] = 2 5 (2)

LIS[] = 2 5 6 (1)

⇒ 즉, 길이가 3인 LIS가 나올 것

 

 

📌 코드 설계하기

1. 아이들의 수 N, 1~n명의 줄 숫자 입력
2. LIS 코드 작성

 

 

📌 정답 코드

##dp##
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main{

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int n = Integer.parseInt(br.readLine());
        int[] children = new int[n];
        int[] dp = new int[n];
        Arrays.fill(dp, 1);
        for (int i = 0; i < n; i++) {
            children[i] = Integer.parseInt(br.readLine());
        }

        int maximum = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (children[i] > children[j] && dp[i] < dp[j] + 1) {
                    dp[i] = dp[j] + 1;
                }
            }
            maximum = Math.max(maximum, dp[i]);
        }

        System.out.println(n - maximum);
    }
}

 

## 이진탐색 ##
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class q2631_gold4_2 {

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

        int idx = 0;
        lis[idx++] = arr[0];

        for (int i = 1; i < n; i++) {
            if (lis[idx - 1] < arr[i]) {
                lis[idx++] = arr[i];
            } else {
                int start = 0;
                int end = idx - 1;

                while (start <= end) {
                    int mid = start + (end - start) / 2;
                    if (lis[mid] < arr[i]) {
                        start = mid + 1;
                    } else {
                        end = mid - 1;
                    }
                }

                lis[start] = arr[i];
            }
        }

        int cnt = 0;
        for (int i = 0; i < n; i++) {
            if (lis[i] > 0) {
                cnt++;
            }
        }

        System.out.println(n - cnt);
    }
}

 

실제로 코드 길이 대비 확실히 이진탐색이 더 메모리가 적게 들어가긴 했다. 

근데 문제의 N크기가 그렇게 큰편이 아니라 그런지 차이가 미미한듯 하다.

그럼에도 불구하고, 각 알고리즘의 시간복잡도에 따른 구현의 차이를 배운 것 같아 다행이다 👍