그리디 알고리즘

눈 앞의 이익만 우선 추구하는 알고리즘을 총칭하는 말

주의할 점

그리디 알고리즘의 경우 가장 좋아보이는 선택을 했을 때 최적 해가 나오는 지에 대한 지속적인 검증이 필요하다.

그리디 알고리즘으로 최적해가 보장되지 않는 예

이진 트리의 최적합 경로 찾기

이진 트리에서는 전체의 합이 가장 큰 것을 찾으려면 전체적은 트리를 전부 봐야하기 때문에 그리디로 최적해를 낼 수 없는 직관적인 예

보따리 문제(Knapsack)

보따리의 부피를 넘지 않으면서 최대 가치를 가지는 물건들을 넣는 알고리즘

동전 문제

가장 적은 수의 동전을 사용해서 물건을 사는 알고리즘
그리디로 해결하려면 다음과 같은 조건이 필요하다.

• 모든 동전들이 한 단계 작은 동전의 배수로 이루어져 있어야한다.

그리디 알고리즘으로 최적해가 보장되는 예

최소 신장트리

최소 신장트리를 위한 프림, 크루스칼 알고리즘

회의실 배정 문제

1개의 회의실에서 n개의 회의신청에 대해 가장 많은 수의 회의를 할 수 있게 하는 문제

• 해당 문제는 회의 종료 시간대로 정렬한 후 종료 시간을 기준으로 그리디를 실행한다.
  정한 후 이에 겹치지 않는 시간을

다익스트라 알고리즘