πŸ“‚ μ•Œκ³ λ¦¬μ¦˜/ETC

졜μž₯μ¦κ°€λΆ€λΆ„μˆ˜μ—΄(Longest Increasing Subsequence - LIS)

Amenable 2023. 4. 1. 01:03

1. κ°œλ… 🌠

  μ΅œμž₯ μ¦κ°€ λΆ€λΆ„ μˆ˜μ—΄(LIS - Longest Increasing Subsequence)μ΄λž€ μž„μ˜μ˜ μˆ˜μ—΄λ‘œ λ§Œλ“  λΆ€λΆ„ μˆ˜μ—΄ μ€‘ μ˜€λ¦„μ°¨μˆœμœΌλ‘œ μ •λ ¬λœ κ°€μž₯ κΈ΄ μˆ˜μ—΄μ„ μ˜λ―Έν•œλ‹€.

  '3 2 6 4 5 1'이 μžˆλ‹€κ³  ν•˜μž. ν•΄λ‹Ή μˆ˜μ—΄μ˜ λΆ€λΆ„ μˆ˜μ—΄μ€

{3}, {2}, {6},...
{3, 2}, {2, 1},...
{2, 6, 4}, {2, 4, 5},...
{3, 2, 5, 1},...
{2, 6, 4, 5, 1},...
{3, 2, 6, 4, 5, 1}

등이 μ‘΄μž¬ν•œλ‹€. μ—¬κΈ°μ„œ 졜μž₯ 증가 λΆ€λΆ„ μˆ˜μ—΄μ€ {2, 4, 5}이며 κ·Έ κΈΈμ΄λŠ” 3이 되게 λœλ‹€.
  이번 글을 톡해 졜μž₯ μ¦κ°€ λΆ€λΆ„ μˆ˜μ—΄μ˜ κΈΈμ΄λ₯Ό κ΅¬ν•˜λŠ” 3κ°€μ§€ λ°©λ²•을 μ•Œμ•„λ³΄μž. μˆœμ„œλŠ” μ‹œκ°„λ³΅μž‘도가 ν° κ²ƒμ—μ„œλΆ€ν„° μž‘은 κ²ƒμœΌλ‘œ μ§„ν–‰λœλ‹€.

 

2. 방법 1 - O(2^N) πŸŒ€

  μ²« λ²ˆμ§Έ λ°©λ²•은 μœ„μ—μ„œ μ„€λͺ…ν•œ κ²ƒμ²˜λŸΌ λΆ€λΆ„ μˆ˜μ—΄μ„ μ΄μš©ν•˜λŠ” κ²ƒμ΄λ‹€. μ£Όμ–΄μ§„ μˆ˜μ—΄μ—μ„œ λΆ€λΆ„ μˆ˜μ—΄μ„ λͺ¨λ‘ κ΅¬ν•΄μ„œ μ¦κ°€ν•˜λŠ” λΆ€λΆ„ μˆ˜μ—΄ μ€‘ κ°€μž₯ κΈΈμ΄κ°€ κΈ΄ κ²ƒμ„ μ°ΎλŠ” λ°©μ‹μ΄λ‹€.
  μ‹œκ°„λ³΅μž‘λ„λŠ” O(2^N)인 μ§€μˆ˜ μ‹œκ°„ λ³΅μž‘λ„λ₯Ό κ°€μ§€κ²Œ λœλ‹€.

 

3. 방법 2 - O(N^2) 🌟

  λ‘ λ²ˆμ§Έ λ°©λ²•은 DPλ₯Ό μ΄μš©ν•˜λŠ” λ°©λ²•이닀. μ΄ λ°©λ²•은 μ£Όμ–΄μ§„ μˆ˜μ—΄μ„ iλ²ˆμ§ΈκΉŒμ§€λ§Œ κ³ λ €ν•˜λ©΄μ„œ μ΅œλŒ€μ¦κ°€ λΆ€λΆ„μˆ˜μ—΄μ˜ κΈΈμ΄λ₯Ό μ—…λ°μ΄νŠΈν•˜λŠ” λ°©μ‹μ΄λ‹€.
  μ•„λž˜μ˜ DP[i]λŠ” (0 ~ i) 번째 μ›μ†Œλ“€μ„ ν¬ν•¨ν•˜λŠ” μˆ˜μ—΄μ—μ„œμ˜ μ΅œλŒ€μ¦κ°€ λΆ€λΆ„μˆ˜μ—΄μ˜ 길이λ₯Ό λ‚˜νƒ€λ‚Έλ‹€.

