동적계획법(Dynamic Programming)

동적 계획법 (Dynamic Programming, DP)은 복잡한 문제를 더 작은 하위 문제로 나누어 해결한 후, 그 결과를 저장하고 사용하여 큰 문제를 해결하는 알고리즘 설계 기법(최하위에서 해답을 구한 후, 이를 저장하고, 해당 결과값을 이용해서 상위 문제를 푸는 상향식 접근법)이다. 동적 계획법은 특히 최적화 문제를 해결하는 데 효과적이다.

특징

1. 최적 부분 구조 (Optimal Substructure): 큰 문제의 최적 해결 방법이 그것의 하위 문제들의 최적 해결 방법들로부터 구성될 수 있을 때 이 특성이 존재한다.
2. 중복되는 부분 문제 (Overlapping Subproblems): 동일한 하위 문제가 여러 번 발생할 수 있으므로, 이 하위 문제의 결과를 저장하면 후에 다시 계산하지 않아도 되어 연산 시간을 절약할 수 있다.

동적 계획법의 접근 방식

1. Top-down 접근법: 재귀를 사용하여 주어진 문제를 하위 문제로 분해한 후, 하위 문제의 해결 결과를 저장하는 방식이다. 이러한 방식은 일반적으로 메모이제이션 (Memoization)이라고 부른다.
2. Bottom-up 접근법: 가장 작은 하위 문제부터 시작하여 차례로 해결하며, 최종적으로 주어진 문제의 해를 구하는 방식이다. 이러한 방식은 일반적으로 테이블 (Table) 방식이라고 한다.

예시: 피보나치 수열

Top-down접근법(Memoization 활용)

def fibonacci(n, memo={}):
    if n in memo:
        return memo[n]
    if n <= 1:
        return n
    memo[n] = fibonacci(n-1, memo) + fibonacci(n-2, memo)
    return memo[n]

이 코드는 피보나치 수열을 계산하기 위해 메모이제이션을 활용한 재귀적인 방법을 사용한다. 메모이제이션은 이미 계산된 결과를 재사용함으로써 중복 계산을 피하고, 연산 시간을 단축시키는 방법이다.

1. 함수정의

fibonacci 함수는 두 개의 매개변수를 받는다. ('n' (피보나치 수열에서 원하는 n번째 항) 및 'memo' (이미 계산된 피보나치 값들을 저장하는 딕셔너리)) memo는 기본적으로 빈 딕셔너리로 초기화된다.

2. 메모이제이션 체크

if n in memo:
    return memo[n]

'n'에 대한 결과가 이미'memo'에 저장되어 있으면, 그 값을 바로 반환한다. 이로 인해 중복계산을 피할 수 있다.

3. 기본 경우

if n <= 1:
    return n

피보나치 수열의 0번째와 1번째 항은 각각 0과 1이다. 따라서 'n'이 1 이하일 경우 n을 그대로 반환한다.

4. 피보나치 수열 계산.

memo[n] = fibonacci(n-1, memo) + fibonacci(n-2, memo)

피보나치 수열의 n번째 항은 (n-1)번째 항과 (n-2)번째 항의 합이다. 재귀적으로 fibonacci 함수를 호출하여 이 값을 계산하고, 결과를 memo에 저장한다.

5. 결과 반환

return memo[n]

계산된 피보나치 수열의 n번째 항을 반환한다.

Bottom-up 접근법(테이블 방식 활용)

def fibonacci(n):
    if n <= 1:
        return n

    dp = [0] * (n+1)
    dp[1] = 1

    for i in range(2, n+1):
        dp[i] = dp[i-1] + dp[i-2]

    return dp[n]

분할 정복 (Divide and Conquer)

분할 정복(Divide and Conquer)은 복잡한 문제를 더 작은 하위 문제로 분할하여 각각의 하위 문제를 해결한 후, 그 결과를 합쳐서 원래의 문제를 해결하는 알고리즘 설계 전략이다. 이 방법은 주로 재귀적인 방식으로 구현된다.

