μ΄ κ²μκΈμ κ°μΈμ μΈ κ³΅λΆλ₯Ό μν΄ μμ±λ κ²μλ¬Όμ λλ€.
μ΄ κΈμ λͺ¨λ μΆμ²λ https://babbab2.tistory.com/100 μ λλ€.
λμ κ³νλ²
μν₯μ μ κ·Όλ²μΌλ‘ κ°μ₯ μμ λΆλΆμ ν΄λ΅μ ꡬν ν,
μ΄λ₯Ό μ μ₯νμ¬ μ μ₯ν κ°μ μ΄μ©ν΄ μμ λ¬Έμ λ₯Ό νμ΄κ°λ λ°©λ²
λμ κ³νμ ν΅μ¬μ Memoization(λ©λͺ¨μ΄μ μ΄μ )μ΄λΌλ κΈ°λ²μΈλ°
μ€λͺ μ μλμ κ°μ΅λλ€.
λ©λͺ¨μ΄μ μ΄μ
λμΌν κ³μ°μ λ°λ³΅ν΄μΌν λ, μ΄μ μ κ³μ°ν κ°μ λ©λͺ¨λ¦¬μ μ μ₯ν ν
λ°λ³΅μνμ μ κ±°νμ¬ νλ‘κ·Έλ¨ μ€νμλλ₯Ό λΉ λ₯΄κ² νλ κΈ°λ²
νΌλ³΄λμΉ μμ΄λ‘ μ΄ν΄νκΈ°
0, 1, 2, 3, 5, 8, 13 ...
μ΄λ°μμΌλ‘ κ°μ₯ μ²μ 0, 1μ μ μΈνκ³ λ΄ μμ λ λμ λν΄μ λλ₯Ό λ§λλ κ²μ΄ νΌλ³΄λμΉ μμ΄μ λλ€.
μ¬κ·ν¨μλ₯Ό μ΄μ©ν ꡬν
func fibo(_ n: Int) -> Int {
if n <= 1 { return n }
return fibo(n - 1) + fibo(n - 2)
}
λ§μ½ μ ν¨μλ‘ fibo(4)λ₯Ό νΈμΆνλ€λ©΄
fibo(0)μ ꡬνλ ν¨μλ₯Ό 2λ² μ€λ³΅ μ€ννκ³ ,
fibo(1)μ ꡬνλ ν¨μλ₯Ό 3λ² μ€λ³΅ μ€ννκ³ ,
fibo(2)λ₯Ό ꡬνλ ν¨μλ₯Ό 2λ² μ€λ³΅μ€νν΄μΌν©λλ€.
νλμ κ²°κ³Ό κ°μ λμΆνλλ° μ€λ³΅λλ κ°μ μ»κΈ°μν΄ μ€νλλ ν¨μκ° λ무 λ§μ΅λλ€.
μ΄λ° λ°©λ²μ μ«μκ° μ»€μ§μλ‘ νλ‘κ·Έλ¨μ μ€νμλλ₯Ό λ¨μ΄λ¨λ¦½λλ€.
λμ κ³νλ²μ μ΄μ©ν ꡬν
λμ κ³νλ²μμλ λ©λͺ¨μ΄μ μ΄μ μ μ¬μ©ν©λλ€.
κ°μ₯ μμ λ¨μλΆν° κ³μ°νκ³ μ μ₯νμ¬, ν° λ¨μ κ°μ λμΆν©λλ€.
λμ κ³νλ²μμλ μμ λ¨μλ₯Ό μ μ₯ν μ μ₯ 곡κ°μ΄ νμν©λλ€.
func fibo(_ n: Int) -> Int{
var cache: [Int] = [0, 1]
for num in 2...n {
cache.append(cache[num - 1] + cache[num - 2])
}
return cache[n]
}
μ΄λ κ² cacheλΌλ μ μ₯ 곡κ°μ νμ©ν΄μ, κ°μ₯ μμ λ¨μ 0, 1λΆν° λμΆλλ κ°μ κ³μ μ μ₯ν΄λκ°λλ€.
λ§μ½ 4λ²μ§Έ μλ₯Ό ꡬνκΈ° μν΄ μλμ κ°μ΄ μ€ννλ©΄
fibo(4)
4λ³΄λ€ μμ κ°λ€μΈ 0, 1, 2, 3λ²μ§Έ κ°κΉμ§λ₯Ό λ¨Όμ ꡬνμ¬ μ μ₯νκ³ ,
μ΄ κ°λ€μ΄ μ μ₯λμ΄ μλ λ©λͺ¨λ¦¬λ₯Ό μ΄μ©νμ¬,
2λ²μ§Έ index + 3λ²μ§Έ indexμ κ°μ λν΄ κ΅¬νλ κ²μ λλ€.
μ΄λ―Έ μ μ₯λμ΄ μλ κ°μ νμ©νλ κ²μ΄κΈ° λλ¬Έμ, μ€λ³΅ μ€ν ν νμκ° μμ΅λλ€.
μ΄λ° κ³Όμ λ€λ‘ μΈν΄ μ€νμλλ₯Ό λΉ¨λΌμ§λλ€.
'π» CS > μκ³ λ¦¬μ¦' μΉ΄ν κ³ λ¦¬μ λ€λ₯Έ κΈ
λΉνΈλ§μ€νΉ (2) | 2023.05.13 |
---|---|
[Swift] λ°±νΈλνΉ (0) | 2023.05.09 |
[Swift] 그리λ(Greedy) μκ³ λ¦¬μ¦ (0) | 2023.04.04 |
[Swift] (λΆν μ 볡) ν΅ μ λ ¬ ꡬνν΄λ³΄κΈ° (0) | 2023.04.03 |
[Swift] κΉμ΄μ°μ νμ(DFS) ꡬνν΄λ³΄κΈ° (0) | 2023.03.30 |
μ΄ κ²μκΈμ κ°μΈμ μΈ κ³΅λΆλ₯Ό μν΄ μμ±λ κ²μλ¬Όμ λλ€.
μ΄ κΈμ λͺ¨λ μΆμ²λ https://babbab2.tistory.com/100 μ λλ€.
λμ κ³νλ²
μν₯μ μ κ·Όλ²μΌλ‘ κ°μ₯ μμ λΆλΆμ ν΄λ΅μ ꡬν ν,
μ΄λ₯Ό μ μ₯νμ¬ μ μ₯ν κ°μ μ΄μ©ν΄ μμ λ¬Έμ λ₯Ό νμ΄κ°λ λ°©λ²
λμ κ³νμ ν΅μ¬μ Memoization(λ©λͺ¨μ΄μ μ΄μ )μ΄λΌλ κΈ°λ²μΈλ°
μ€λͺ μ μλμ κ°μ΅λλ€.
λ©λͺ¨μ΄μ μ΄μ
λμΌν κ³μ°μ λ°λ³΅ν΄μΌν λ, μ΄μ μ κ³μ°ν κ°μ λ©λͺ¨λ¦¬μ μ μ₯ν ν
λ°λ³΅μνμ μ κ±°νμ¬ νλ‘κ·Έλ¨ μ€νμλλ₯Ό λΉ λ₯΄κ² νλ κΈ°λ²
νΌλ³΄λμΉ μμ΄λ‘ μ΄ν΄νκΈ°
0, 1, 2, 3, 5, 8, 13 ...
μ΄λ°μμΌλ‘ κ°μ₯ μ²μ 0, 1μ μ μΈνκ³ λ΄ μμ λ λμ λν΄μ λλ₯Ό λ§λλ κ²μ΄ νΌλ³΄λμΉ μμ΄μ λλ€.
μ¬κ·ν¨μλ₯Ό μ΄μ©ν ꡬν
func fibo(_ n: Int) -> Int {
if n <= 1 { return n }
return fibo(n - 1) + fibo(n - 2)
}
λ§μ½ μ ν¨μλ‘ fibo(4)λ₯Ό νΈμΆνλ€λ©΄
fibo(0)μ ꡬνλ ν¨μλ₯Ό 2λ² μ€λ³΅ μ€ννκ³ ,
fibo(1)μ ꡬνλ ν¨μλ₯Ό 3λ² μ€λ³΅ μ€ννκ³ ,
fibo(2)λ₯Ό ꡬνλ ν¨μλ₯Ό 2λ² μ€λ³΅μ€νν΄μΌν©λλ€.
νλμ κ²°κ³Ό κ°μ λμΆνλλ° μ€λ³΅λλ κ°μ μ»κΈ°μν΄ μ€νλλ ν¨μκ° λ무 λ§μ΅λλ€.
μ΄λ° λ°©λ²μ μ«μκ° μ»€μ§μλ‘ νλ‘κ·Έλ¨μ μ€νμλλ₯Ό λ¨μ΄λ¨λ¦½λλ€.
λμ κ³νλ²μ μ΄μ©ν ꡬν
λμ κ³νλ²μμλ λ©λͺ¨μ΄μ μ΄μ μ μ¬μ©ν©λλ€.
κ°μ₯ μμ λ¨μλΆν° κ³μ°νκ³ μ μ₯νμ¬, ν° λ¨μ κ°μ λμΆν©λλ€.
λμ κ³νλ²μμλ μμ λ¨μλ₯Ό μ μ₯ν μ μ₯ 곡κ°μ΄ νμν©λλ€.
func fibo(_ n: Int) -> Int{
var cache: [Int] = [0, 1]
for num in 2...n {
cache.append(cache[num - 1] + cache[num - 2])
}
return cache[n]
}
μ΄λ κ² cacheλΌλ μ μ₯ 곡κ°μ νμ©ν΄μ, κ°μ₯ μμ λ¨μ 0, 1λΆν° λμΆλλ κ°μ κ³μ μ μ₯ν΄λκ°λλ€.
λ§μ½ 4λ²μ§Έ μλ₯Ό ꡬνκΈ° μν΄ μλμ κ°μ΄ μ€ννλ©΄
fibo(4)
4λ³΄λ€ μμ κ°λ€μΈ 0, 1, 2, 3λ²μ§Έ κ°κΉμ§λ₯Ό λ¨Όμ ꡬνμ¬ μ μ₯νκ³ ,
μ΄ κ°λ€μ΄ μ μ₯λμ΄ μλ λ©λͺ¨λ¦¬λ₯Ό μ΄μ©νμ¬,
2λ²μ§Έ index + 3λ²μ§Έ indexμ κ°μ λν΄ κ΅¬νλ κ²μ λλ€.
μ΄λ―Έ μ μ₯λμ΄ μλ κ°μ νμ©νλ κ²μ΄κΈ° λλ¬Έμ, μ€λ³΅ μ€ν ν νμκ° μμ΅λλ€.
μ΄λ° κ³Όμ λ€λ‘ μΈν΄ μ€νμλλ₯Ό λΉ¨λΌμ§λλ€.
'π» CS > μκ³ λ¦¬μ¦' μΉ΄ν κ³ λ¦¬μ λ€λ₯Έ κΈ
λΉνΈλ§μ€νΉ (2) | 2023.05.13 |
---|---|
[Swift] λ°±νΈλνΉ (0) | 2023.05.09 |
[Swift] 그리λ(Greedy) μκ³ λ¦¬μ¦ (0) | 2023.04.04 |
[Swift] (λΆν μ 볡) ν΅ μ λ ¬ ꡬνν΄λ³΄κΈ° (0) | 2023.04.03 |
[Swift] κΉμ΄μ°μ νμ(DFS) ꡬνν΄λ³΄κΈ° (0) | 2023.03.30 |