자바 알고리즘 인터뷰 21. 그리디 알고리즘

그리디 알고리즘은 탐욕적 알고리즘으로 해석된다. 그리디 알고리즘은 최적화를 위해서 사용하는 알고리즘이다. 현재 이용 가능한 정보를 기반으로 결정이 내려진다는 것이다. 현재 정보가 무엇이든 현재 결정이 미래에 미칠 영향을 걱정하지 않고 결정이 내려진다. 

 

1.     탐욕적 접근 방식은 전역 최적을 찾기 위해 각 단계에서 지역적으로 최적의 선택을 합니다.

2.     욕심 많은 접근 방식은 현재 선택의 미래 결과를 반드시 고려하지 않습니다.

3.     탐욕적 접근 방식은 각 단계에서 지역적으로 최적의 선택을 하면 전역적으로 최적이 되는 문제를 해결하는 데 유용합니다.

 

대표적인 예시

1. 허프만 코딩

2. 프림 알고리즘

3. 크루스칼 알고리즘

4. 분수 배낭 문제