[Python 공부] 탐욕의 알고리즘: Greedy Algorithm

안녕하심까! 오랜만에 공부 글로 돌아왔네요.
 
요즘 medium 레벨의 릿코드 문제들을 풀면서 Greedy Algorithm을 사용하는 문제들이 많이 나오기 시작했습니다. 하지만 저는 대학교에서 이것을 들어본 적도 풀어본 적도 없었기 때문에 결국에 막혀서 NeetCode의 영상들을 많이 참고하면서 풀고 있습니다.
 
연속 3문제를 유튜브로 찾아보니까 자존심이 상하더군요 하하! 그래서 아싸리 인터넷으로 찾아서 공부해보기로 했습니다.
 
 

 

그리디 알고리즘?)

그리디 알고리즘은 제가 일반적으로 생각하는 알고리즘들과 다릅니다.
 
제가 알고있는 Binary Search나 DFS (Depth-First-Search) 알고리즘들은 정해져 있는 틀, 풀이 방식, 그리고 사용되는 문제 형태들이 정해져 있는 느낌입니다.
 
하지만 그리디는 다릅니다. 그리디도 물론 사용되는 형태나 푸는 방식이 정해져 있지만 다른 알고리즘처럼 명확하게 명시되어 있지는 않은 것 같습니다. 알고리즘보다는 개념이라는 말이 더 잘 어울리죠.

 

그래서 이게 뭔데?)

그리디 알고리즘은 주로 주어진 정답들 중 가장 효율적인 정답을 찾을 때 사용됩니다.
가장 효율적이다는 뜻은 곧 최소/최대를 구할 때 사용된다는 뜻이겠죠?
 
그럼 이 효율적인 정답을 어떻게 구하느냐?
닉값을 하면 됩니다.
 
뒤의 발생할 선택들은 생각하지 않은 채, 현재 가능한 가장 탐욕스러운 선택을 고르면서 원하는 정답이 나올 때까지 경우를 줄이는 것입니다. 이 탐욕스러운 선택이 이해하셔야 되는 포인트입니다.

 

예시)

예를 들어 [100원, 10원, 1원, 0.1원] 동전들이 무제한으로 주어질 때, 142원이라는 잔돈을 최소 개수의 동전으로 줘야할 때 어떻게 해야 될까요?
 
여기서 할 수 있는 가장 탐욕스러운 선택은 무엇일까요?
 
일단 뒤에 값은 내 알빠가 아니고 가장 값어치가 큰 동전으로 빨리빨리 채워 놓고 싶엉. 
- 100원 동전을 최대로 줄 수 있는 개수는 1개
 
물론 마음 같아선 욕심이 많은 나는 2개로 채워 놓고 싶지만 그렇게 할 수 없으므로 아쉬움을 뒤로한 채 두 번째로 큰 값을 찾아봅시다.
- 10원 동전을 최대로 줄 수 있는 개수는 4개
 
남은 2원도 마찬가지로 탐욕스럽게 세 번째로 큰 값을 이용해 채워줍니다.
- 1원 동전을 최대로 줄 수 있는 개수는 2개
 
이렇게 잔돈을 최소 개수의 동전으로 줄 수 있는 개수는 7개입니다. 위와 같은 절차들을 적어보죠.

 

그리디 알고리즘 절차)

1) 초기 값이 0인 res 변수를 먼저 정의해 줍니다.
2) 주어진 선택들 중 가장 탐욕스러운 선택을 해줍니다. 그리고 이 선택이 최종적인 결과에 적용된다면 res 변수에 저장해 줍니다.

3) 가장 탐욕스러운 선택에서 덜 탐욕스러운 선택들을 완료했다면 res를 리턴해줍니다.

 

현실은...)

하지만 전 현재까지 이런 방식을 그.대.로 적용시킬 수 없는 릿코드 문제들 밖에 보지 않았고 그래서 굉장히 고전했습니다.
 
그러므로 중요한 포인트들만 짚자면,
 
1) 가장 탐욕스러운 선택을 해라
2) 그게 성공했다면 바로 다음 선택지를 봐라
3) 미래에 어떤 값이 나올지 몰라도 일단은 탐욕적으로 끝까지 해봐라
3) 하지만 너무 맹목적으로 골라서는 안된다
 

 

솔직히 정체되어 있는 것 같아 무섭습니다. 못된 AI가 내 미래 직장을 빼앗을지, 하고 있는 공부가 올바른 방향을 향하는지, 1년 반 후의 내가 후회하진 않을지 무섭습니다.
 
그래도 어쩌겠슴까 주어진 환경에서 사람이 최선을 다해야지 않겠습니까? 미래의 나는 릿코드도 눈 감고 풀고 블로그도 유명해지고 주짓수도 잘하고 그냥 더 머싰는 사람이 되어있으면 좋겠습니다 (-.-) b 
 
참고자료: GeeksForGeeks