자료구조 & 알고리즘 (그리디)

그리디

매 선택에서 지금 이 순간 가장 최적의 답을 선택하는 알고리즘

최적해를 보장해주지 않는다.

그리디 알고리즘의 특징

▶ 보통 최적해를 구하는 알고리즘보다 빠른 경우가 많다

▶ 크루스칼, 다익스트라 알고리즘 등에 사용된다.

▶ 직관적인 문제 풀이에 적합하다.

동전 반환 문제

큰 단위인 지폐, 동전 순으로 거스름돈을 만들면 된다.

가장 쉽고 직관적인 그리디 문제