Greedy Algorithm   탐욕 알고리즘

(2023-12-27)

욕심쟁이 방법, 욕심쟁이 알고리즘, 탐욕적 방법, 그리디 알고리즘


1. 탐욕 알고리즘, 욕심쟁이 알고리즘 (Greedy Algorithm, 그리디 알고리즘) 전략 

  ㅇ 용어 유래
     - 그때그때 상황에 맞는 최상의 해결책을 찾는다는 의미로, `탐욕(Greedy)`이라는 말을 씀

  ㅇ 기본 생각
     - 매 상황 마다 가장 좋아 보이는 것 만 선택하는 방식
        . 완벽한 해결책 보다는 차선책(Suboptimal) 추구
           .. 과거나 미래는 생각 않고, 오직 현재 최대의 만족을 추구 (근시안적임)

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

  ㅇ 주의 사항
     - 최적 해를 구하는 보장이 없으므로, 
     - 최적 해를 얻는지 확인하는 절차 필요


2. 탐욕 알고리즘의 적용 요건

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

  ㅇ 전체 최적 해가, 부 문제(subproblem)들의 최적 해로부터, 생성될 수 있어야 함
     - 부 문제 : 원래 문제와 같은 성질을 갖으나, 그 크기 만 작은 경우
     - 이를, 탐욕 선택 특성 (greedy choice) 또는 컷 특성 (cut) 이라고도 함


3. 탐욕 알고리즘의 특징 및 적용 例)

  ㅇ 주요 특징
     - 적당히 괜찮고 근사적이나, 
     - 매우 빠르게 최적 해를 구할 때 유용

  ㅇ 적용 대상
     - 종종 시간,공간적 제약 때문에 완벽한 해를 찾기 어려워서,
     - 준 최적 해를 찾고자할 때 주로 적용됨 


4. 탐욕 알고리즘의 例)최소값/최대값 등을 구하는 최적화 문제를 다룰 때 적합
  ㅇ 동전 거스름돈을 가장 적은 수의 동전으로 주는 문제 (일명, 거스름돈 문제)
  ㅇ 배낭 내 합이 최대가 되도록 물체를 넣는 방법 (일명, 배낭 문제)
  ㅇ 최소 비용 신장트리를 구하는 알고리즘 (쿠르스칼 알고리즘, 프림 알고리즘) 
  ㅇ 최단 경로 탐색 알고리즘 (다익스트라 알고리즘) 등


5. 주요 접근 단계

  ㅇ 선택 과정 (selection procedure)
     - 현 상태 하에서, 최적 해에 포함시킬 대안(해)들을 선택

  ㅇ 적절성 검사 (feasibility check)
     - 선택된 해가, 주어진 조건을 만족하는지 여부 검사

  ㅇ 해답 점검 (solution check)
     - 원래의 문제가 해결되었는지를 검사

알고리즘 전략
   1. 알고리즘 설계   2. Brute Force   3. 분할 정복법   4. 탐욕 알고리즘   5. 동적 계획법  


Copyrightⓒ written by 차재복 (Cha Jae Bok)               기술용어해설 후원
"본 웹사이트 내 모든 저작물은 원출처를 밝히는 한 자유롭게 사용(상업화포함) 가능합니다"