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() λ©μλ'
λ₯Ό μ°Έκ³ νμμ΅λλ€.
'π μκ³ λ¦¬μ¦ > ETC' μΉ΄ν κ³ λ¦¬μ λ€λ₯Έ κΈ
μ΅μ₯곡ν΅λΆλΆμμ΄(Longest Common Subsequence - LCS) (0) | 2023.04.01 |
---|---|
μ΅μ₯곡ν΅λ¬Έμμ΄(Longest Common Substring - LCS) (0) | 2023.04.01 |
μλ‘μ μ§ν©(Disjoint-sets) (0) | 2023.03.01 |