| 그리디(Greedy)란 |
Greedy란 단어에서 느껴지듯이 Greedy 알고리즘은 아주 탐욕스런 알고리즘이다.
그리디 알고리즘의 핵심은 여러 선택에 있어서 앞으로의 선택을 고려하지 않고 각각의 선택마다 가장 최선의 선택을 하는 것이다. 즉, 우리가 선택할 경우에는 가장 최적의 선택만을 하지만, 그리디 알고리즘은 각각 선택에 있어서는 최적이 될지는 모르나 전체적으로 최적이 아닐 수도 있다는 것을 명심해야 한다.
우리가 그리디 알고리즘을 사용함에 있어서 가장 고려해야 할 부분이 바로 이 "전체적으로 최적이 될 것인가?" 라는 부분이다.
다음 예시를 통해 좀더 구체적이고 자세히 알아보자.
<예시> 어느 슈퍼마켓에서 우리는 물건을 팔고 있다. 어느 손님이 오셨을 때 1000원을 내고 물건을 230원어치 샀다. 이때 우리는 동전을 770원을 거슬러 줘야 한다. 단, 우리는 동전의 개수를 최소화하여 거슬러 줘야 한다. 즉, 10원짜리 77개를 줘서는 안 되는 것이다. 어떻게 하면 동전의 개수를 최소화하여 거슬러 줄 수 있을까? |
| 그리디 알고리즘에서 중요한 점은 앞에서 언급했듯이 그리디로 나온 해답이 가장 최적의 해답이 아닐 수도 있다는 것이다. 예를 들어, 한국은행에서 600원짜리 동전이 나왔을 경우 우리가 1600원을 거슬러 줘야 한다면, 그리디에선 600 + 600 + 100 + 100 + 100 +100 = 6개 사용한다. 그러나 실제로는 500 + 500 + 500 + 100 = 4개 사용이 최적화가 된다. |
| 그리디(Greedy) 알고리즘 개념 |
- 그리디 알고리즘을 사용할 때, 설계의 기본은 선택할 것이 여러 개일 경우, 그 중 가장 좋은 것을 선택한다는 것이다.
- 문제를 여러 단계로 구분하여 각 단계마다 그 단계에 해당하는 최적해를 구한다.
- 각 단계마다 최적해를 구하는 과정에선 가장 큰 것 또는 가장 작은 것을 선택한다.
(예) 잔돈 거슬러 주기 문제는 - 큰 단위의 잔돈을 먼저 선택하고 계산하여 준다.
- 정확한 알고리즘은 아니지만, 빠른 단계적 최적화를 구할 때 사용한다.
- 가장 간단한 설계이면서, 다양한 문제들에 적용할 수 있다.
| 그리디 알고리즘을 구현할 때의 유의점 |
여러 선택에 있어서 전체적인 최적해를 고려하지 않고
각각의 선택에 있어서 가장 최적의 선택을 하기 때문에
전체적으로 최적이 될 수 없는 경우가 있다.
따라서 '전체적인 최적이 될 것인가?'라는 점을 항상 염두에 두고 알고리즘을 구현해야 한다.
| 그리디 알고리즘의 응용범위 |
다익스트라(Dijkstra)의 최단경로 알고리즘이나
MST(Minimum Spaning Tree=최소비용신장트리) 같은 유명한 알고리즘들은
그리디 알고리즘을 이용한 대표적인 문제라고 불 수 있다.
| 그리디는 sort를 알아야 한다. |
정렬(Sort)이란 임의의 순서대로 배열되어 있는 자료의 집합을 일정한 순서대로 재배열하는 것을 의미한다.
예를 들어, 1부터 10까지의 번호가 적힌 카드가 순서 없이 배열되어 있다고 하자.
이때 오름차순(ascending order)으로 정렬한다는 것은 1, 2, 3, 4 순으로 10까지의 카드를 순서대로 배열함을 말하며,
내림차순(descending order)으로 정렬한다는 것은 10, 9, 8, 7 순으로 정렬을 수행하는 것이다.
| sort의 종류 |
- 버블 정렬(Bubble sort)
- 삽입 정렬(Insert sort)
- 선택 정렬(selection sort)
- 쉘(Shell) 정렬
- 퀵 정렬(quick sort) 등등....
[ 문제1 ] 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
[ 문제2 ] www.acmicpc.net/problem/11399
11399번: ATM
첫째 줄에 사람의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어진다. (1 ≤ Pi ≤ 1,000)
www.acmicpc.net
[ 문제3 ] www.acmicpc.net/problem/5585
5585번: 거스름돈
타로는 자주 JOI잡화점에서 물건을 산다. JOI잡화점에는 잔돈으로 500엔, 100엔, 50엔, 10엔, 5엔, 1엔이 충분히 있고, 언제나 거스름돈 개수가 가장 적게 잔돈을 준다. 타로가 JOI잡화점에서 물건을 사
www.acmicpc.net
[ 문제4 ] www.acmicpc.net/problem/10162
10162번: 전자레인지
3개의 시간조절용 버튼 A B C가 달린 전자레인지가 있다. 각 버튼마다 일정한 시간이 지정되어 있어 해당 버튼을 한번 누를 때마다 그 시간이 동작시간에 더해진다. 버튼 A, B, C에 지정된 시간은
www.acmicpc.net
[ 문제5 ] www.acmicpc.net/problem/1138
1138번: 한 줄로 서기
첫째 줄에 사람의 수 N이 주어진다. N은 10보다 작거나 같은 자연수이다. 둘째 줄에는 키가 1인 사람부터 차례대로 자기보다 키가 큰 사람이 왼쪽에 몇 명이 있었는지 주어진다. i번째 수는 0보다
www.acmicpc.net
[ 문제6 ] www.acmicpc.net/problem/1439
1439번: 뒤집기
다솜이는 0과 1로만 이루어진 문자열 S를 가지고 있다. 다솜이는 이 문자열 S에 있는 모든 숫자를 전부 같게 만들려고 한다. 다솜이가 할 수 있는 행동은 S에서 연속된 하나 이상의 숫자를 잡고 모
www.acmicpc.net
[ 문제7 ] www.acmicpc.net/problem/14916
14916번: 거스름돈
첫째 줄에 거스름돈 액수 n(1 ≤ n ≤ 100,000)이 주어진다.
www.acmicpc.net
[ 문제8 ] www.acmicpc.net/problem/14720
14720번: 우유 축제
영학이는 딸기우유, 초코우유, 바나나우유를 좋아한다. 입맛이 매우 까다로운 영학이는 자신만의 우유를 마시는 규칙이 있다. 맨 처음에는 딸기우유를 한 팩 마신다. 딸기우유를 한 팩 마신 후
www.acmicpc.net
[ 문제9 ] www.acmicpc.net/problem/1931
1931번: 회의실배정
(1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다.
www.acmicpc.net
[ 문제10 ] www.acmicpc.net/problem/1541
1541번: 잃어버린 괄호
첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다
www.acmicpc.net
'C언어 알고리즘' 카테고리의 다른 글
| [동적계획법 5일차] 다이나믹 프로그래밍 - 최장 공통 부분 문자열(LCS) - 10문제 (0) | 2021.02.05 |
|---|---|
| [동적계획법 6일차] 다이나믹 프로그래밍 - 기업투자 (0) | 2021.02.05 |
| [동적계획법 문제풀이 1] - 문제 19 (0) | 2020.09.12 |
| [동적계획법 3일차] 다이나믹 프로그래밍 ( 배낭문제 ) - 11문제 (0) | 2020.09.10 |
| [동적계획법 2일차] 다이나믹 프로그래밍 기초 - 동전교환 - 4문제 (0) | 2020.09.10 |
