그리디 알고리즘이 최적해를 구할 수 있는 조건
1. greedy choice property: 현재 선택이 이후의 선택에 영향을 주지 않아야 한다.
영향을 준다는 것은 현재 선택 이전에는 사용 가능했던 후보가 현재 선택 이후 사용 불가능해진 경우
ex) 10, 30, 40, 50의 조합으로 70을 만들기
50을 고르면 30, 40을 고를 수 없게됨.
2. optimal substructure: 매 순간 최적의 해가 문제 전체에 대한 최적의 해여야 함. 즉, 매 순간의 선택이 최적의 선택으로 가는 길이어야한다.
* 추가 공부 필요
두 조건의 차이: https://stackoverflow.com/questions/26439973/optimal-substructure-and-greedy-choice
Optimal substructure and Greedy choice
I was reading about the two properties of a greedy problem and I'm trying to understand the difference between the two below :- Optimal substructure property: an optimal global solution contains the
stackoverflow.com
조건이 참임을 증명하는 방법
알고리즘 :: 종만북 :: 10장 :: 그리디
Greedy 알고리즘은 현재 주어진 상황에서 가장 이득이 되는 최선의 경우를 선택하는 알고리즘을 의미한다.Greedy 알고리즘은 지금의 선택이 앞으로 남은 선택들에 대해 어떤 영향을 끼칠지 고려하
velog.io
1. 다른 방법으로 최적해를 구할 수 있음을 가정한다.
2. 최대 최소값을 바꾸거나 순서를 바꾸는 등의 다른 방법으로 해를 구한다.
3. 그리디 알고리즘을 쓰는 것이 손해가 없음을 증명한다.
4. 부분해의 최적해가 전체 답안의 최적해임을 증명한다. (?)
부분해를 구하는 과정이 최적해를 구하는 길임을 보장할 수 있어야 한다.
'Code' 카테고리의 다른 글
| [JS] Map, Set 자료형 심화 이해 (0) | 2022.08.24 |
|---|---|
| [JS] 배열을 객체로 바꾸는 방법 속도 비교 (forEach VS. reduce) (0) | 2022.07.27 |
| [JS] 소수점 데이터 출력하기 (feat. 야구 타율) (0) | 2022.03.22 |
| [JS] 숫자형으로의 변환 number, parseInt 차이에 대한 고찰 (0) | 2022.03.17 |
| [JS] sort, map은 화살표를 좋아해 (0) | 2022.03.17 |
