그리디

* 현재 상황에서 지금 당장 좋은 것만 고르는 방법

* 암기한다고 해서 잘풀수 있는 문제는 아님

* 정렬 알고리즘문제와 짝을 이뤄 출제되는 경우가 많음

 

문제1) 거스름돈

- 500, 100, 50, 10 단위의 동전 무한히 존재

- 거슬러 줘야 할 돈은 N (단, N은 10의 배수)

- 거슬러 줘야 할 동전의 최소 개수

 

문제2) 큰 수의 법칙

- N은 배열의 크기, M은 숫자가 더해지는 횟수, K는 특정 수가 연속해서 더해질수 있는 최대 횟수

 

문제3) 1이 될 때까지

- 어떠한 수 N이 1이 될 때까지 수행

- 1) N에서 1을 뺀다. 2) N을 K로 나눈다. 두가지 연산만 반복 선택하여 수행 (단, 2번째 연산은 K로 나눠질때만 가능)