λ§Œμ•½ i < k이고, arr[i] < arr[k]이고, DP[i] + 1> DP[k] 라면 DP[k]λŠ” DP[i] + 1둜 μ—…λ°μ΄νŠΈν•΄μ£Όμ–΄μ•Ό ν•œλ‹€. μ΄λŠ” 'kλ²ˆμ§ΈκΉŒμ§€ 고렀된 상황'μ—μ„œ 'k보닀 μ•žμ„  iλ²ˆμ§ΈκΉŒμ§€ 고렀된 μƒν™©μ—μ„œμ˜ μ΅œλŒ€μ¦κ°€ λΆ€λΆ„μˆ˜μ—΄μ˜ 길이'보닀 더 큰 μ΅œλŒ€μ¦κ°€ λΆ€λΆ„μˆ˜μ—΄μ˜ 길이λ₯Ό 찾은 경우λ₯Ό μ˜λ―Έν•œλ‹€.

  즉, μˆ˜μ—΄μ˜ 길이λ₯Ό μ¦κ°€ν•˜λ©΄μ„œ μ΅œλŒ€μ¦κ°€ λΆ€λΆ„μˆ˜μ—΄μ˜ 길이도 같이 μ—…λ°μ΄νŠΈν•΄ μ£ΌλŠ” 것이닀. μ•„λž˜μ˜ μ½”λ“œλ₯Ό μ΄μš©ν•˜μ—¬ μžμ„Ένžˆ 이해해 보자.

public static void main(String[] args) {
    int N = 6;
    int[] arr = new int[]{3, 2, 6, 4, 5, 1};
    int[] DP = new int[N];

    // μ΅œλŒ€μ¦κ°€λΆ€λΆ„μˆ˜μ—΄μ˜ 길이
    int maxLen = 0;

    // iλ²ˆμ§ΈκΉŒμ§€λ§Œ κ³ λ €ν•˜λŠ” μˆ˜μ—΄ λ§Œλ“€κΈ°
    for(int i = 0; i < N; i++) {
        DP[i] = 1;

        for(int j = 0; j < i; j++) {

            // i번째의 값보닀 μž‘μ€ 것(= 증가 λΆ€λΆ„ μˆ˜μ—΄)λ“€ μ€‘μ—μ„œ
            // 증가 λΆ€λΆ„ μˆ˜μ—΄μ˜ 길이가 κ°€μž₯ κΈ΄ κ²ƒμœΌλ‘œ μ—…λ°μ΄νŠΈ ν•˜λŠ” κ³Όμ •
            if((arr[j] < arr[i])
                    && (DP[i] < DP[j] + 1)) {
                DP[i] = DP[j] + 1;
            }
        }

        // μ–΄λŠ μ§€μ μ—μ„œ 
        // 졜μž₯μ¦κ°€μˆ˜μ—΄μ˜ μ΅œλŒ€ 길이λ₯Ό ν¬ν•¨ν•˜λŠ”μ§€ λ°”λ‘œ μ•Œ 수 μ—†κΈ° λ•Œλ¬Έμ—
        // μ΄λ ‡κ²Œ 계속 졜μž₯μ¦κ°€λΆ€λΆ„μˆ˜μ—΄μ˜ 길이(maxLen)λ₯Ό μ—…λ°μ΄νŠΈ
        if(maxLen < DP[i]) {
            maxLen = DP[i];
        }
    }

    System.out.println(maxLen);
}

  ν•΄λ‹Ή λ°©λ²•μ˜ μ‹œκ°„λ³΅μž‘λ„λŠ” O(n ^ 2)이닀.

 

4. 방법 3 - O(N logN) 🌌

  μ„Έ λ²ˆμ§Έ λ°©λ²•은 DPλ₯Ό μ΄μš©ν•œ λ‘ λ²ˆμ§Έ λ°©λ²•을 κ°œμ„ ν•œ κ²ƒμ΄λ‹€. 
