그리디 알고리즘

그리디 알고리즘이란?

---

그리디 알고리즘은 보통 탐욕법이라고 한다. 

말 그대로 문제를 해결할 때 현재 경우만 고려해서 최적의 상황을 선택하는 방법이다. 

 

그리디 알고리즘 성립 조건 2가지

---

하지만 당연하게도 항상 사용할 수 있는 방법은 아니기 때문에 아래의 2가지 조건이 성립된다면 그리디 알고리즘을 기계적으로 적용할 수 있다. 

 

1. 현재의 최적의 선택이 다음 선택에 영향을 미치지 않는다.

2. 현재의 선택이 최종 선택의 최적 해결 방법에 포함된다. 

 

그리디 알고리즘 문제를 해결하는 방법

---

1. 현재 상태에서의 최적의 해답을 선택한다.

2. 선택된 해가 문제의 조건을 만족하는지 검사한다. 

3. 원래의 문제가 해결되었는지 검사하고, 해결되지 않았다면 1번으로 돌아가 위의 과정을 반복한다. 

 

그리디 알고리즘 예시

---

일반적인 코딩 테스트 정도의 레벨에서 나오는 유형은 한정되어 있기 때문에 자주 나오는 몇 가지 상황에 대해 그리디로 해결할 수 있음을 알고 있는 것이 좋다.

 

예를 들어, 물건 가격이 4040원이고, 5000원을 지불했을 때, 거스름돈으로 동전 개수를 최소한으로 거슬러 받는 문제가 있다. 

• 거스름돈은 960원
• 500원 1개, 100원 4개, 50원 1개, 10원 1개

1. 거스름돈의 동전 개수를 줄이기 위해 현재 가장 가치가 높은 동전을 우선 선택한다.
2. 1번 과정을 통해 선택된 동전들의 합이 거슬러 줄 금액을 초과하는지 검사하고, 
만약 초과한다면 가장 마지막에 선택한 동전을 삭제하고, 
1번으로 돌아가 한 단계 작은 동전을 선택한다. 
3. 선택된 동전들의 합이 거슬러 줄 금액과 일치하는지 검사하고, 
일치하지 않으면 1번 과정부터 다시 반복한다. 

 

참고자료

---

• 블로그