기록
Greedy Algorithm (탐욕 알고리즘) 본문
그리디 알고리즘이란?
문제를 해결하는 과정에서 매번 최적이라고 생각하는 방법으로 결정하는 태도라고 할 수 있을 것같다.
특별한 공식같은 건 없는 거같다. 그래서 이름이 Greedy인 것이 아닐까?
Greedy 알고리즘은
1. Greedy choice property
2. Optimal Substructure
위의 두 조건이 성립될 때 적용 가능하다.
<탐욕스러운 선택 조건 (Greedy choice property)>
: 이 조건을 만족함은 앞의 선택이 이후의 선택에 영향을 주지 않는다는 것이다.
<최적 부분 구조 조건(Optimal Substructure)>
: 전체 문제의 최적해가 부분 문제의 최적해들로써 구성된다는 것이다.
'공부 > Algorithm' 카테고리의 다른 글
BinaryTree (0) | 2020.09.30 |
---|---|
Searching (0) | 2020.09.30 |
[알고리즘] 동적 계획법 (Dynamic Programming) (0) | 2020.08.11 |
[알고리즘] 선택정렬, 버블정렬, 삽입정렬 - O(N^2) (0) | 2020.08.11 |
[알고리즘] 깊이 우선 탐색(Depth-First Search)와 너비 우선 탐색(Breadth-First Search) (0) | 2020.07.22 |
Comments