목록CS (17)

코딩은 마라톤

탐욕 알고리즘(Greedy Algorithm)

1. 탐욕 알고리즘 Greedy algorithm이라고 부름 최적의 해에 가까운 값을 구할 때 사용한다. 여러 경우 중 하나를 결정할 때마다, 매순간 "최적"이라고 생각되는 경우를 선택해서 최종적인 값을 구한다. 2. 탐욕 알고리즘 예 문제 1: 동전 문제 - 지불해야 하는 값이 4720원일 때, 1원, 50원, 100원, 500원 동전으로 동전의 수가 가장 적게 지불하는 방식 1. 가장 큰 동전부터 최대한 지불해야 하는 값을 채우는 방식 public class Main { public static void main(String[] args) { // 만약 동전 리스트가 내림차순으로 정렬되지 않을 경우 // 정렬을 해주어야 한다. sort int[] list = {500, 100, 50, 1}; Syst..
CS/알고리즘 2023. 10. 7. 22:13
이전 Prev 1 2 3 Next 다음