[알고리즘] 그리디 알고리즘

 

그리디 알고리즘(Greedy Algorithm)이란?

 

현재 상황에서 가장 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행하여 해답에 도달하는 알고리즘이다.

문제를 풀 때, 두가지 조건이 성립해야 그리디 알고리즘을 적용시킬 수 있다.

 

1. Greedy Choice Property

이 선택이 항상 전체 문제의 최적해를 반드시 도출할 수 있어야 한다.

그리디 알고리즘을 사용해서 푸는 문제가 나왔을 때, 이 조건이 만족되는가?를 생각해 충족되면 그리디 알고리즘을 사용하는 것이다.

 

2. Optimal Substructure

 문제에 대한 최종 해결 방법이 부분 문제에 대해서도 최적해로 구성될 수 있는 경우를 말한다.

즉, 전체 문제를 작은 부분 문제로 나누어 각각의 부분 문제에서 최적의 해를 구한 후 이를 조합하여 전체 문제의 최적해를 구하는 것을 의미한다. 

 

 

<그리디 알고리즘 단계>

 

1. 문제의 최적해 구조를 결정한다.

2. 문제의 구조에 맞게 선택 절차를 정의한다. (Selection Procedure) 선택 절차

3. 선택 절차에 따라 선택을 수행한다.

4. 선택된 해가 문제의 조건을 만족하는지 검사한다. (Feasibility Check) 적절성 검사

5. 조건을 만족하지 않으면 해당 해를 제외한다.

6. 모든 선택이 완료되면 해답을 검사한다. (Solution Check) 해답 검사

7. 조건을 만족하지 않으면 해답으로 인정되지 않는다.

 

선택 절차 -> 현재 상태에서 최적인 선택을 한다.

적절성 검사 -> 선택한 항목이 문제의 조건을 만족시키는지 확인한다. 조건을 만족시키지 않으면 해당 항목은 삭제된다.

해답 검사 -> 모든 선택이 완료되면 최종 선택이 문제의 조건을 만족시키는지 확인한다. 조건을 만족시키면 해답으로 인정된다. 

그리디 알고리즘 문제에서는 문제 풀이를 위한 최소한의 아이디어를 떠올리고, 이것이 정당한지 검토할 수 있어야 한다.

 

 

 

 

---

 

 

 

예시

1) 거스름 돈 문제

 

김코딩은 오늘도 편의점에서 열심히 아르바이트하고 있습니다. 손님으로 온 박해커는 과자와 음료를 하나씩 집어 들었고, 물건 가격은 총 4,040원이 나왔습니다. 박해커는 계산을 하기 위해 5,000원을 내밀며, 거스름돈은 동전의 개수를 최소한으로 하여 거슬러 달라고 하였습니다.

 

1. 선택절차

- 거스름돈의 동전 개수를 줄이기 위해 가장 큰 단위의 동전을 우선 선택한다.

2. 적절성 검사

- 1번 과정을 통해 선택된 동전들의 합이 거슬러 줄 금액을 초과하는지 검사한다.

초과하면 가장 마지막에 선택한 동전을 삭제하고, 1번으로 돌아가 한 단계 작은 동전을 선택한다.

3. 해답 검사

- 선택된 동전들의 합이 거슬러 줄 금액과 일치하는지 검사한다. 액수가 부족하면 1번 과정부터 다시 반복한다.

 

 

public int GreedyAlgorithm(int k) {
    int[] arr = new int[]{500, 100, 50, 10, 5, 1};
    int answer = 0;
    for (int n : arr) {
      if (k > 0) {
        int temp = k / n;
        answer += temp;
        k -= (n * temp);
      }else break;
    }
    return answer;
}