5. 알고리즘 정리 [그리디]

그리디 알고리즘, 흔히 말해 탐욕기법이다.

우선 해당 알고리즘의 동작 형태 및 구현 방법에 대해서 익혀보자

 

그리디 탐욕기법은, 경우의 수가 존재할 경우, 매순간 최선의 경우를 선택하는 알고리즘이다.

현재 상황에서 가장 좋다고 생각되는 것을 선택해 나가는 것이기 떄문에, 항상 가장 좋은 결과를 만드는 것은 아니다.

 

그럼, 그냥 문제를 바로 풀어보자

 

* 동전 0

https://www.acmicpc.net/problem/11047

11047번: 동전 0

 

상당히 간단하다, 문제에서 오름차순으로 준다고해서, 별도 정렬 도필요없고

그냥 끝번호부터 차례로 나눌수있는지 체크를해서 더해주고

 

나머지와 몫을 잘활용하면 된다.

 

 

 

그리디 알고리즘은 솔직히 항상 최적의 해를 만족한다고 보기어려워서 

잘 안쓰일것같다.

하지만 한문제만 더 풀어보자

 

* 회의실 배정

https://www.acmicpc.net/problem/1931

1931번: 회의실 배정

 

 

이 문제는 그리디의 어떻게 보면 예제 같은 문제인데,

해결방법은 간단하다. 근데 조금 깊게 생각해보면 이 값에 대한 테스트케이스가 좀 더 많거나 깊다면, 틀릴것같다.

그리디는 조금 애매하다. 사실 탐욕기법이라기 보다, 그냥 다이나믹 프로그래밍에 대한 일련 간단 방법? 같기도 하다.

 

무튼, 방법은 종료시간에 대한 정렬 뒤에, 하나씩 추가하고, 종료시간을 갱신, 시작시간과 종료시간을 비교해 가면서 값을 추가 하는 것이다.

 

이런 문제는 사실 연습에 큰 도움이 안될 것같다.