탐욕 알고리즘 vs. 동적 계획법

  • 최적화 문제를 해결하여라.
  • 탐욕 알고리즘은 동적 계획처럼 작은 부 문제들로 나뉘어지지 않는다.
  • 탐욕 알고리즘은 순서대로 답을 하나씩 모아서 최종 답을 구축하는데, 가장 좋아보이는 답을 선택하여 모은다.
  • 지역적으로는 최적이다.
  • 결정된 선택은 재 고려 대상이 아니다.
  • 과거와 미래의 선택은 현재 선택의 영향을 끼치지 않는다.

탐욕 알고리즘 접근 방법

  • 공집합에서 시작한다.
  • 그 집합이 문제의 해답이 될 때까지 원소를 그 집합에 차례로 추가한다.

절차

  1. 선택 과정(Selection procedure):선택과정 집합(set solution)에 추가할 다음 원소를 고른다. 그 당시 최적을 선택하는 탐욕(greedy)기준에 따라 선택한다.
  2. 적절성 검사(Feasibility Check)): 새로운 집합이 해답이 되기 적절한지 검사한다.
  3. 해답 점검(Solution Check): 새로운 집합이 문제의 최적의 해답인지를 결정한다.

예) 거스름돈 계산하기 문제

  • 문제 : 동전의 개수가 최소가 되도록 거스름 돈을 주는 문제
  • 가정 : 무제한의 동전 개수
  • 탐욕적인 알고리즘:
    • 거스름돈을 x라 하자.
    • 먼저, 가치가 가장 높은 동전부터 x가 초과하지 않도록 계속 내준다.
    • 이 과정을 가치가 높은 동전부터 내림순으로 총액이 정확히 x가 될 때까지 계속한다.

그래프

  • 가중치 포함 그래프(weighted graph)
  • 순환 경로(cycle)
  • 순환적 그래프(cyclic graph), 비 순환적 그래프(acyclic graph)
  • 트리(tree):비 순환적이며, 비 방향성 그래프
  • 뿌리 있는 트리(rooted tree) : 한 정점이 뿌리로 지정된 트리