π λμ κ³νλ².
ν΅μ¬μ top down / bottom up λ°©μμμ μ€λ³΅λλ μ°μ°μ νΌνλ κ².
-> O(2^n)μ μκ°λ³΅μ‘λλ₯Ό κ°μ§κ² λ κ²½μ° ( μ¬κ· ν¨μ )
-> μ°μ°μ νμκ° λμ΄λλ€.
-> μ½ μ€νμ΄ λ§μ΄ λμ΄λλ―λ‘ μ±λ₯μ΄ μμ’μμ§λ€.
μ±λ₯λΏλ§μ΄ μλ νκ³μ κΉμ§ κ° κ²½μ° μλ¬λ λ°μνλ€.
μ΄λ―Έ μ°μ°μ ν κ³Όμ μ λ€μ μ°μ°νλ λΆλΆμ΄ μ겨λλ€.
π νΌλ³΄λμΉ μμ΄λ‘ μμλ₯Ό λ§μ΄ λ λ€.
public class pbnc {
public static void main(String[] args) {
int n = 10;
}
// λ°λ³΅λλ μ°μ°μ κ³ λ €νμ§ μμ.
static int ffibo1( int x ) {
if (x == 1 || x== 2) {
return 1;
}
return ffibo1(x-1) + ffibo1(x -2);
}
}
λ°λ³΅λλ μ°μ°μ νΌνκ³ μΆλ€λ©΄, νλ² μ°μ°ν κ°μ μ°μ°μμ΄ μΈ μ μκ² κΈ°μ΅νκ³ μμΌλ©΄ λλ€.
λ°λΌμ, μ΄λ―Έ μμ μ°μ°ν κ³Όμ μ λ©λͺ¨μ΄μ μ΄μ μ ν΅ν΄ μ°μ°μ μλ΅ ν μ μλ€.
π€’ λ©λͺ¨μ΄ μ μ΄μ ==> μ°μ°ν κ²°κ³Ό ( ν λ² κ³μ°ν κ²°κ³Ό ) λ₯Ό λ©λͺ¨λ¦¬ 곡κ°μ λ©λͺ¨ νλ κ².
static int memoFibo(int x) {
if (x == 1 || x == 2) {
return 1;
}
// λ°°μ΄ dp[x]κ° μ°μ°ν μ μ΄ μλ€λ©΄,
if (dp[x] != 0) {
return dp[x]; // μ°μ° νλ κ° (λ©λͺ¨μ μ΄μ
κ°) μ 리ν΄νλ€.
}
// μ°μ° ν μ μ΄ μλ€λ©΄ μ°μ°ν΄μ λ©λͺ¨μ μ΄μ
μ²λ¦¬.
dp[x] = memoFibo(x-1) + memoFibo(x-2);
return dp[x];
}
μ λ°©μμ λ€μκ³Ό κ°μ κ·Έλ¦Όμ ν΄λΉνλ€.
μ΄λ° λ©λͺ¨μ μ΄μ μ ꡬνν΄μ λμ κ³νλ²μ ꡬμνλ λ°©λ²μ ν¬κ² top down(μ¬κ·) / bottom up(for-loop) λ°©μμ΄ μλ€.
μ¬κ·λ μμ λ°©μκ³Ό λμΌνλ―λ‘ μλ΅νκ³ bottom up λ°©μμ λ€μκ³Ό κ°λ€.
static int bottomUpForLoop(int j ) {
// 10λ² μ°μ°νκ³ μΆλ€λ©΄,
int n = 10;
dp[0] = 1;
dp[1] = 1;
int k = n;
for (int i=0; i<n; i++) {
if (dp[i]==null) { //λ°°μ΄ κ°μ΄ μμ κ²½μ°λ§ μ°μ°.
dp[i]=dp[i-1]+dp[i-2];
}
}
return dp[n];
}
λ.
https://www.acmicpc.net/problem/10844
'ALGORITHM' μΉ΄ν κ³ λ¦¬μ λ€λ₯Έ κΈ
[νΌλ³΄λμΉ μμ΄] μ¬κ·νΈμΆ, λ°°μ΄ (1) | 2022.11.19 |
---|---|
[μ΄μ§ νμ] Binary Search Algorithm (0) | 2022.11.18 |
[LIS] λ°±μ€ 2631 μ€ μΈμ°κΈ° (0) | 2022.08.28 |
[LIS] λ°±μ€ 11053 κ°μ₯ κΈ΄ μ¦κ°νλ λΆλΆ μμ΄ (0) | 2022.08.28 |
DFS java (0) | 2022.06.17 |