동적 계획법(DP), 분할 정복

• 동적 계획법
  • 입력 크기가 작은 부분 문제들을 해결한 후, 해당 부분 문제들의 해를 활용해서 보다 큰 크기의 부분 문제들을 해결한다. 마지막에는 전체 문제를 해결하는 알고리즘이다.
  • 상향식 접근법이다. 가장 최하위 문제의 해답을 구한 다음, 이를 저장하고, 결과값을 활용해서 상위 문제를 풀어가는 방식이다.
  • Memoization 기법을 사용한다.
    • 프로그램 실행 시 이전에 계산한 값을 저장하여, 다시 계산하지 않아 전체 실행 속도를 줄이는 기술이다.
  • 예시 : 피보나치 수열
• 분할 정복
  • 문제를 나눌 수 없을 때까지 나누어서 각각을 풀면서 다시 합병하여 문제의 답을 얻는 알고리즘이다.
  • 하향식 접근법이다. 상위의 해답을 구하기 위해 아래로 내려가면서 하위의 해답을 구하는 방식이다.
    • 일반적으로 재귀함수로 구현한다.
  • 문제를 잘게 나눌 때, 부분 문제들은 서로 중복되지 않는다.
  • 예시 : 병합 정렬, 퀵 정렬

공통점과 차이점

• 공통점
  • 문제를 잘게 나누어서, 가장 작은 단위로 분할한다.
• 차이점
  • 동적 계획법
    • 부분 문제는 중복되어, 상위 문제 해결 시 재활용된다.
    • Memoization 기법을 사용한다.
  • 분할 정복
    • 부분 문제들은 중복되지 않는다.
    • Memoization 기법을 사용하지 않는다.

동적 계획법 알고리즘 예제

• 피보나치 수열 : n을 입력받았을 때, 피보나치 수열로 결과값을 출력하시오.
  
  

fibo(0) = 0
fibo(1) = 1
fibo(2) = 1
fibo(3) = 2
fibo(4) = 3
fibo(5) = 5
fibo(6) = 8
fibo(7) = 13
fibo(8) = 21

재귀 용법(Recursive Call) 활용

def fibo(num):
    if num <= 1:
        return num
    else:
        return fibo(num-1) + fibo(num-2)

동적 계획법(DP) 활용

def fibo_dp(num):
	# Memoization 기법
    dp_cache = [0 for _ in range(num+1)]
    dp_cache[0] = 0
    dp_cache[1] = 1
    for i in range(2, num+1):
        dp_cache[i] = dp_cache[i-1] + dp_cache[i-2]
    return dp_cache[num]

• num 값을 작게 했을 때는 돌아가는 시간이 비슷하지만, num 값을 크게 하였을 때는 돌아가는 시간 차이가 크게 난다.
  • num = 40일 때 재귀 용법은 19초가 걸렸지만, 동적 계획법은 n = 500 이여도 0.000- 초가 걸렸다.