최적 해1 [알고리즘] Greedy Algorithm, 그리디(탐욕) 알고리즘 1. 그리디(탐욕) 알고리즘의 정의 미래를 고려하지 않고 오직 현재 시점에서 가장 좋은 선택예) 잔돈 반환 프로그램 - 사용할 수 있는 가장 큰 동전부터 최대 사용 가능한 양만큼 쓰고 밑으로 차근차근 내려가며 동전의 개수를 최소로 사용하게 하는 방법, 6800원이 들어왔다면 5000원 한 장을 낼 때 뒤에 어떤 돈들이 쓰일 지 고려하지 않음 2. 그리디 알고리즘의 특징 이 알고리즘은 항상 최적을 보장하지 못함, 현재의 최적 해가 전체의 최적 해를 보장하지 않음예) 마시멜로를 참으면 10분 뒤에 두 개를 먹을 수 있지만, 그리디 알고리즘에 따르면 하나를 먹는게 최선임 따라서 항상 최적 해를 찾아야 하기 때문에 최적 해가 보장되는 조건에서만 그리디 알고리즘을 사용해야함 조건1 - 현재의 선택이 미래에 영향을.. 2024. 6. 4. 이전 1 다음