[3-1] Q : 카운터에는 거스름돈으로 사용할 500원, 100원, 50원, 10원짜리 동전이 무한히 존재한다. 거슬러줘야 할 돈이 N원일 때 거슬러 줘야 할 동전의 최소 개수를 구해라.
A : 동전의 수를 가장 적게 주려면 가장 큰 화폐단위(500원)부터 거슬러 주면 된다. 여기서 그리디 알고리즘이 사용된다. 그리디 알고리즘은 항상 최적의 해를 보장하지 않는다. 따라서 그리디 알고리즘으로 문제를 풀었을 경우에는 그 풀이가 정당한지 확인해야 한다. 이 문제의 경우에는 가지고 있는 동전 중 큰 단위의 동전은 항상 더 작은 단위의 배수이기 때문이다. 때문에, 항상 10원짜리 30개, 50원짜리 6개를 주는 것보다 100원짜리 3개를 주는 것이 낫다.
위 코드의 경우, 동전의 수가 K라면 시간복잡도는 O(K)이다. 이 알고리즘의 시간복잡도는 받아야 하는 돈(N)에는 관련이 없고, 거슬러 줘야 하는 화폐의 종류(K)에만 관련이 있다.
[3-2] Q : 다양한 수로 이루어진 배열이 있을 때, 주어진 수들을 M번 더하여 가장 큰 수를 만드는 법칙을 큰수의 법칙이라 한다. 단, 배열의 특정한 인덱스에 해당하는 수가 연속해서 K번을 초과해 더해질 수 없다는 것이 이 법칙의 특징이다. 예를 들어 2,4,5,4,6으로 이루어진 배열이 있을 때 M이 8이고 K가 3이라 가정하면, 특정 인덱스의 수가 연속해 세 번까지만 더해질 수 있으므로 결과는 6+6+6+5+6+6+6+5인 46이 된다. 첫 줄에는 배열의 크기 N, 숫자가 더해지는 횟수 M, K가 입력된다. 둘째 줄에는 N개의 자연수가 공백으로 구분되어 입력된다.
A :위 코드로 큰수의 법칙을 해결할 수 있었다. 그리디 알고리즘을 사용하기 적합한 문제다.
하지만 더 효율적인 해결법이 있다. 반복되는 수열을 파악하고, 이를 바탕으로 푸는 것이다. 예를 들어, Q에서의 예시에서는 [6,6,6,5] + [6,6,6,5]로 나누어 볼 수 있다. 가장 큰 수와 두번째로 큰 수가 더해질 때는 일정 패턴이 반복해서 나타나게 된다. 가장 큰 수가 K번 나타나고, 두번째로 큰 수가 한 번 나타나는 것이다. 이를 구현하면 아래와 같다.
위 풀이대로라면, M이 K+1 크기의 배열로 나누어 떨어지는 경우가 있지만, 그렇지 않은 경우도 있다. 그래서 처음에는 line 7에서 if (M//(K+1) == 0)으로 해서 두 케이스일때의 tot을 나눠서 기술하려 했지만, line 7처럼 쓰면 어차피 M%(K+1) == 0일 때는 뒷 항이 0이 되므로 한 번에 써도 괜찮다.
[3-3] Q : 어떠한 수 N이 1이 될때까지 다음의 두 과정 중 하나를 반복적으로 선택해 수행한다. 둘째 연산은 N이 K로 나누어 떨어질때만 선택할 수 있다. 1. N에서 1을 뺀다. 2. N을 K로 나눈다. 예를 들어, N이 17, K가 4라고 가정하자. 1->2->2 순으로 수행하면 N은 1이 되고, 전체 과정을 실행한 횟수는 3이다. 첫 줄에 N과 K가 공백을 두고 입력된다. N이 1이 될때까지 수행해야 하는 최소한의 횟수를 출력해라.
A : 이 문제에서는 K가 2 이상이라면 1을 수행하는 것 보다 2를 수행하는 것이 이득이다. 따라서 최대한 2를 많이 수행하는 것이 좋기에 그리디 알고리즘을 사용할 수 있다. line 14~16에서는 N을 1씩 감소시키고 cnt도 1씩 증가시켰지만, 그 대신 N%K씩 cnt를 증가시키고 N을 감소시키면 연산횟수를 더 줄일 수 있다.
