[Note] 그리디 알고리즘을 알아보자

[saseungmin]

📚 그리디 알고리즘

• 눈앞의 이익만 우선 추구하는 알고리즘을 총칭해서 그리디 알고리즘이라 한다.
• 그리디 알고리즘은 대부분의 경우 뛰어난 결과를 도출하지 못하지만 드믈게 최적해를 보장하는 경우도 있다.
• 그리디 알고리즘은 최적화 문제를 대상으로 한다. 최적해를 찾을 수 있으면 그것을 목표로 삼고, 찾기 어려운 경우에는 주어진 시간 내에 그런대로 괜찮은 해를 찾는 것을 목표로 삼는다.

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

1. 이진 트리의 최적합 경로 찾기
2. 보따리 문제
3. 동전 바꾸기

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

1. 최소 신장 트리
   최소 신장 트리를 위한 프림 알고리즘, 크루스칼 알고리즘은 그리디 알고리즘으로 최적해가 보장되는 예이다.
   최소 신장 트리는 어떤 시점이든지 그 시점에서 집합 S에 가장 싼 비용으로 연결되는 정점을 택한다.

2. 회의실 배정 문제
   JavaScript 예제

3. 그 밖의 예
   그래프에서 최단 경로를 구하는 다익스트라 알고리즘도 그리디 알고리즘이다.
   문서에서 각 원소들의 출현 빈도가 주어질 때 해당 문서를 효율적으로 압축하는 코드를 만드는 허프만 코딩 알고리즘도 그리디 알고리즘이다.

💻 프로그래머스 그리디 문제

• 단속카메라
• 섬 연결하기: 최소 신장 트리