GREEDY 알고리즘
Greedy 알고리즘이란 ?
현재 상황에서 지금 당장 최선인 것, 좋은 것만을 고르는 알고리즘이다. 또한 탐욕 법이라고도 불립니다.
Greedy 알고리즘은 '정당성' 분석이 매우 중요합니다. - 단순히 가장 좋아보이는 것을 반복저긍로 선택해도 최적의 답을 구할 수 있는지 검토가 필요합니다.
일반적인 상황에서 Greedy 그리디 알고리즘은 최적의 해를 보장할 수 없을 때가 많습니다. 왜냐하면 탐욕법은 당장의 좋은 것을 선택하기 때문입니다. 하지만 코딩테스트의 Greedy 문제는 대개 탐욕법으로 얻은 답(해)이 최적의 답이 되는 상황이 주어집니다.
그리디 알고리즘의 대표문제 :
그리디 알고리즘은 대표적으로 k 원의 돈을 건네야할 때 n개의 잔돈 가짓수(500원, 100원, 50원..) 를 최소로 사용하는 값을 구하는 문제 등이 있습니다.
화폐의 종류가 n라고 할 때, 코드의 시간 복잡도는 O(n) 입니다. 거슬러줘야하는 금액과는 무관하며 동전의 총 종류에만 영향을 받습니다.
백준 사이트의 그리디 알고리즘 문제 :
https://www.acmicpc.net/problem/5585
5585번: 거스름돈
타로는 자주 JOI잡화점에서 물건을 산다. JOI잡화점에는 잔돈으로 500엔, 100엔, 50엔, 10엔, 5엔, 1엔이 충분히 있고, 언제나 거스름돈 개수가 가장 적게 잔돈을 준다. 타로가 JOI잡화점에서 물건을 사
www.acmicpc.net
https://www.acmicpc.net/problem/2839
2839번: 설탕 배달
상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그
www.acmicpc.net
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/11047
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
References: https://www.youtube.com/watch?v=5OYlS2QQMPA
'Python > Python 코딩테스트' 카테고리의 다른 글
| [ 그리디 알고리즘 1 ] 백준 1774 수 묶기 파이썬 (0) | 2021.07.14 |
|---|---|
| [Python] 백준 1946번 이해하기 (0) | 2021.07.07 |
| [Python 파이썬] 해시 (Hash) 해싱 (Hashing) 알고리즘 예제로 알아보기 (0) | 2021.07.04 |
| [프로그래머스] 모의고사 파이썬 python (0) | 2021.06.23 |
| [프로그래머스] python 2016년 (0) | 2021.06.22 |
댓글