그리디
[ 알고리즘 설명 ]
- 지금 가장 최적인 답을 근시안적으로 택하는 알고리즘
- 관찰을 통해 탐색 범위를 줄이는 알고리즘
ex) 머지소트
- 이상적인 풀이 흐름
1. 관찰을 통해 탐색 범위를 줄이는 방법을 고안한다.
2. 탐색 범위를 줄여도 올바른 결과를 낸다는 사실을 수학적으로 증명한다. ( 코딩 테스트에서는 강한 믿음을 가진다 )
3. 구현해서 문제를 통과한다.
- 코딩 테스트에서의 추천 전략
1. 거의 똑같은 문제를 풀어봤거나 간단한 문제여서 나의 그리디 풀이를 100% 확신한다.
=> 짜서 제출해보고 틀리면 빠르게 손절
2. 100% 확신은 없지만 맞는 것 같은 그리디 풀이를 찾았다.
=> 일단은 넘어가고 다른 문제를 풀게 없거나 종료가 20-40분 남은 시점에 코딩 시작
[ 연습 문제 ]
ex) 백준 11047번 : https://www.acmicpc.net/problem/11047
D[i] = 가치의 합을 i로 만들 때 필요한 동전 개수의 최솟값
D[i] = min(D[i-A1], D[i-A2], ... , D[i-An]) +1
-> 시간 초과 발생
- 보조 정리 1 : 동전을 최소로 소모하면서 물건값을 지불하려면 10/100원 동전은 4개 이하, 50원 동전은 1개 이하로 사용해야 한다. (귀류법)
- pf) 10/100원 동전을 5개 이상 사용->50/500원 동전으로 대체, 50원 동전을 2개 이상 사용->100원 동전으로 대체
- 명제 : 동전을 최소로 소모하면서 물건값을 지불하려면 500원 동전을 최대한 많이 써야 한다.
- pf) 10, 50, 100원 동전으로는 물건값을 최대 10*4+50*1+100*4 = 490원만 감당 가능, 500원을 다 사용하지 않을 경우 10, 50, 100원 동전으로 500원 이상 감당해야 한다.
- 동전의 배수관계가 성립하지 않으면 위의 풀이가 적용되지 않는다.
ex) 백준 1931번 : https://www.acmicpc.net/problem/1931
1. O(2^n) : 모든 가능한 배정 방법을 확인
2. O(N^2) : 회의를 끝나는 시간이 빠른 순으로, 끝나는 시간이 같다면 시작 시간이 빠른 순으로 정렬
D[i] = i 번째 회의를 마지막으로 진행했을 때 최대 회의의 수
D[i] = max( D[j] ) + 1 ( j 번째 회의의 끝나는 시간이 i 번째 회의의 시작 시간 이하인 모든 j )
- 명제 : 현재 시간이 t라고 할 때 시작 시간이 t 이상인 모든 회의 중에서 가장 먼저 끝나는 회의를 택하는 것이 최적이다
- pf) 회의 A 대신 회의 B를 택했을 때 더 많은 회의를 배정할 수 있다고 가정 ( 귀류법 ) 모순
ex) 백준 2217번 : https://www.acmicpc.net/problem/2217
- 사용할 로프를 미리 정한다면 가장 최대 중량이 큰 순서대로 사용한다.
ex) 백준 1026번 : https://www.acmicpc.net/problem/1026
- 재배열 부등식
[ 잘못된 그리디 ]
ex) 백준 12865번 : https://www.acmicpc.net/problem/12865
- 0-1 knapsack
- 그리디로 풀게 되면 모순이 발생한다. ( DP문제 )
ex) 백준 1477번 : https://www.acmicpc.net/problem/1477
- 그리디로 풀려하면 현재 가장 긴 값의 중간에 휴게소를 세우려고 하지만 모순으로 휴게소가 하나도 없을 때 500, 250에 휴게소를 건설하여 틀리게 된다.
- parametric search를 사용한다.
'실전알고리즘 공부' 카테고리의 다른 글
실전 알고리즘 0x13강 - 이분탐색 (0) | 2022.05.18 |
---|---|
실전 알고리즘 0x12강 - 수학 (0) | 2022.05.15 |
실전 알고리즘 0x10강 - 다이나믹 프로그래밍 (0) | 2022.05.12 |
실전 알고리즘 0x0F강 - 정렬2 (0) | 2022.05.11 |
실전 알고리즘 0x0E강 - 정렬1 (0) | 2022.05.09 |