그리디 Greedy

📍그리디 알고리즘

: greedy란 '탐욕스러운'이라는 뜻으로,
현재 상황에서 가장 좋은 것만 고르는 방법을 의미한다.

매순간 가장 좋아보이는 것을 선택하면 현재의 선택이 나중에 미칠 영향을 고려하지 않는다.

장점 : 동적 계획법보다 구현하기 쉽고 시간 복잡도가 좋다.
단점 : 항상 최적의 해를 보장하지 못한다.

			시작
	3				  5
100	 101		  10     11

위와 같다면 그리디는 5 -> 11을 선택해 16이 나온다.
하지만 위에서 가장 큰 값은 3 -> 101을 선택해서 104이다.
즉, 항상 최적의 해를 보장하지는 못한다.

2. 그리디 알고리즘 수행 과정

1. 해 선택 : 현재 상태에서의 최적의 해답을 선택한다.
2. 적절성 검사 : 선택된 해가 문제의 제약 조건을 만족하는지 검사한다.
3. 해답 검사 : 원래의 문제가 해결되었는지 검사하고, 해결되지 않았다면 1번으로 돌아가 위의 과정을 반복한다.

문제에 "가장 작은 순대로", "가장 큰 순서대로" 라는 말이 있으면 그리디 알고리즘일 가능성이 높다.

대부분 문제 조건에 맞추어 정렬을 한 후 알고리즘 과정을 수행한다.

3. 알고리즘 적용 조건

1. 선택 조건 : 앞의 선택이 이후의 선택에 영향을 주지 않는 것이다.
2. 최적 부분 구조 조건 : 문제에 대한 최적의 해가 부분문제에 대해서도 역시 최적의 해이어야 한다.

이러한 조건이 성립하지 않는 경우에는 그리디 알고리즘은 최적의 해를 구하지 못한다.