[자료구조] 8. Dynamic Programming 이해하기(feat. codestates, self tutorial)

 

 

 

 

 

안녕하십니까 다제입니다. 

 

오늘은 Dynamic Programming에 대해서 포스팅을 진행하고자 합니다. 

 

Dynamic Programming은 memoization(하향식 접근)과 Tabulation(상향식 접근)으로 구성되어 있습니다. 

 

먼저 Dynamic Programming에 대해서 살펴본 뒤

memoization(하향식 접근)과 Tabulation(상향식 접근)도 함께 살펴보도록 하겠습니다. 

 

사실 Dynamic Programming은 Divide and Conquer와 매우 유사하지만 사용해야하는 조건이 있습니다. 

 

Dynamic Programming는 

1. 최적부분 구조(Optimal Substructure)가 있고

2. 중복되는 부분 문제(overlapping subproblems)가 있다면 사용하게 됩니다. 

 

최적부분 구조(Optimal Substructure)가 있다는 것은 부분 문제들의 최적의 답을 이용해서 기존 문제의 최적의 답을 구할 수 있다는 것을 의미합니다. 또한, 부분 문제들을 풀다보면 중복되는 부분 문제들이 있을 수 있습니다. 똑같은 문제를 여러번 풀어야한다는 문제가 발생됩니다. 이와 같은 구조로 이루어진 문제를 풀때 Dynamic Programming를 이용하게 됩니다. 

 

 

---

 

 

1. memoization

1) 정의 

 -. 분할된 서브문제를 해결하기 위해, 재귀를 이용하여 하양식으로 반복되는 해결법을 재사용하는 기법이다.

 

2) 특징 

 -. 미리 계산한 값을 재사용하므로 프로그램 실행속도를 빠르게 해준다. 

 -. 동일한 입력을 가진 함수를 처음 호출할 때만 전체 호출 비용이 발생되도록 한다. 

 -. 함수의 시간 복잡도는 감소시키고, 공간 복잡도를 증가시키니다. 

 -. 반복되는 계산 결과를 특정 변수에 저장하여 필요할 때 다시 꺼내서 사용을 한다. 

 

3) 소스코드 

# 메모이제이션을 적용한 경우

# 실행순서 
# n이 5부터 1까지 쭉 recursive_factorial을 들어가게 된다. 
# 이제 recursive_factorial(1)부터 recursive_factorial(5)까지 예산이 진행된다. 
# 이때 recursive_factorial(2)부터는 memo라는 dict에서 데이터가 있는지 없는지를 확인하게 된다.
# 있다면 거기서 바로 정보를 가져오고 없다면 result = n * recursive_factorial(n-1)까지 들어가서 계산이 진행된다. 

memo = {}    # 재사용을 값을 저장하기 위한 딕셔너리 변수

def recursive_factorial(n):
    if n is 0:
        return 1
    elif n in memo:
        return memo[n]   # 메모이제이션
    else:
        result = n * recursive_factorial(n - 1)
        memo[n] = result
        return result

# 1번째 케이스
print("recursive_factorial(5):",recursive_factorial(5)," memo:", memo)

# 2번째 케이스
print("recursive_factorial(4):",recursive_factorial(4)," memo:", memo)


---------------------------------------------------------------------------


# 메모이제이션 적용되지 않은 경우

def recursive_factorial(n): # 최상위 호출
    if n is 0:
        return 1
    else:
        return n * recursive_factorial(n - 1) # 함수 내부

print(recursive_factorial(10))
print(recursive_factorial(4))

 

 

---

 

 

2. Tabulation

1) 정의 

 -. 분할된 서브문제를 해결하기 위해, 반복문을 이용하여 상향식으로 반복되는 해결법을 재사용하는 기법이다.

 

2) 특징 

 -. 중복된 비효율을 제거해주고, 반복문을 사용한다. 

 -. 표를 하나씩 아래에서부터 위로 계산이 진행되기 때문에 n번째까지 계산하려면 n번 계산이 이루어져야 한다. 

 

3) 소스코드 

def fib_tab(n):
    fib_table = {}
    fib_table[1] = 1
    fib_table[2] = 1

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

    return fib_table[n]

 

 

 

지금까지 Dynamic Programming에 대해서 살펴보았습니다. 

 

보시다가 궁금하신 사항이 있으시면 댓글 부탁드립니다. 

 

오늘도 글을 읽어주셔서 감사합니다. 

 

공감과 댓글은 사랑입니다. ㅎ