🔵 탐욕적 기법, Greedy Algorithm 이란?
욕심쟁이 기법, 그리디 라고도 하는 이 기법은
눈 앞의 가장 큰 이익만을 좇는 방법이다.
성질이 동일하게 보존되므로 아까 했던 전략을 계속 취해도 정답을 얻을 수 있다.
문제를 딱 보고 그리디인지 알기가 쉽지 않다.
✔ 그리디의 가장 흔한 예시
10원, 50원, 100원, 500원을 최소한으로 사용하여 금액 표현하기!
👉 풀이 : 가장 큰 금액의 동전을 사용할 수 있는 최대개수를 무조건 다 사용하는 것!
왜 이게 성립할까??
반드시 큰 쪽은 작은 쪽 액수의 배수이기 때문
작은 동전들이 많이 있을 때, 이를 모아 큰 동전을 만들 수 있다면 무조건 바꿔주는 게 이득!
-> 저 배수라는 성질이 성립하지 않으면 이 성질도 깨진다.
-> 그리디도 더 이상 사용 불가!
만약 60, 50, 10원 동전을 사용한다고 해보면, 60은 50의 배수가 아니다.
220원을 표현하려고 할 때, 60원짜리부터 무작정 최대로 사용하게되면
60 3, 50 0, 10 4 ==> 총 7개
하지만,
60 0, 50 4, 10 2 = 20 ==> 총 6개 얘가 더 좋네?
60원을 최대한 많이 사용한다해서 좋은 게 아니죠?? -> 그리디 기법 불가!!
문제의 성질이 동일하게 보존되고, 같은 전략을 반복적으로 취할 수 있는 것이 그리디 알고리즘의 특징. 즉, 일반화가 가능하다는 소리인 듯
✔ 그리디 알고리즘의 실패 경우
현재 A 지점에 서 있다고 해보자. A에서 최대 높이에 다다르려 한다.
m은 loacl maximum이다. 그 근처 지역에 한해서는 가장 이득이지만, 전체 중에서는 최적해가 아닐 수 있다.
M은 global maximum이다. 전체에서 최적해를 의미한다. global maximum 또한 local maximum이다. 그러나 전체상황을 모르는 A의 입장에서는 어딘가 도착해도 그게 글로벌인지, 로컬 최적해인지 판단하기 어렵다.
이런 상황에서 그리디를 적용한다면?
A의 위치에서 m으로 가는길은 경사가 45도보다 커보이고, M으로 가는 길은 당장 보기엔 기울기가 0에 가깝기 때문에m으로 가버린다.
-> 최적해 찾기 실패
그러면 왜 중요해?
✔ 그리디 알고리즘이 중요한 이유
그리디는 다른 복잡하지만 최적해를 뽑아내는 것들에 비해 비용이 적은 경우가 많다.
풀이가 대부분 가장 큰~, 가장 긴~, 가장 빠른~부터 뭔가 해나가라는 것이다보니 정렬기술은 필수다.
💙 스터디 예제
◼ ch04
🟠II 5585 거스름돈
🟠I 2839 설탕 배달
🟠I 2828 사과 담기 게임
🔘V 1789 수들의 합
🔘V 4796 캠핑
🔘II 11047 동전 0
🔘II 1541 잃어버린 괄호
◼ ch05
🔘III 1449 수리공 항승
🔘II 2138 전구와 스위치
🔘III ATM
🔘II 회의실 배정
🟡III 과제
🟡I 멀티탭 스케줄링
◾ 출처
