S534 Dynamic Programming, Greedy Algorithm

Dynamic Programming

1. 개념
   • 주어진 문제의 일부를 풀고 그 결과를 재활용하는 방법이다.
   • 하나의 문제를 중복되는 서브 문제로 나누어 푸는 방법.
   • 분할 정복(Divide and Conquer) < 동적 프로그래밍 (Dynamic Programming) 속하는 개념
   • DP는 중복되는 서브 문제가 있지만(그래서 메모이제이션도 활용 가능) 분할 정복은 분할된 서브문제가 독립적이다.

   • 

     동적 프로그래밍과 분할 정복의 관계

2. 방법론
   • 메모이제이션 (하향식)
     • 메인 문제를 분할하면서 해결 하는 방법
     • 코드 구현
       • 피보나치 수열을 구하는 방법을 기준으로 비교해보았다.
       • 피보나치 수열: [1,1,2,3,5,8,,,,] 이런식으로 앞의 두개의 항을 더한 수열을 말한다. 첫번쨰와 두번째 항의 경우 1이 들어가는 것이 원칙이다. 
       • 메모이제이션은 메인을 분할하고 해결하는 하향식 방향이라고 했다. 이미지를 참조해 설명하자면 dp[5]가 피보나치 수열 다섯번째를 구하는 식이라고 하면
         • dp[5] = dp[4] + dp[3] = 3 + 2 = 5
         • dp[4] = dp[3] + dp[2] = 2 + 1 = 3
         • dp[3] = dp[2] + dp[1] = 1 + 1 =  2
         • dp[2] = 1
         • dp[1] = 1
       • 방향은 하향식이지만 문제를 푸는 방식은 스택처럼 풀리는 느낌이다.
         

         

     • def memo_fib(input_value, save_memo):
           """
           문제 1.
               메모이제이션 개념을 사용하여 피보나치 수열을 구하는 함수를 작성해주세요
               input_value 번째 피보나치 수열을 구하는 함수를 작성해주세요
       
               입력값:
                   33
               출력값:
                   3524578
           """
           # if 0,1 1을 넣기.
           if input_value <=2:
               save_memo[input_value] = 1
               return save_memo[input_value]
           # else: memo_fib(input_value,save_memo)
           else:
               save_memo[input_value] = memo_fib(input_value-1,save_memo) + memo_fib(input_value-2,save_memo)
               return save_memo[input_value]

   • 타뷸레이션 (상향식)
     • 가장 작은 문제를 먼저 해결하고 최종적으로 메인문제를 해결하는 법
     • 코드 구현

     • def tabul_fib(input_value):
           """
           문제 1.
               태뷸레이션 개념을 사용하여 피보나치 수열을 구하는 함수를 작성해주세요
               input_value 번째 피보나치 수열을 구하는 함수를 작성해주세요
       
               입력값:
                   33
               출력값:
                   3524578
           """
           result = [0,1]
           if input_value==1:
               return result[input_value]
           for i in range(2,input_value+1):
               value = result[i-2]+result[i-1]
               result.append(value)
           return result[input_value]

Greedy Algorithm

1. 개념
   • 동적 프로그래밍과 차이점은 중복되지 않은 서브문제를 푼다는 것.
   • 최종적으로 최선, 최적의 답을 찾기보다 주어진 상황에서 최선의 선택을 하는 것이다.
   • 그래서 이전의 선택으로 돌아가는 역추적과 반대 개념으로, 다른 문제들과 독립적이다.
2. 활용
   • 여행 짐싸기, 여행 경로 짜기, 마을 전력 공급망 짜기, 잔돈 주기
   • 코드 구현
     • 1000원 이하의 물건을 샀을 때, 잔돈을 거슬러 주는 방법으로 구현해보았다. coin의 값이 높은 순서대로 구하는 걸 원칙으로 삼았다.

   • def changes(price):
         change = 1000 - price
         coin_list = [700, 400, 300, 100, 50, 10]
         change_dict = {}
         while True:
             if change ==0:
                 break
             for i in coin_list:
                 num = change//i
                 if num ==0:
                     pass
                 else:
                     change = change - num*i
                     change_dict[i] = num
         return change_dict​