탐욕(그리디) 알고리즘(greedy algorithm)

6mn12j·2020년 9월 3일
0

탐욕 알고리즘

  • 각 단계에서 가장 최선의 방법을 선택하는 알고리즘 방법으로. 여러 경우 중 하나를 선택할 때 그것이 그상황에서 최선이라고 생각하는 것을 선택해 나가는 방법으로 진행하여 답을 구한다.

  • 각 단계에서 최선의 방법을 선택해 나가기 때문에 항상 가장 좋은 결과를 얻는 것이 보장 되는 것은 아니다.

가장 최적의 해는 파랑색을 따라가서 128을 얻는 경우이지만 그리디 알고리즘은 8과 15중 15를 선택해 26을 얻는 주황색의 경우를 따른다.

  • 그리디 알고리즘은 기본적으로 최선 ( 가장 큰 경우,가장 작은 경우, 가장 긴 경우, 가장 짧은 경우 등)극단적으로 문제에 접근 하기 때문에 정렬(Sort)와 많이 사용하는 경우가 많다.
  • 탐욕 알고리즘 활용

    1.최소수의 동전 으로 거스롬돈 거슬러 주기

    동전은 큰 단위의 동전을 우선으로 거스름돈을 구성 시 최소수의 동전이 됨.
    가장 큰 단위의 동전을 골라서 추가 한 후 금액을 초과한다면 가장 최근의 동전을 삭제하고 다시 돌아가서 한 단계 아래 단위의 동전을 추가.

    profile
    TIL 쩨끼럽 남기는 중 💻

    0개의 댓글