greedy algorithm

그리디 알고리즘(Greedy Algorithm) & 동적 계획법(Dynamic Programming)

그리디 알고리즘(Greedy Algorithm) 다음 단계를 생각하지 않고, 현재 단계에서 가장 최선을 선택하는 기법이다 조건 탐욕 선택 속성(Greedy Choice Property) 이전의 선택이 이후에 영향을 주지 않음 최적 부분 구조(Optimal Substructure) 부분 문제의 최적결과가 전체에도 그대로 적용될 수 있어야 한다 특징 전체 상황에서의 최적의 결과를 보장하지 못한다. 속도가 매우 빠르다 사용 예시 : 거스름돈, 활동 선택(Action Selection) 문제 등 동적 계획법(Dynamic Programming) 하나의 큰 문제를 여러 개의 작은 문제로 나누어서 그 결과를 저장하여 다시 큰 문제를 해결할 때 사용 조건 겹치는 부분 문제(Overlapping Subproblems)..