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. 탐욕 알고리즘
  1.   기술공통
  2.   기초과학
  3.   진동/파동
  4.   방송/멀티미디어/정보이론
  5.   전기전자공학
  6.   통신/네트워킹
  7.   정보기술(IT)
        1. 정보기술
    1.   전산기초
    2.   컴퓨터구조
    3.   프로그래밍
          1. 프로그램, 프로그래밍
      1.   프로그래밍 언어론
      2.   프로그래밍 방법론
      3.   객체지향 프로그래밍
      4.   자료표현코드
      5.   자료구조
      6.   알고리즘
            1. 알고리즘
            2. 순서도
            3. 재귀 호출
        1.   알고리즘 효율성
        2.   알고리즘 종류
        3.   알고리즘 전략
          1.   1. 알고리즘 설계
              2. Brute Force
              3. 분할 정복법
              4. 탐욕 알고리즘
        4.   (기타 알고리즘)
      7.   시스템 소프트웨어
      8.   프로그래밍언어 종류
      9.   프로그래밍 기타일반
    4.   데이터베이스
    5.   소프트웨어 공학
    6.   운영체제
    7.   정보보호/보안
    8.   IT 기타기술
  8.   공업일반(기계,재료등)
  9.   표준/계측/품질
  10.   기술경영

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