[JAVA] 그리디 알고리즘 (탐욕 알고리즘, Greedy Algorithm)

매 선택에서 지금 이 순간 당장의 최적인 선택을 하여 적합한 결과를 도출하는 알고리즘 기법이다.

기본적으로 무조건 큰 경우, 무조건 작은 경우, 무조건 짧은 경우 등 극단적으로 문제에 접근하므로 정렬(Sort)이 함께 이용되는 경우가 많다.

 

특수한 조건 2가지를 만족해야 사용할 수 있다.

1) 탐욕 선택 속성 (Greedy Choice Property)

• 이전의 선택이 이후에 영향을 주지 않는다.

2) 최적 부분 구조 (Optimal Substructure)

• 부분 문제의 최적 결과가 전체에도 그대로 적용될 수 있어야한다.

 

 

그리디 알고리즘을 활용한 백준 문제를 풀어보자.

2022.11.27 - [JAVA/알고리즘 공부] - [백준 JAVA] 2839번: 설탕 배달