[algorithm] 그리디(greedy, 탐욕) 알고리즘

🤔 그리디 알고리즘

---

• 탐욕, 욕심쟁이 알고리즘이라고도 불림.
• 미래를 생각하지 않고 각 단계에서 가장 최선의 선택을 하는 기법
• 선택의 순간마다 당장 눈앞에 보이는 최적의 상황만을 쫒아 최종적인 해답에 도달하는 방법
• 일반적인 상황에서 그리디 알고리즘은 최적의 해를 보장할 수 없을 때가 많다
• 현재의 최적 해 != 전체의 최적 해

 

 

 🧦 사용해야 하는 조건

---

서울에서 대전을 거쳐 부산까지 가는 최적의 경로를 선택해라.

 

 

1. 현재의 선택이 미래의 선택에 영향을 주지 않는다.

탐욕스런 선택 조건

 

2. 부분의 최적 해가 모이면 전체의 최적 해가 된다.

최적 부분 구조 조건

 

그리디 문제를 푸는 방법의 핵심은 정렬이다.

어떻게 정렬해야 이 두가지 조건을 만족할 수 있을지 생각해야한다.

 

 

🤖 그리디는 왜 사용할까?

---

빠른 속도

 : 항상 최적의 선택을 하기 때문에 dp보다도 빠른 속도를 자랑함.

dp의 경우 항상 최적 해를 보장하기 위해 모든 경우의 수를 고려한다.

 

현실 세계에서는 100% 최적 해를 보장하지 않아도 되는 일에 성능을 개선하고자 사용한다.

ex. 네비 길 안내

 

대표적인 문제 

: 거스름 돈

- 최적의 해를 빠르게 구하기 위해서는 가장 큰 화폐 단위부터 돈을 거슬러 주면 된다.

- N원을 거슬러 줘야 할 때, 가장 먼저 500원으로 거슬러 줄 수 있을 만큼 거슬러 준다.

  -> 이후에 100원, 50원, 10원 동전을 차례대로 거슬러 줄 수 있을 만큼 거슬러 준다.

- N = 1,260일 때의 예시를 확인해보자.

 

 

 

- 가장 큰 화폐 단위부터 돈을 거슬러 주는 것이 최적의 해를 보장하는 이유는 무엇일까?

   -> 가지고 있는 동전 중에서 큰 단위가 항상 작은 단위의 배수이므로 작은 단위의 동전들을 종합해 다른 해가 나올 수 없기 때문이다. 

- 만약 800원을 거슬러 주어야 하는데 화폐 단위가 500원, 400원, 100원이라면 어떻게 될까?

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

 

 

자바 문제 풀이

public static void main(String[] args) {
    int n = 1260;
    int cnt = 0;
    int[] coinTypes = {500, 100, 50, 10};

    for (int i = 0; i < 4; i++){
        cnt += n / coinTypes[i];
        n %= coinTypes[i];
    }

    System.out.println(cnt); // 6
}

 

 

더 많은 그리디 문제 확인하기

 

 

🐨 reference

https://www.youtube.com/watch?v=_IZuE7NIeW4 

https://www.youtube.com/watch?v=2zjoKjt97vQ 

https://hanamon.kr/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%ED%83%90%EC%9A%95%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-greedy-algorithm/