그리디 알고리즘/탐욕 알고리즘/Greedy Algorithm
- 매 선택마다 바로 눈앞에 보이는 최적의 상황만을 쫓아 최적해를 도출하는 알고리즘
- 최적해를 항상 보장하는 것은 아님!
- 그리디 알고리즘을 만족하려면 두가지 조건을 성립해야한다.
1. 탐욕스러운 선택 조건
→ 이 선택으로 인해 전체 문제의 최적해를 반드시 도출할 수 있어야 함, 즉 앞의 선택이 이후의 선택에 영향을 주지 않는다.
2, 최적 부분 구조 조건
→ 문제에 대한 최종 해결 방법이 부분 문제에서도 최적의 해결방법이다, 즉 전체 문제가 여러 갈래로 나뉘고, 이 갈래 마다도 최적해가 도출되어야 한다는 뜻.
이 두가지 조건이 모두 성립하지 않는 경우에는 그리디 알고리즘으로 최적해를 도출할 수 없음.
매트로이드 구조 : 그리디 알고리즘이 최적해를 가려낼 수 있는 지 판별할 수 있는 수학적 공간
- 단 그리디 알고리즘을 적용할 수 있는 모든 경우를 판별하는 것은 아님
- 즉 매트로이드 구조일 경우에 그리디 알고리즘을 사용하면 최적해를 도출할 수 있지만, 반대로 그리디 알고리즘으로 풀리는 문제가 모두 매트로이드 구조는 아니라는 뜻이다.
매트로이드 구조 예시 : 백준 11047번 동전 0
11047번: 동전 0
첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수)
www.acmicpc.net
해결 방안 : 가장 큰 동전 값 부터 카운트를 시작한다.
'code 공부' 카테고리의 다른 글
| 큰 이미지를 downsampling하는 코드 (0) | 2023.07.25 |
|---|---|
| 이미지 리사이징 code (0) | 2023.07.05 |
| 파이썬 파일 불러올 때 \UXXXXXXXX escape 에러 해결법 (0) | 2023.05.03 |