그리디 : 어떤한 것을 기준을 정렬을 해서 시작
1.쪼갤 수 있는(fractional) 배낭 문제에서 그리디는 100프로 최적값을 찾아 줌.
2. canonical Coin System에서 그리디는 100프로 최적값을 찾아 줌
3. Interval Scheduling 알고리즘에서는 그리디가 100프로 최적값을 찾아 줌.
사용하기 적합할 때
1. DP 처럼 동적으로 데이터가 수시로 바뀔 때!
2. DP는 무조건 중복된 하위 문제가 존재하기에 빠르게 최적값을 구할 수가 있다.
하위 문제가 존재하나 중복되지 않은 경우에는 그리디로 빠르게 구해 볼 수도 있다.(최적값은 보장 못함)
==================================================================================
그리디가 최적값을 보장하는 경우는 문제가 Matroid 구조일 때이다.
그러나 이 Matroid를 증명하는 것이 매우 어려우므로, 그리디는 알고리즘 중에서도 매우 어려운 알고리즘으로 분류가 된
다.
고로, 위에서 언급한 최적값이 보장되는 특정 문제가 아니면 함부로 그리디를 사용하는 것이 더 좋을 것 같다.
그러나 대부분의 문제에서는 예시를 보여 준다.
그 예시에서 local optimal만을 고려하여 최종적으로 global optimal 값을 구하는 것 같을 때에는 그리디를 고려해 볼 수가
있다.(아래의 문제들을 참조)
https://www.acmicpc.net/problem/11399
11399번: ATM
첫째 줄에 사람의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어진다. (1 ≤ Pi ≤ 1,000)
www.acmicpc.net
https://www.acmicpc.net/problem/13305
13305번: 주유소
표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 도시의 개수를 나타내는 정수 N(2 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 인접한 두 도시를 연결하는 도로의 길이가 제일 왼쪽 도로부터 N-1
www.acmicpc.net
'알고리즘(アルゴリズム） > 자주 까먹는 알고리즘(よく忘れるアルゴリズム）' 카테고리의 다른 글
| 이진수를 이용하여 O(log n)으로 거듭 제곱 빠르게 계산하기 (2) | 2023.01.30 |
|---|---|
| 조합론(Combination) == 이항 계수(binomial Coefficient) (0) | 2023.01.29 |
| Quad Tree - 2D 공간을 트리로 표현 (0) | 2023.01.26 |
| Stack과 Queue에 대한 고찰!!! (0) | 2023.01.26 |
| C++ - 2개 이상의 Delimiter를 사용한 Parsing Template (0) | 2023.01.24 |