[알고리즘] 동적 계획법(DP)과 탐욕 알고리즘(Greedy)이란?

Posted on | In
알고리즘 개념을 숲을 보는 시점으로 생각하고 동적 계획법(Dynamic Programming)과 탐욕 알고리즘(Greedy)에 대한 개념

다이나믹 프로그래밍(Dynamic Programming)

  • 프로그래밍과 연관지어 생각하고, 완성한 코드를 분석하는 습관은 중요하다.
  • 문제를 해결하기 위해 핵심적으로 다뤄지는 다이나믹 프로그래밍과 그리디(Greedy)에 대해 알아본다.

동적 계획법

  • 동적 계획법은 동적 알고리즘, 동적 프로그래밍, 다이나믹 프로그래밍 등 다양한 용어로 사용되는데, 보편적 의미는 ‘문제의 일부분을 풀고 그 결과를 재활용하는 방법’이다.
    • 하나의 문제를 중복되는 서브 문제로 나누어 푸는 방법이다.
    • 분할 정복(Divide and Conquer)과 유사한 개념이다.
  • 새로운 알고리즘이나 방법론을 알게 되었을 때 기존에 완성한 간결한 코드를 분석하고 이해하는 것이 좋다.
    • DP는 알고리즘에서 재귀와 함께 사용되기 때문에 코드를 분석하면서 흐름을 이해해야 한다.

동적 계획법을 사용하게 되는 상황

  • 이진 검색
  • 최단 경로 알고리즘
  • 최적화 문제
  • 외판원 문제

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

image

  • 동적 계획법에는 분할 정복에 아래 개념이 추가된다.
  • 반복되는 서브 문제(Overlapping Subproblems)
    • 메인과 서브 문제를 같은 방법으로 해결할 수 있어야 한다.(문제 해결 관점)
  • 최적 부분 구조(Optimal Substructure)
    • 메인 문제 해결 방법을 서브 문제에서 구하여 재사용하는 구조여야 한다.(문제의 구조 관점)
  • 동적 계획법은 최적 부분 구조로 구성된 중복된 서브 문제를 분할 정복으로 해결한다.

동적 계획법의 두가지 방법론

메모이제이션(하향식 방법)

  • 메인 문제를 분할하면서 해결하는 방법이다.

태뷸레이션(상향식 방법)

  • 가장 작은 문제를 먼저 해결하고 최종적으로 메인 문제를 해결하는 방법이다.

피보나치 수열 개념 적용 소스 코드

메모이제이션

1
2
3
4
5
6
7
8
9
def memo_fib(input_value, save_memo):
    """
        메모이제이션 개념을 사용하여 피보나치 수열을 구하는 함수
    """
    if input_value < 2: return input_value
    elif input_value in save_memo: return save_memo[input_value]
    else:
        save_memo[input_value] = memo_fib(input_value - 1, save_memo) + memo_fib(input_value - 2, save_memo)
        return save_memo[input_value]

태뷸레이션

1
2
3
4
5
6
7
8
def tabul_fib(input_value):
    """
        태뷸레이션 개념을 사용하여 피보나치 수열을 구하는 함수
    """
    tabul = [0, 1, 1]
    for i in range(3, input_value + 1):
        tabul.append(tabul[i - 1] + tabul[i - 2])
    return tabul[input_value]

그리디(Greedy)

탐욕 알고리즘

  • DP가 중복되는 서브 문제를 다뤘다면, 그리디는 중복되지 않는 서부 문제를 다룬다.
  • 탐욕 알고리즘은 발견법(heuristic method)의 방법 중 하나이다.
    • 발견법: 최선, 최적의 답을 찾기보다 주어진 상황을 한단계씩 빠른 시간 내에 해결하기 위해 사용하는 방법론이다.
    • 역추적(backtracking)과 같이 알고리즘 수행 시간이 많이 걸릴 때 사용하는 방법이다.
  • 탐욕법은 이전의 선택으로 돌아가는 역추적과는 반대개념으로 다른 문제들과 독립적이다.
  • 어떠한 문제가 있을 때 단순 무식하게, 탐욕적으로 문제를 푸는 알고리즘이다.
    • 현재 상황에서 지금 당장 좋은 것만 고르는 방법을 의미한다.

실제 상황 예시

여행 짐 싸기

  • 여행 배낭에 물건을 정해진 시간 내에 담으려는 경우, 우선 순위가 높은 순서대로 물건을 담을 때 한번 배낭에 담은 물건은 다시 빼지 않는다.

여행 경로 짜기

  • 도시가 많아질수록, 도시를 방문할 수 있는 가짓수가 많아진다.
  • 알고리즘 연산 비용도 함께 증가한다. 이런 상황에서 탐욕 알고리즘을 활용한다.
    • 방문하지 않은 도시 중 가장 가까운 도시로 간다.
    • 모든 도시를 방문할 때까지 반복한다.

전력망 연결

  • 발전소 한 개로 여러 마을에 전력을 공급하는 경우, 최소 비용을 들여 모든 마을에 전력을 공급하려면,
    • 전력이 공급되지 않은 마을과 공급되는 마을의 사이가 가장 가까운 것을 골라, 두 마을을 연결한다.
    • 모든 마을에 전력이 공급될 때까지 반복한다.

파이썬 예제

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24


def changes(price):
    """
        물건 값을 입력하면 '잔돈갯수' 만을 출력
        받은 잔돈의 종류와 종류별 잔돈갯수를 출력하기 위한 코드

        입력값:
            100
        출력값:
            {700: 1, 100: 2}
    """
    change = 1000 - price
    coin_list = [700, 400, 300, 100, 50, 10]
    result = {}
    for residual in coin_list:
        count = 0
        if residual > change:
            continue
        while change >= residual: # 잔여 돈이 코인 보다 작을 때 까지 반복
            change -= residual
            count += 1
        result[residual] = count
    return result

DP와 Greedy

  • 최적 부분 구조 문제를 푼다는 점에서 비교된다.

DP

  • 문제를 작은 단위로 분할하여 해결한 후, 해결된 중복 문제들의 결과를 기반으로 전체 문제를 해결한다.

Greedy

  • 각 단계마다 최적해를 찾는 문제로 접근한다.
  • 해결해야 할 전체 문제의 갯수를 줄이기 위해 개별적으로 문제를 해결해나가는 선택을 한다.

참조

0%