안녕하세요, 계략입니다.
오랜 시간이 흘렀습니다.
대문부터 시작해서 좀 많이 개편했습니다.
전문성을 조금 낮추더라도 더 쉽게 설명하는게 좋을 것 같다고 생각해서, 좀 편하게 설명하겠습니다.
그러면, 잘 부탁드리겠습니다!
이번 시간에는?
욕심쟁이 (Greedy, 그리디)
정의
이름에서 느낌이 팍!팍! 올겁니다.
다른 거 신경 안씁니다.
현재 상태에서 할 수 있는 최선의 선택만을 합니다.
10분 더 공부하면 아내의 얼굴이 바뀐다는 말이 있습니다.
이 말을 듣고 논다와 공부한다 중에 고르면, 욕심쟁이 알고리즘으로 선택을 하면 결과는
논다
무조건 그렇습니다. 공부따위 하지 않습니다. 머뭇거리지도 않습니다.
돈? 권력? 그런 거 없습니다. 지금만 잘 살면 된다는 방식입니다.
장점
만들기가 쉽습니다.
특별히 다른 걸 고려 할 필요가 없어요!
사람으로 따지면 그때 그때 FEEL대로 하는겁니다.
구상하기도 쉽습니다.
미래까지 고려할 필요가 없어요. 현재 상태만 보면 됩니다.
시간이 오래 걸리지 않습니다.
현재 상태만 보기 때문에, 어지간해선 작동 시간이 짧습니다.
단점
멍청합니다.
뭔가를 할 때는 일반적으로 멀리 내다보는 시선이 필요합니다.
리플에 물려도, 다른 알트코인에 물려도 존버정신으로 버티면 좋을 때가 있습니다.
그러나 얘는 그런 거 없어요.
오르면 좋다꾸나 하고 내리면 아이고.. 합니다.
당장에 이득을 챙기다가 나중의 이득을 놓치게 되는 경우가 생깁니다.
내일 100원을 받을래, 7일 뒤에 10000원을 받을래?
라는 질문에 욕심쟁이 알고리즘에 최적화를 안 해 놓은 상태라면
100원만 받고 나가리하게 되는 수가 있습니다.
사용 예시
조금 흔한 문제로, 거스름돈 문제가 있습니다.
1만원, 5천원, 1천원, 500원, 100원짜리 화폐만 사용합니다. X원의 거스름돈을 줘야 할때, 가장 적은 수의 화폐를 사용하려고 합니다. 어떻게 해야 할까요?
요약하면 덜 귀찮게 거스름돈 주기가 되겠죠.
어떻게 하면 될까요?
간단합니다. 줄 수 있는 가장 큰 돈부터 주면 됩니다.
지금 줄 수 있는 최고액이 얼마죠? 1만원이네요.
그러면 거슬러 주면 6700원을 더 줘야 하네요.
그 중에서 줄 수 있는 최고액은요? 5천원이네요.
거슬러 주면 1700원입니다.
그러면 1천원을 주고 700원이 남고, 500원을 주고 200원이 남고, 100원을 주고 100원이 남고, 100원을 주겠죠.
이 방법으로 거스름돈을 주면 가장 적은 화폐 수로 거슬러주게 됩니다.
잘 생각해보시면 일상생활에서도 이렇게 생각합니다.
28500원을 거슬러준다 하면 만원 1장, 오천원 1장, 천원 3장, 오백원 1개를 주면 된다고 생각하는게 이런 과정을 통해서 생각하는겁니다.
다만 함정이 있습니다.
단점에서 언급했듯이, 욕심쟁이 알고리즘은 멍청한 친구에요.
대부분의 나라에서는 이게 성립하지만, 아닌 경우도 있어요.
1원, 4원, 5원의 화폐만 존재한다고 합시다. 8원을 거슬러줍시다.
거슬러줄 수 있는 최고액인 5원을 거슬러줍시다.
그러면 3원이 남네요? 1원짜리로 3개 줘야 합니다.
이 경우 4개를 사용합니다.
거슬러줄 수 있는 최고액이 아닌 4원짜리 2개를 준다면?
2개로도 해결됩니다.
요약
- 욕심쟁이 알고리즘은 현재 상태에서 최선의 행동 만을 하는 알고리즘이다.
- 만들거나 생각하기가 쉽다는 장점이 있다.
- 오류가 생길 가능성이 높다.
여담
만들거나 생각하기가 쉽다고 했지만,
실은 오류가 없다는 걸 검증하기 위해서 시간을 좀 투자해야 합니다.
게다가 제대로 사용하려면 상당한 최적화가 필요하긴 합니다.
의외로 머리싸매야 하는 알고리즘입니다.
분량이 짜네요.
예시를 한 개 더 생각해보려고 했지만, 더 이상 들어가면 너무 복잡해집니다.
언젠가 크루스칼 알고리즘을 들고오면서 그리디를 언급하는 날이 오겠죠...?
주소 정할 때 3이 아니라 2로 해버렸네요. 망했습니다. ㅠㅠ