그리디 알고리즘

동현·2021년 3월 29일
0

그리디 알고리즘

그리디 알고리즘이란?
"매 선택에서 지금 이 순간 당장 최적인 답을 선택하여 적합한 결과를 도출하자"

  • 그리디 -> 탐욕이란 뜻으로 말그대로 탐욕알고리즘이다.

  • 그리디 알고리즘은 각 단계에서 최선을 선택하게 되는 알고리즘이며 동적 프로그래밍 이랑 비슷한 부분이 있다. (동적 프로그래밍은 다음 시간에 알아보도록 하겠다)


  • 다음과 같은 그림에서 서울에서 대구를 찾아갈때 가장 최소 거리는?
    • 위와 같은 질문을 만족하기 위해 여러가지 방법이 있을 텐데 그중
      각 도시에서 가장 최소거리에 있는 도시를 찾아가는 방법도 하나의 방법이 될수가 있다.
    • 하지만 이때 이는 각 단계에서는 최선이지만 최종적인 결과 면에서 최선값이라고 볼수는 없다. 이때 이방법을 그리디 알고리즘이라고 한다.
  • 다른 예로는 마시멜로우 예가 있다
      1. 당장 마시멜로 1개를 먹을 수 있다.
      2. 2분뒤에 2개를 먹을 수 있다.
    • 다음과 같은 경우에서는 당장의 기준에서는 1, 0이지만
      미래에는 1, 2이다 하지만 그리디 알고리즘은 각 단계에서의 최선 값을 선택하기 때문에 1을 선택하게 된다. 이경우를 보면 최선 값은 2개지만 결과값은 1이다. 이처럼 모든 부분에 그리디 알고리즘을 적용시켜서는 안된다.

Reference

https://namu.wiki/w/그리디%20알고리즘

profile
여긴 어디 나는 누구?

0개의 댓글