실전 알고리즘 0x11강 - 그리디

그리디

[ 알고리즘 설명 ]

- 지금 가장 최적인 답을 근시안적으로 택하는 알고리즘

- 관찰을 통해 탐색 범위를 줄이는 알고리즘

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를 사용한다.