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

특징

• 탐욕적으로 하는 문제 풀이, 현재 상황에서 지금 당장 좋은 것만 고르는 방법
  but, 반드시 최적의 해를 구할 수 있는 것은 아니다
• 사전에 외우고 있지 않아도 풀 가능성이 높은 문제 유형(다익스트라 알고리즘 경우 암기 필요)
• 창의력(문제를 풀기 위한 최소한의 아이디어)을 요구하는 문제 유형(대표문제 : 거스름돈 계산)

그리디 적용 조건 2가지

1. 탐욕 선택 속성(Greedy Choice Property)
   : 앞서 했던 선택이 이후의 선택에 영향을 주지 않는다
2. 최적 부분 구조(Optimal Substructure)
   : 전체 문제에 대한 최종 해결 방법은 부분 문제에 대한 최적 문제 해결 방법으로 이루어진다

⭐️ 위의 2가지 조건을 모두 성립해야지 최적의 해 구할 수 있다
(조건을 만족하는 상황이라면 계산 속도가 빠르기 때문에 이 알고리즘을 실용적으로 사용할 수 있다)

총정리

그리디 알고리즘이란, 문제를 해결하는 과정에서 항상 최적이라 생각하는 해답을 토대로 최종 해답을 찾는 문제 해결 방식이다
but, 항상 최적의 해를 보장하지 못한다는 점을 알아야 한다