동적 계획법(DP)

정의

• 입력 크기가 작은 부분 문제들을 해결한 후, 해당 부분의 답을 이용해, 전체 크기의 문제를 해결하는 알고리즘
• 상향식 접근법
• Memoization 기법: 프로그램 실행 시, 이전에 계산한 값을 저장하여, 다시 계산하지 않도록 하여 전체 실행 속도를 빠르게 하는 기술

피보나치 수열

피보나치 수열 문제

• 재귀함수 활용

// recursive
func fibo(_ num: Int) -> Int {
    if num <= 1 {
        return num
    }
    return fibo(num - 1) + fibo(num - 2)
}

 

• 동적 계획법 활용

// 동적 계획법
func fiboDP(num: Int) -> Int {
    var caches = [Int].init(repeating: 0, count: num + 1)
    caches[0] = 0
    caches[1] = 1
    
    for index in 2...num {
        caches[index] = caches[index-1] + caches[index - 2]
    }
    return caches[num]
}

 

출처 : 패스트 캠퍼스 알고리즘 / 기술면접 완전 정복 올인원 패키지 Online.