[알고리즘] Greedy Algorithm이란? (최적, 예제, 정의, 개념)

 

그리디 알고리즘

- 결정해야 할 때, 그 순간에 가장 좋다고 생각하는 것을 선택하면서 답을 찾아가는 알고리즘

- 그 때는 최적일지 몰라도, 최종적으로 답이 최적이 아닐 수도 있다.

​

??? : 최적이라면서 왜 답이 아니죠?

​

오해하기 쉬운 알고리즘입니다. '그리디 알고리즘은 쉽다!' 라는 인식이 강합니다. 하지만 그렇지 않습니다.

사실상 ​저 선택이 왜 최적인지를 증명해야 하기 때문에 어렵습니다.

항상 최적이 아닐 수도 있으니까요...

---

어렵나요? 한 번 예를들어 보겠습니다.

​

1) 여러분은 까까를 사먹기 위해 편의점에 왔습니다.

지금 딱 만원이 있는데, 2430원이라는 가격에 까까 하나를 샀습니다.

그리고 만원 지폐 한 장을 내밀었습니다. 거슬러 받아야 할 돈은? 7570원 입니다.

이 때, 거스름돈의 지폐, 동전의 갯수가 최소가 되야한다면 어떻게 돌려 받아야 할까요?

​

7570원 이므로 7570 - 5000 = 2570 ! ( 총 1개 )

2570원 이므로 2570 - 2 * 1000 = 570 ! ( 총 3개 )

570원 이므로 570 - 500 = 70 ! ( 총 4개 )

70원 이므로 70 - 50 = 20 ! ( 총 5개 )

20원 이므로 20 - 2 * 10 = 0 ! ( 총 7개 )

​

감이 오시나요? 저렇게 돌려줘야 욕 안 먹습니다.

저렇게 항상 최적의 경우를 선택하는 방법이 바로 '그리디 알고리즘' 입니다.

너무 쉽나요? 그럼 하나 예를 더 들어봅시다.

---

2) 이 세상의 동전은 저희가 알고있는 것과 다르게

1원, 4원, 5원 밖에 존재하지 않습니다.

​

그러면 위에 경우와 같은 방법으로 거스름돈 12원을 받아 봅시다.

​

12원 이므로 12 - 2 * 5 = 2 ! ( 총 2개 )

2원 이므로 2 - 2 * 1 = 0 ! ( 총 4개 )

​

와! 깔끔하게 답이 나왔네요! (역시 그리디 알고리즘! 블로그를 뒤집어 놓으셨다!)

이라고 생각하면 안됩니다. 이건 답이 아니기 때문이죠...

​

12원을 12 - 4 * 3 = 0 하면 총 3개라는 더 좋은 결과가 나와버리기 때문입니다.

이처럼, 1) 예제는 최적이었지만, 2) 예제는 아니었습니다.

이렇게 특별한 조건에 맞는 체계에서만 성립하는 알고리즘이 바로 그리디 알고리즘입니다.

​

이해가 되셨나요? 다음 포스팅은 그리디 알고리즘을 활용하여 문제를 풀어보는 시간을 가져보겠습니다.

열심히 살겠습니다.