알고리즘(8) - 동적 프로그래밍(Dynamic Programing), 그리디(Greedy)

안녕하세요.

 

오늘은 알고리즘의 마지막 시간입니다. 그동안 많은 알고리즘과 자료구조에 대해서 알아보았는데요.

알아본 내용 이외에도 몬테카를로 알고리즘이나 퍼셉트론 알고리즘과 같이 수많은 알고리즘이 존재합니다.

 

오늘 동적 프로그래밍과 그리디를 정리하고나서 추후에 시간이 나는 경우 하나하나 정리하는 시간을 가지려고 합니다.

 

그렇게 오늘은 동적 프로그래밍(Dynamic Programing)과 그리디(Greedy)(탐욕 알고리즘) 에 대해서 살펴보겠습니다.

 

 

동적 프로그래밍(Dynamic Programing)

 

 

동적 계획법은 동적 알고리즘, 동적 프로그래밍, 다이나믹 프로그래밍 등등 다양한 용어로 사용되는데, 보편적 의미는 '문제의 일부분을 풀고 그 결과를 재활용하는 방법' 입니다.

 

이러한 개념은 이전에 배운 '분할정복'의 개념과 비슷합니다. (추가적으로 분할정복에 대해서 궁금하시다면 아래 링크를 들어가주세요.)

2021.11.30 - [AI일별 정리] - 알고리즘(4) - 퀵정렬, 병합정렬 (Quick sort, Merge sort)

 

동적 계획법은 주로 어디에서 사용되는 방법일까요?

 

동적 계획법을 사용하게 되는 상황으로는 이진 검색, 최단경로 알고리즘, 최적화 문제, 외판원 문제에서 사용됩니다.

 

 

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

 

동적 계획법은 문제를 분할하는 경우에 Subproblems(서브문제)가 중복됩니다.

반대로 분할정복의 경우에는 서브문제는 독립적 입니다.

 

다시 말하면, 동적 계획법과 분할 정복의 차이는 문제를 나누는 방식입니다. 동적 계획법에서는 어떤 부분 문제는 두 개 이상의 문제를 푸는데 사용될 수 있기 때문에, 이 문제의 답을 여러 번 계산하는 대신 한 번만 계산하고 그 결과를 재활용함으로써 속도의 향상을 시킬 수 있습니다. 이때 이미 계산한 값을 저장해 두는 메모리를 캐시(cache)라고 부르며, 두 번 이상 계산되는 부분 문제를 중복되는 서브문제(overlapping subproblems)라고 부른다.

 

 

위에 말씀드린 것처럼 DP는 분할정복과 비슷한 개념을 가지고 있습니다. 그러나 DP를 활용할 수 있으려면 두가지의 조건을 충족해야 가능합니다.

 

1. 중복된(반복되는) 서브문제 (Overlapping Subproblems)

 : 전체 큰 문제와 분할된 서브문제는 같은 방법으로 해결이 가능해야합니다.

 

2. 최적 부분 구조 (Optimal Substructure)

 : 전체 큰 문제의 해결을 위해서 그 해결방법을 분할된 서브문제에서 구하여 재사용하여야 하는 구조여야 합니다.

 

 

이렇게 두가지 조건이 충족되면 문제는 중복되는 서브문제들로 이루어진 구조를 띄게 되는데 이 중복되는 서브문제를 풀 때, 중복되는 문제도 다시 풀어가는 방법은 매우 비효울적이라고 볼 수 있습니다.

 

그래서 DP에서는 효율적으로 문제를 해결하기 위해 2가지의 방법을 사용할 수 있습니다.

 

 

동적 계획법의 방법론

 

1. 메모이제이션(Memoization) - 하향식 접근법

 

DP는 중복된 문제를 해결하기 때문에 중복된 문제를 해결한 적이 있다면 그 내용을 저장하여 다음 같은 문제를 마주쳤을 때 연산을 할 필요가 없이 저장된 값을 불러내어 효율성을 늘리는 방법입니다.

 

메모이제이션은 하향식 접근법으로 위에서 아래로 문제들을 분할하면서 풀어가는 접근법으로 재귀를 사용하여 문제를 해결합니다.

 

#메모이제이션 개념을 사용하여 피보나치 수열을 구하는 함수
def fibonacci_memo(input_value, save_memo):
    # base case
    if input_value <= 0:
      return 0
    if input_value ==1 :
      return 1
      
  # checking if already calculated 이미 연산된 문제인지 확인합니다.
    elif input_value in save_memo:
        return save_memo[input_value]
 
  # storing the result and returning 연산한 문제는 메모리에 저장해줍니다.
    else:
        save_memo[input_value] = fibonacci_memo(input_value-2,save_memo) + fibonacci_memo(input_value-1,save_memo)
	#재귀를 사용하여 연산값들을 하나하나 저장해줍니다.
    return save_memo[input_value]

 

 

2. 타뷸레이션(tabulation) - 상향식 접근법

 

타뷸레이션은 이미 모든 문제에 대한 연산을 해놓고 저장하여 필요할 때에 불러내서 해결하는 방법입니다.

 

상향식 접근법으로 작은 문제부터 해결하여 큰 문제를 해결하는 접근법으로 반복문을 사용하여 구현합니다.

 

#타뷸레이션으로 피보나치수열 구현하기
def fibonacci_tabul(input_value):
    # base case
    tab = [0,1]

    for i in range(input_value):
        new = tab[-1] + tab[-2]
        tab.append(new)
    
    return tab[input_value]

 

 

Greedy(탐욕 알고리즘)

 

그리디(Greedy)란,

 

동적 프로그래밍,backtracking(역추적) 사용 시 지나치게 많은 연산을 한다는 것을 보완하기 위해 고안된 알고리즘입니다. 동적 프로그래밍을 대체하는 것은 아닙니다.

 

탐욕 알고리즘은 여러 문제들을 독립적으로 해결하며 매순간순간 최선의 선택을 하는 알고리즘입니다.

 

이러한 방법은 해결해야할 문제들을 빠르게 해결해나갈 수 있지만, 최종적으로 최고의 선택이 되지 않을 수 있습니다.

 

 

탐욕 알고리즘의 사용예시

 

• 여행짐싸기(물건담기), 여행경로 짜기(도시방문), 전력망 연결(전력공급), 잔돈 구하기, 활동 선택 문제, 분할가능 배낭문제 등등

 

def change_money(price):
    change = 10000 - price
    coin_list = [700, 400, 300, 100, 50, 10]
    
    change_count = {}   # 잔돈갯수

    while change != 0:
        for coin in coin_list:
            change_bool = 0
            change_bool = change_bool + (change // coin)
            if change_bool == 0:
                pass
            else :
                change_count[coin]=change_bool
                change = change - (change_bool * coin)
    return change_count