[알고리즘 기초] 동적계획법(DP)

동적계획법 (Dynamic Programming)

문제를 쪼개서 작은 문제의 답을 구하고 그걸로 더 큰 문제의 답을 구하는 것을 반복

 

1) 정의 : DP함수의 정의

2) 구하는 답 : 문제에서 요구하는 정답 (출력값)

3) 초기값 : DP함수의 초기값

4) 점화식 : DP함수의 점화식

 

 

피보나치 수열

1) 정의 : f(i) : i번째 피보나치 수

2) 구하는 답 : f(n)

3) 초기값 : f(0) = 0
          f(1) = 1

4) 점화식 : f(i) = f(i-2) + f(i-1) if i >= 2

 

1) Bottom-up 방식으로 구현 : 반복문

let input = Int(readLine()!)!

var arr = [Int]()
arr.append(0)
arr.append(1)

for i in 2...90 {
    arr.append(arr[i-2] + arr[i-1])
}
print(arr[input])

 

2) Top-down 방식으로 구현 : 재귀

let input = Int(readLine()!)!

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

재귀를 사용하여 피보나치 수열을 구하면 중복되는 구간이 많아 시간이 많이 걸린다.

n=10일 때를 구하려할때 n=9일때와 n=8일때를 더해주는 값이다. 작은 값은 계속해서 중복된 계산을 하게 되면서 시간 초과가 난다.

이를 해결하기 위해서 메모이제이션을 사용한다

 

메모이제이션 (Memoization)

중복된 부분을 다시 호출하지 않는다

부분 문제들의 답을 한번 구했으면 또 구하지 않도록 캐시에 저장해두고 그 다음에 필요할 때는 가져다 사용한다

let input = Int(readLine()!)!

//캐시를 통해 저장해두고 반복되는 연산은 가져다가 쓴다
var cache = [Int](repeating: -1, count: input + 1)
cache[0] = 0
cache[1] = 1

func fibo(_ num: Int) -> Int {
    if cache[num] < 0 {
        cache[num] = fibo(num - 2) + fibo(num - 1)
    }
    return cache[num]
}

print(fibo(input))

 

 

정리

동적계획법 DP 란 ?

• 문제를 바로 풀기에는 너무 커서 작은 문제의 답을 먼저 구해서
  점점 큰 문제의 답을 구하는 것을 반복하여 원래 문제의 답을 구하는 방식
• 시간/공간복잡도는 보통 DP테이블 크기이다

 

 

 

 

 

2022.08.24 - [분류 전체보기] - [알고리즘] Swift -백준 # 2748 (피보나치 수2) -DP

[알고리즘] Swift -백준 # 2748 (피보나치 수2) -DP