'8 2 4 3 6 11 7 10 14 5'λΌλŠ” μˆ˜μ—΄μ΄ μžˆλ‹€κ³  ν•΄λ³΄μž. μˆ˜μ—΄μ˜ μ•žλΆ€λΆ„λΆ€ν„° κ³ λ €ν•˜λ©΄μ„œ μ΅œλŒ€μ¦κ°€ λΆ€λΆ„μˆ˜μ—΄μ„ λ§Œλ“ λ‹€κ³  ν•˜λ©΄ μ•„λž˜μ²˜λŸΌ λ§Œλ“€ 수 μžˆλ‹€. (μ£Όμ–΄μ§„ μˆ˜μ—΄μ€ 검은색 μ˜μ—­μ— κ°€λ‘œλ‘œ, ν•΄λ‹Ή μ§€μ μ˜ μ΅œλŒ€μ¦κ°€ λΆ€λΆ„μˆ˜μ—΄μ€ μ„Έλ‘œλ‘œ λ‚˜νƒ€λ‚˜μ Έ μžˆλ‹€.)

  μ΄λŠ” λ§€ μˆœκ°„ μ΅œλŒ€μ¦κ°€ λΆ€λΆ„μˆ˜μ—΄μ„ μ΅œμ ν™”ν•΄ λ‚˜κ°„λ‹€κ³  ν•  수 μžˆλ‹€. μ—¬κΈ°μ„œ λ§ν•œ μ΅œμ ν™”λŠ” μ΅œλŒ€μ¦κ°€ λΆ€λΆ„μˆ˜μ—΄μ„ λ§Œλ“€κΈ° μœ„ν•΄ μ΄ν›„μ˜ 상황을 κ³ λ €ν•˜μ˜€μ„ λ•Œ μ£Όμ–΄μ§„ μƒν™©μ—μ„œ κ°€μž₯ μ μ ˆν•œ μ΅œλŒ€μ¦κ°€ λΆ€λΆ„μˆ˜μ—΄μ„ λ§Œλ“œλŠ” 것이라고 ν•  수 μžˆλ‹€.
  κ²°κ΅­ 순회λ₯Ό ν•  λ•Œ(=μ£Όμ–΄μ§„ μˆ˜μ—΄μ˜ μ•žλΆ€λΆ„λΆ€ν„° κ³ λ €ν•˜λ©΄μ„œ μ§„ν–‰ν•  λ•Œ) 졜적의 μ΅œλŒ€μ¦κ°€ λΆ€λΆ„μˆ˜μ—΄μ„ λ§Œλ“€μ–΄λ‚˜κ°€λ©΄ λ˜λŠ” 것이닀. μ΄λŠ” μ•„λž˜μ˜ μ½”λ“œμ²˜λŸΌ 이뢄탐색을 μ΄μš©ν•˜μ—¬ λ§Œλ“€ 수 μžˆλ‹€. 전체 μ‹œκ°„λ³΅μž‘λ„λŠ” O(N log N)이닀.

public static void main(String[] args) {
    int N = 6;
    int[] arr = new int[]{3, 2, 6, 4, 5, 1};
    // 졜적의 μ΅œλŒ€μ¦κ°€λΆ€λΆ„μˆ˜μ—΄
    int[] bestSubsequence = new int[N];

    // μ΅œλŒ€μ¦κ°€λΆ€λΆ„μˆ˜μ—΄μ˜ 길이
    int maxLen = 0;
    for(int i = 0; i < N; i++) {
        // 이뢄 탐색을 μ΄μš©ν•˜μ—¬ μœ„μΉ˜ μ°ΎκΈ°
        int pos = Arrays.binarySearch(bestSubsequence, 0, maxLen, arr[i]);

        // 이미 같은 값이 μ‘΄μž¬ν•˜λŠ” 경우(pos > 0)λŠ” κ±΄λ„ˆλ›°κΈ°
        if(pos >= 0) {
            continue;
        }

        int posiblePos = Math.abs(pos) - 1;
        // 졜적의 μ΅œλŒ€μ¦κ°€λΆ€λΆ„μˆ˜μ—΄ μ—…λ°μ΄νŠΈ
        bestSubsequence[posiblePos] = arr[i];

        // 맨 뒀에 μΆ”κ°€ν•œ 경우
        if(posiblePos == maxLen) {
            maxLen++;
        }
    }

    System.out.println(maxLen);
}

  μœ„μ—μ„œ λ‚˜μ˜€λŠ” Arrays.binarySearch의 리턴값은 μ•„λž˜μ˜ 그림을 톡해 λΉ λ₯΄κ²Œ 이해할 수 μžˆλ‹€.

  κ°„λ‹¨ν•˜κ²Œ μƒκ°ν•˜λ©΄, 찾고자 ν•˜λŠ” 값이 있으면 ν•΄λ‹Ή 인덱슀λ₯Ό 리턴해주고, μ—†λ‹€λ©΄ μžˆμ–΄μ•Ό ν•˜λŠ” μœ„μΉ˜μ˜ μ†Œμˆ˜μ  μžλ¦¬μ— -λ₯Ό λΆ™μ—¬μ„œ λ¦¬ν„΄ν•΄μ£ΌλŠ” 것이닀.

 

  μ΄μƒμœΌλ‘œ 졜μž₯증가 λΆ€λΆ„μˆ˜μ—΄(LIS)을 κ΅¬ν•˜λŠ” 3κ°€μ§€ 방법에 λŒ€ν•΄μ„œ μ•Œμ•„λ³΄μ•˜λ‹€. 각각의 λ°©λ²•μ˜ μ‹œκ°„λ³΅μž‘λ„λŠ” O(2^N), O(N^2), O(N logN)μ΄λΌλŠ” 점을 κΈ°μ–΅ν•΄ λ‘μž.

 

ν•΄λ‹Ή 글은
큰돌 λ‹˜μ˜ 'μ΅œλŒ€μ¦κ°€λΆ€λΆ„μˆ˜μ—΄, LIS, Longest Increase Sequence',
bang2001 λ‹˜μ˜ 'Arrays.binarySearch() λ©”μ†Œλ“œ'
λ₯Ό μ°Έκ³ ν•˜μ˜€μŠ΅λ‹ˆλ‹€.