[방학의 PS] 그리디 알고리즘 - BOJ_1931, BOJ_1541
그리디 알고리즘의 정의 그리디 알고리즘이란 어떤 문제를 해결해야 할 때, 그 문제를 반복되는 여러 단계로 나눈 뒤에, 각 단계의 문제에 대한 최적해를 구하는 것을 반복하는 알고리즘입니다. 그리디 알고리즘의 예 간단한 예를 통해 말씀드리면, 거스름돈 구하기 문제를 셍각해 볼 수 있습니다. 만일 여러분이 편의점 알바생이고, 손님에게 X원의 현금을 거슬러주어야 할 때, 누구나 자연스럽게 가장 큰 단위의 화폐부터 거슬러주게 됩니다. 예를 들어 6670원을 거슬러준다면, 5000원짜리 한 장, 1000원 짜리 한 장, 500원 한 개, 100원 한 개, 50원 한 개, 10원 2개 순서로 거슬러 드릴 것입니다. 즉 X원을 거슬러 드리는 문제를 5000원을 거슬러 드리는 문제, 1000원을 거슬러 드리는 문제.....
2022. 7. 2. 04:21
