공부한 내용 기록하기 공부한 내용 기록하기

1. 거스름돈 문제란?거스름돈 문제(Coin Change Problem)는 최소한의 동전 개수로 특정 금액을 거슬러 주는 문제다. 일반적으로 그리디 알고리즘(Greedy Algorithm)을 활용하여 해결할 수 있으며, 일부 경우에는 동적 계획법(Dynamic Programming)이 필요할 수도 있다.1.1 문제 정의동전의 종류가 주어졌을 때, 최소 개수의 동전을 사용하여 특정 금액을 만들기일반적인 화폐 단위에서는 그리디 알고리즘이 최적해를 보장특정 동전 조합에서는 최적해가 보장되지 않을 수 있음1.2 거스름돈 문제의 특징탐욕적 선택 속성(Greedy Choice Property): 가장 큰 단위의 동전부터 선택최적 부분 구조(Optimal Substructure): 부분 문제의 최적해가 전체 문제의 ..