Greedy Algorithm   탐욕 알고리즘

(2019-12-18)

욕심쟁이 방법

1. 탐욕 알고리즘 (Greedy Algorithm) 전략 

  ㅇ 기본 생각
     - 완벽한 해결책 보다는 차선책(Suboptimal)
        . 최적 해를 구하는 보장이 없으므로, 최적 해를 얻는지 확인하는 절차 필요
     - 그때그때 상황에 맞는 최상의 해결책을 찾는다는 의미로 `탐욕(Greedy)`라는 말을 씀
        . 과거나 미래는 생각 않고, 오직 현재 최대의 만족을 추구(근시안적임)

  ㅇ 접근 방식
     - 그때그때 가장좋은 해결핵을 찾아가는 기법
     - 해를 구하는 일련의 선택 과정 마다,
        . 가장 좋아보이는 최선을 선택하면, 전체적으로 최적 해를 구할 수 있다는 방법론
        . 각 단계 마다 최상으로 보이는 해결책으로 구한 해들을 모아 제시하게 됨
     - 주요 단계
        . 선택 과정 (selection procedure)
        . 적절성 검사 (feasibility check)
        . 해답 점검 (solution check)

  ㅇ 주요 특징
     - 적당히 괜찮고 근사적이나, 매우 빠르게 최적 해를 구할 때 유용
     - 최소값/최대값을 구하는 최적화 문제를 다룰 때 적합

  ㅇ 문제의 성질
     - 주어진 문제가, 최적 부분 구조 (Optimal Substructure)를 갖춰야 함
        . 큰 문제의 해답에 그보다 작은 문제의 해답이 포함되어 있는 경우
           .. 이런 최적 부분 구조의 경우, 재귀호출로 쉽게 구현 가능하나, 항상 효율적이지는 않음
        . 전체 최적 해가, 부 문제(subproblem)들의 최적 해로부터 생성될 수 있어야 함

  ㅇ 例)
     - 동전 거스름돈을 가장 적은 수의 동전으로 주는 문제 
     - 최소비용 신장트리를 구하는 알고리즘(크루스칼 알고리즘,프림 알고리즘) 등


[알고리즘 전략] 1. 알고리즘 설계 2. Brute Force 3. 분할 정복법 4. 탐욕 알고리즘

 
        최근수정     요약목록     참고문헌