[Python] 그리디 알고리즘이란 무엇일까? /백준 11047 동전 0 파이썬 풀이
Greedy 알고리즘 말 그대로 탐욕적인, 현재 상황에서 지금 당장! 좋은 것만 고르는 방법 그리디 알고리즘은, 문제를 풀기 위한 최소한의 아이디어를 적절히 떠올려야 풀 수 있다! 그리디 알고리즘의 단점 최적의 해는 5 = > 7=> 9 총 21이 나오는 경로일 것이다 Q. 그리디 알고리즘을 사용하여 단순히 매 상황에서 가장 큰 값만 고른다면? 5 => 10 => 4 총 19가 나오는, 최적의 해를 구할 수 없는 상황이 나온다. 예시처럼 그리디 알고리즘은 최적의 해를 보장할 수 없을 때가 많다.... 하지만, 코테에서 대부분의 그리디 문제는 그리디 알고리즘으로 얻은 해가 최적의 해가 되는 상황에서 이를 추론할 수 있도록 출제된다고 한다! 가장 대표적인 문제는 거스름돈 문제이다 백준-11047번 문제 준규..
2023. 1. 22.