코딩테스트
-
Swift 코딩테스트 - 탐욕(Greedy) 알고리즘🧑💻/Algorithm 2021. 2. 17. 15:58
Greedy Algorithm 최적 해에 가까운 값을 구할 때 사용합니다. 매 순간마다 최적의 방법을 선택하여 값을 구하지만 결과적으로 최적 해라는 보장은 없습니다. 다음 그림을 탐욕 알고리즘으로 풀면 다음과 같이 13 + 11 = 24라는 값이 도출됩니다. 하지만 실제로는 7 + 100 = 107이 나올 수 있는 최대 값입니다. 이렇게 탐욕 알고리즘은 최적 해라는 보장이 없습니다. 최적 해를 구하는 동적 계획법을 사용하면 되지만 속도가 월등히 빠르다는 장점이 있습니다. 대표적으로 최소 동전 개수로 돈을 거슬러 주는 예가 있습니다. 거스름돈 : 1200원 동전 종류 : 500원, 400원, 100원 탐욕 알고리즘에 의하면 500원 2개, 100원 2개로 총 4개가 나옵니다. 하지만 실제로 최적의 개수는 ..