일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | |||||
3 | 4 | 5 | 6 | 7 | 8 | 9 |
10 | 11 | 12 | 13 | 14 | 15 | 16 |
17 | 18 | 19 | 20 | 21 | 22 | 23 |
24 | 25 | 26 | 27 | 28 | 29 | 30 |
Tags
- 파이썬
- Algorithm
- DRF
- 알고리즘
- django ORM
- c++
- 알고리즘 풀이
- Git
- js
- Baekjoon
- java
- 백준
- API
- javascript
- django rest framework
- es6
- PYTHON
- form
- react
- django widget
- Django
- CSS
- HTML
- 장고
- 알고리즘 연습
- web
- AWS
- 알고리즘 문제
- MAC
- 파이썬 알고리즘
Archives
- Today
- Total
수학과의 좌충우돌 프로그래밍
[Algorithm] 그리디 알고리즘 본문
그리디 알고리즘
은 한국어로 탐욕 알고리즘 이라고도 하며 결정해야 하는 순간 가장 좋다고 생각하는 것을 선택하면서 답을 찾아가는 알고리즘을 말합니다.
이 방식의 한계점은 그 순간에는 최적일지도 모르지만 최종적으로는 답이 아닐 수 있는 경우가 많기 때문에 그리디 알고리즘을 사용한 경우, 최적이라는 걸 입증하는게 쉽지 않습니다. 그래도 입증만 한다면 구현하는건 다른 알고리즘에 비해 쉬운 편입니다.
문제를 풀면서 이해해보도록 하겠습니다.
BAEKJOON 동전 0
https://www.acmicpc.net/problem/11047
#include <iostream>
using namespace std;
int main(int argc, const char * argv[]) {
int coin[10];
int coinNum = 0;
int N,K;
cin >> N >> K;
for (int i=0;i<N;i++){
cin >> coin[i];
}
for (int i=N-1;i>=0;i--){
int temp = K / coin[i];
coinNum += temp;
K -= coin[i] * temp;
}
cout << coinNum << "\n";
return 0;
}
화폐의 가치가 큰 동전부터 순회하면서 그 순간 최적의 수, 최대한 동전을 많이 사용하도록 합니다. 여기서 다음과 같은 그리디 알고리즘을 사용할 수 있는 이유는 아래와 같은 문장 때문입니다.
둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수)
동전의 가치가 서로 배수관계에 있기 때문에 가능합니다. 만약 다음과 같은 언급이 없었으면 반례가 존재합니다.
3 1200
1
100
400
500
그리디 알고리즘
을 사용한다면 500원 짜리 두 개를 사용한 후 100원 짜리 두 개를 더 사용하여 4개 동전을 사용하는 반면, 400원 동전을 통해 3개만에 만들 수 있습니다.
이처럼 그리디 알고리즘
은 사용할 수 있음을 증명만 한다면 쉽지만 조금만 조건이 바뀌더라도 예외사항이 많이 존재하기 때문에 쉬지만은 않은 알고리즘 입니다.
'알고리즘 > 이론' 카테고리의 다른 글
[Algorithm] 유니온 파인드(Union - Find) (11) | 2019.09.22 |
---|---|
[Algorithm] Divide and Conquer, 분할 정복 (0) | 2019.09.20 |
[Algorithm] 범위에 따른 이항계수 구하는 방법 (0) | 2019.09.11 |
[Algorithm] 범위에 따른 피보나치 수 구하는 방법 (0) | 2019.09.09 |
[Algorithm] 분할 정복을 이용한 a^b (0) | 2019.09.08 |
Comments