알고리즘/Greedy1 GREEDY 알고리즘 이란? 영어로 적어놓으니까 뭔가 생소하고 어려울 것 같지만, 실제 개념은 그렇게 복잡하지 않다. 현재에서 최선의 선택을 따라가는 것이다. 로컬 미니멈 초이스를 통해 글로벌 미니멈에 도달한다는 생각인데, 즉 최종 결과가 최선일 수도, 아닐 수도 있다. 예로 동전 교환 문제를 들어보자. 17원을 10 5 1원 주화로 바꾸는 것을 생각해보자. 10원 1개, 5원 1개 1원 2개. 당장 작은수 코인 교환을 보장하는 큰 코인 부터 바꿨는데, 최선의 결과가 됐다. 17원을 7 6 5 4 1원 주화로 바꾸는 것을 생각해보자 같은 접근법으로 7원 2개 1원 3개라는 결과가 나온다. 하지만 최선의 결과는 따로 있다. 6원 2개 5원 1개. 즉 같은 접근 법임에도 최선이 아닐 수 있다. 탐욕알고리즘 풀이 이전에는 , 반례가 없는.. 2022. 11. 3. 이전 1 다음