λ°˜μ‘ν˜•

이 κ²Œμ‹œκΈ€μ€ 개인적인 곡뢀λ₯Ό μœ„ν•΄ μž‘μ„±λœ κ²Œμ‹œλ¬Όμž…λ‹ˆλ‹€.

이 κΈ€μ˜ λͺ¨λ“  μΆœμ²˜λŠ” 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의 값을 더해 κ΅¬ν•˜λŠ” κ²ƒμž…λ‹ˆλ‹€.

이미 μ €μž₯λ˜μ–΄ μžˆλŠ” 값을 ν™œμš©ν•˜λŠ” 것이기 λ•Œλ¬Έμ—, 쀑볡 μ‹€ν–‰ ν•  ν•„μš”κ°€ μ—†μŠ΅λ‹ˆλ‹€.

이런 κ³Όμ •λ“€λ‘œ 인해 싀행속도λ₯Ό λΉ¨λΌμ§‘λ‹ˆλ‹€.

λ°˜μ‘ν˜•
JerryiOS