그리디(greddy) 알고리즘이란 말 그대로 탐욕 알고리즘입니다.
미래를 고려하지 않고 오직 현재 시점에서 가장 좋은 선택을 하는
탐욕적인 알고리즘이기 때문입니다.
코딩 테스트에서 많이 출시되는
그리디 알고리즘은 단순하지만 강력한 문제 해결 방법입니다. 😀
하지만, 당연히도 그리디 알고리즘은 항상 '최적의 해'를 보장하지 못합니다.
현재의 최적 해가 전체의 최적 해가 되리라는 보장이 없기 때문입니다.
따라서 다음과 같은 조건을 생각해서 문제 풀이를 위한 아이디어를 떠올리고
정당한지 검토할 수 있어야 제대로 된 해답을 도출할 수 있습니다. 👍
📝 그리디 알고리즘의 조건
⦁ 조건 1
✔ 현재의 선택이 미래에 영향을 주지 않는다.
서울에서 대전까지 가는 거리를 고려했을 때, 대전에서 부산까지의 거리에 영향을 미치지 않습니다.
즉, 현재의 선택이 미래 선택에 영향을 주지 않는다라는 조건이 성립된 것입니다.
어려운 말로 탐욕스러운 선택 조건(Greedy Choice Property)이라고 합니다.
⦁ 조건 2
✔ 부분의 최적해가 모이면 전체의 최적 해가 된다.
큰 문제를 여러 개의 작은 문제로 나눌 수 있고, 작은 문제들에 대한 최적의 해가 더해진 것이
곧 전체 문제에 최적해가 되는 구조입니다.
어려운 말로 최적 부분 구조 조건(Optimal Substructure)이라고 합니다.
어려운 말은 참고만 해두시면 됩니다. 😀
📝 그리디 알고리즘 전략
⦁ 그리디를 사용해서 어떻게 문제를 해결할 수 있을까?
✔ 핵심은 정렬입니다.
어떻게 정렬해야 미래의 조건과 선택을 고려하지 않아도 최적 해를 구할 수 있는지 답을 찾아야 합니다.
따라서 정렬 라이브러리의 사용방법을 꼭 숙지하고 있어야 합니다! 😎
📝 그리디 알고리즘은 왜 사용할까?
⦁ 속도
그리디 알고리즘은 문제를 단순화하여 풀 수 있는 경우가 많아서 구현하기가 쉽습니다.
또한, 다이나믹 프로그래밍의 사촌 동생 같은 존재로 DP보다 더 실행속도가 빠르다는 장점이 있습니다.
⦁ 근사치
그리디 알고리즘은 적당한 해답을 빠른 시간에 얻을 수 있습니다.
따라서 해답이 근사치로도 괜찮을 때 잘 사용될 수 있습니다.
코딩 테스트의 첫걸음인 그리디 알고리즘을 공부해 봤습니다.
코테는 참 막막하고 어렵네요😥
같이 화이팅!
참고 문헌 :
이것이 취업을 위한 코딩 테스트다 - 나동빈
https://www.youtube.com/watch?v=_IZuE7NIeW4