분할 정복의 주요 단계

1. 분할(Divide): 주어진 문제를 더 작은 하위 문제들로 분할한다.
2. 정복(Conquer): 하위 문제를 재귀적으로 해결한다. 하위 문제의 크기가 충분히 작아질 경우, 직접 해결할 수 있도록 한다 (Base case에 도달).
3. 결합(Combine): 하위 문제의 해결 결과를 합쳐서 원래의 문제를 해결한다.

분할 정복의 예시

병합 정렬(Merge Sort)

• 분할: 리스트를 두 개의 동일한 크기의 서브리스트로 분할한다.
• 정복: 서브리스트를 재귀적으로 병합 정렬하여 정렬한다.
• 결합: 두 개의 정렬된 서브리스트를 합쳐서 하나의 정렬된 리스트를 만든다.

장점 및 단점

• 장점: 문제를 더 작은 조각으로 나눔으로써, 해결이 간편해질 수 있습니다. 병렬화가 가능한 경우에도 유용하다.
• 단점: 함수 호출에 따른 오버헤드가 있을 수 있으며, 재귀적 구조 때문에 스택 오버플로우의 위험이 있다.

분할 정복은 문제를 개별 부분으로 나누어 해결하는 방식이기 때문에, 문제의 특성에 따라 매우 효율적인 해결 방법이 될 수 있다.

동적계획법과 분할정복의 공통점과 차이점

두 방법론은 모두 복잡한 문제를 작은 문제로 분해하여 해결하는 방법론이지만, 그 접근 방식과 사용되는 문제 유형에서 차이가 있다.

	동적 계획법	분할 정복
정의	문제를 더 작은 하위 문제로 나눈 다음, 각 하위 문제의 결과를 저장하고 이를 활용하여 원래의 문제를 해결하는 방법.	문제를 동일한 유형의 더 작은 하위 문제로 나눈 후, 각 하위 문제를 독립적으로 해결하여 원래의 문제를 해결하는 방법.
접근방식	문제의 최적해를 위해 이전에 계산한 하위 문제의 해를 재사용한다. (메모이제이션 활용)	문제를 더 작은 하위 문제로 분할하고, 이 하위 문제들을 독립적으로 해결한 후 결과를 합쳐 원래의 문제를 해결한다.
메모리 사용	하위 문제의 해결 결과를 저장하기 위한 메모리가 필요하며, 이를 배열이나 테이블 형태로 저장한다.	보통 재귀적 구조를 활용하므로, 스택 메모리를 사용한다.
중복 문제의 해결	중복되는 하위 문제가 많이 있으므로, 이를 해결하기 위해 결과를 저장하고 재사용한다. (중복 해결의 주된 방식)	일반적으로 하위 문제들이 중복되지 않는다.
장단점	중복된 하위 문제의 계산을 피하기 때문에 시간을 절약할 수 있습니다. 그러나 메모리 사용량이 증가할 수 있다.	문제를 분할하여 독립적으로 해결하기 때문에 병렬 처리에 적합할 수 있다. 그러나 중복되는 하위 문제가 발생할 경우 비효율적일 수 있다.

이 두 기법 모두 복잡한 문제를 더 작고 간단한 하위 문제로 분해하는 공통적인 전략을 사용하지만, 그 방법과 처리 과정에서의 차이점이 있다.

피보나치 수열 풀이(recursive call, 동적 계획법)

# recursive call활용
def fibo(num):
    if num <= 1:
        return num
    return fibo(num - 1) + fibo(num - 2)

fibo(4) # 3

# 동적 계획법 확용
def fibo_dp(num):
    cache = [ 0 for index in range(num + 1)]
    cache[0] = 0
    cache[1] = 1
    
    for index in range(2, num + 1):
        cache[index] = cache[index - 1] + cache[index - 2]
    return cache[num]
 
fibo(10) # 55