Greddy algorithm

cch_chan·2022년 7월 2일
0

알고리즘

목록 보기
1/3

정의

그리디 알고리즘은 탐욕 알고리즘 또는 욕심쟁이 알고리즘이라고도 불리는데요. "미래를 생각하지 않고 지금 이 순간 당장 최적인 답을 선택하여 적합한 결과를 도출하자"를 모토로 하여, 각 단계에서 최선의 선택을 한 것이 전체적으로도 최선이길 바라는 알고리즘

사용처

  • 탐욕 선택 속성(greedy choice property)
  • 최적 부분 구조(optimal substructure)

한번의 선택이 다음 선택에는 전혀 무관한 값이어야 하며 매 순간의 최적해가 문제에 대한 최적해여야 한다는 의미이다.

단점

  • 100% 최적해를 보장해주지 않는다.
    : 예시로 매 순간 최적을 따라가면 1-1-1-100라는 순서로 가는데, 중간에 1-1-10-10으로 움직이는 것이 더 빠를 수 있기 때문에

주로 사용 되는 문제들

  • AI에 있어서 결정 트리 학습법(Decision Tree Learning)
  • 활동 선택 문제(Activity selection problem)
  • 거스름돈 문제
  • 최소 신장 트리(Minimum spanning tree)
  • 제약조건이 많은 대부분의 문제
  • 다익스트라 알고리즘
  • 허프만 코드
  • 크러스컬 알고리즘
profile
꾸준히 새로운 기술을 배워나가는중입니다.

0개의 댓글