동적 계획법과 분할 정복 정리

👩‍💻 동적 계획법과 분할 정복 정리 with Python

🥘 동적 계획법 (Dynamic Programming)

동적 계획법, Dynamic Programming이란?

• 입력 크기가 작은 부분 문제들을 해결한 후, 해당 부분 문제의 해를 활용해서, 큰 부분 문제를 해결하고 최종적으로 전체 문제를 해결하는 알고리즘 기법입니다.
• 상향식 접근법으로 가장 최하위 해답을 구한 후 이를 저장하고,
  해당 결괏값을 이용해 상위 문제를 풀어가는 방식을 활용합니다.
• Memoization 기법을 활용합니다.
  Memoization (메모이제이션) : 프로그램 실행 시 이전에 계산한 값을 저장하며,
  다시 계산하지 않도록 하여 전체 실행 속도를 빠르게 하는 기술입니다.
• 문제를 잘게 쪼갤 때, 부분 문제는 중복되어 재활용됩니다.

 

🍀 Memoization 활용 예시

피보나치수열을 계산하는 알고리즘

 

 

🍀 Memoization을 활용하지 않은 코드

def fibo(value):
    if value <= 1:
        return value

    else:
        return fibo(value - 1) + fibo(value - 2)

시간 복잡도는 O(n^2)

 

 

🍀 Memoization을 활용한 코드

# Memoization
def fibo(value):
    list = [0 for i in range(value + 1)]
    list[0] = 0
    list[1] = 1

    for i in range(2, value + 1):
        list[i] = list[i - 1] + list[i - 2]
    return list[value]

시간 복잡도는 O(n)

 

Memoization은 중복되는 계산을 다시 계산하지 않기 때문에

기존의 알고리즘보다 속도가 매우 빠를 수밖에 없습니다.

 

🍳 분할 정복 (Divide And Conquer)

분할 정복, Divide And Conquer 이란?

• 문제를 나눌 수 없을 때까지 나누어서 각각 풀면서 다시 합병하여 문제의 답을 얻는 알고리즘입니다.
• 하양식 접근법으로 상위의 해답을 구하기 위해 아래로 내려가면서 하위의 해답을 구하는 방식입니다.
• 일반적으로 재귀 함수로 구현됩니다.
• 문제를 잘게 쪼갤 때, 부분 문제는 동적 계획법과 달리 중복되지 않습니다. 
  즉 Memoization 기법을 사용하지 않습니다.

분할 정복의 대표적인 예시 : Quick Sort, Merge Sort

 

🍪 동적 계획법 VS 분할 정복법

공통점

• 문제를 잘게 쪼개서, 가장 작은 단위로 분할합니다.

 

차이점

 동적 계획법

• 부분 문제는 중복되어서, 상위 문제 해결 시에 재활용됩니다.
• 문제가 재활용되기에 재활용되는 문제를 계산하지 않기 위해 Memoization 기법을 활용합니다.

 분할 정복

• 부분 문제는 중복되지 않습니다.
• Memoization 기법을 활용하지 않습니다.

 

동적 계획법, 분할 정복법의

가장 큰 차이점은 Memoization기법을 활용하냐 활용하지 않느냐입니다.