Greedy Algorithm - 욕심쟁이 방법의 원리
해를 구하는 일련의 선택 단계마다 전후 단계의 선택과는 무관하게 해당 단계에서 가장 최선이라고 여겨지는 국부적인 최적해를 선탬함으로써 전체적인 최적해를 구함
- 최적화 문제 해결에 주로 사용
- 최적성의 원리가 적용된 방법
동적 프로그래밍 방법과 차이점
소문제의 여러 최적해로부터 다음 크기의 문제에 대한 최적해가 결정 -> 항상 전체적인 최적해를 구함
- 욕심쟁이 방법은 전체적인 최적해를 구하지 못할 수 있다.
항상 구할 수 없는데 왜 사용을 하나?
동전 거스름돈 문제
- 개념과 원리
동전의 개수를 최소로 하여 돌려주는 방법
동전의 액면가가 임의로 주어지는 일반적인 경우 욕심쟁이 방법으로 해결 불가 [동적프로그래밍 방법은 해결 가능]
배낭 문제
최대 용량 M인 하나의 배낭과 n개의 물체
- 각 물체 i에는 물체의 무게 wi와 해당 물체를 배낭에 넣었을 때 얻을 수 있는 이익 pi
배낭의 용량을 초과하지 않고, 물체의 이익의 합이 최대가 되도록 물체를 넣는 방법 _ 가정 물체를 쪼개서 넣을 수 있다 _ 
무게는 적으면서도 이익이 가장 큰 물체부터 골라서 ‘욕심을 내어’최대한 넣는다.
단위 무게당 이익을 계산 후 가장 큰 물체부터 최대한 배낭에 넣는 과정을 반복
빅오 - O(n)(정렬 고려하지 않을 경우)
특징
- 물체를 쪼갤 수 없는 형태의 배낭 문제 (0/1 배낭 문제)
- 욕심쟁이 방법 적용 불가
- O(2^n) 시간 복잡도
최소 신장 트리
가중 그래프가 트리로 가는 조건
- 무방향
- 모든 정점을 포함
사이클이 없어야 함
- 정점 n 연결선(간선) n-1개
최소 (비용) 신장 트리
- 신장 트리 중에서 간선의 가중치의 합이 가장 작은 트리
- 대표적 알고리즘 : 크루스칼, 프림
크루스칼
1 간선이 하나도 없는 상태에서 시작 2 가중치가 가장 작은 간선부터 하나씩 선택 3 사이클을 만들지 않으면 추가 4 사이클을 만들면 버림
사이클 확인은 어떻게? 각 정점 초기화 가중치가 증가하는 순으로 모든 간선을 정렬
