[4일차] 이.코.테.다! Ch3 그리디 greedy

Ch3. 그리디 greedy

1. 당장 좋은 것만 선택하는 그리디

    - 현재 상황에서 당장 좋은 것만을 골라 현재의 선택이 나중에 미칠 영향은 고려하지 않는 방법

    - 보통 코딩 테스트에서 출제되는 유형은 창의력, 즉 문제를 풀기 위한 최소한의 아이디어를 떠올릴 수 있는 능력을 요구한다.

      특정한 문제를 만났을 때, 그리디로 문제를 풀 수 있을지 파악할 수 있어야 한다.

   - 기준에 따라 좋은 것을 선택하는 알고리즘이기에 기준을 제시해주고, 정렬 알고리즘과 함께 짝을 이루어 출제된다.

      1-1. 예제 거스름돈

             - 문제

             - 소스 코드

             - 정당성
               : 가지고 있는 동전 중에서 큰 단위가 항상 작은 단위의 배수이므로 작은 단위의 동전들을 조합해 다른 해가 나올 수 X 

                 때문에 화폐이 단위가 무작위로 주어졌을 때에 그리디 알고리즘으로 해결할 수 없다.

    

      1-2. 그리디 알고리즘의 정당성

             - 대부분의 문제는 그리디 알고리즘을 이용했을 때 '최적의 해'를 찾을 수 없는 가능성이 다분하다.

               따라서, 그리디 알고리즘으로 문제의 해법을 찾았을 때는 그 해법이 정당한지 검토할 수 있어야 한다.

               Tip. 그리디 -> 다이나믹, 그래프 알고리즘

 

2. 큰 수의 법칙

    - 문제

    - 문제 해결

       : 가장 큰 수와 두번째로 큰 수를 저장한다. 연속으로 더할 수 있는 횟수는 최대 K번이므로

         '가장 큰 수를 K번 더하고, 두 번째로 큰수를 한 번 더하는 연산'을 반복하면 된다.

    - 소스 코드 1(python, M이 10,000 이하일 때)

    - 소스 코드 2(python, M이 100억 이상일 때)

       : 반복되는 수열 first와 second가 더해질 때 특정한 수열 형태로 일정하게 반복해서 더해지는 특징이 있다.

         반복되는 수열의 길이는 (K+1)이고 M을 (K+1)로 나눈 몫이 수열이 반복되는 횟수가 된다.
         여기에 (K+1)*M은 first가 반복하는 횟수가 되고, M이 (K+1)로 나누어 떨어지지 않는 것을 고려했을 때,

         '가장 큰 수가 더해지는 횟수는 int(M/(K+1)) * K + M%(K+1)'

    - 소스 코드 3(c++, M이 100억 이상일 때)

 

3. 숫자 카드 게임

    - 문제

    - 문제 해결

       : 각 행마다 가장 작은 수를 찾은 뒤에 작은 수들 중에서 가장 큰 수를 찾는 것이다.

    - 소스 코드

 

4. 1이 될 때까지

    - 문제

    - 문제 해결

       : 주어진 n에 대하여 최대한 많이 나누기 연산을 수행하면 된다.

    - 소스 코드