C++ Coding Test Course, Greedy Algorithm

1. What is a Greedy Algorithm?

A Greedy Algorithm is a method of solving problems by making the optimal choice at each stage of the process. Generally, greedy algorithms solve problems step by step, assuming that the optimal choice at each stage will lead to the optimal solution for the entire problem. However, such greedy choices do not always guarantee an optimal solution.

2. Characteristics of Greedy Algorithms

Myopic Approach: Since it selects the optimal solution for the current problem, there is no guarantee that the final result will be optimal.
Suitability Varies: Greedy algorithms do not provide optimal solutions for all problems, but there are many problems that can be solved efficiently.
Structural Features: Effective for problems with optimal substructure and greedy choice properties.

3. Problem Description

This lecture will cover the “Change Making” problem, which frequently appears in coding tests. This problem is defined as follows:

Write a program that gives change using the minimum number of coins. The coins available are 500 won, 100 won, 50 won, and 10 won. When the given amount is N won, implement an algorithm that gives change with the minimum number of coins.

4. Problem Analysis

To give change with the minimum number of coins, it is effective to start using the largest coins first to reduce the amount of change. This way, as the remaining amount decreases, it can ensure an optimal solution. By using the selection property of greedy algorithms, we can derive a solution through the following steps:

4.1. Required Coins

500 won
100 won
50 won
10 won

4.2. Coin Usage Process

We start using the largest coin as much as possible. For example, when giving change of 1260 won, the number of coins used is as follows:

500 won → 2 coins (1000 won)
100 won → 2 coins (200 won)
50 won → 1 coin (50 won)
10 won → 1 coin (10 won)

In total, 6 coins are used to give change for 1260 won.

5. Implementation

Now, let’s implement this process in C++. Below is the C++ code based on the above content:

#include <iostream>

using namespace std;

int main() {
    int change = 1260; // Amount to give as change
    int coinTypes[] = {500, 100, 50, 10}; // Available coins
    int coinCount = 0; // Number of coins used

    for(int i = 0; i < 4; i++) {
        coinCount += change / coinTypes[i]; // Divide by the current coin
        change %= coinTypes[i]; // Update remaining amount
    }

    cout << "Minimum number of coins: " << coinCount << endl;
    return 0;
}

6. Code Explanation

The above code is a program that calculates the minimum number of coins when the amount to give as change is 1260 won.

change: Stores the amount to give as change.
coinTypes: Stores the types of available coins in an array.
coinCount: Stores the total number of coins used.
Calculates how many of each coin are used using a for loop.
Updates the remaining amount to proceed to the next coin.

7. Result

When the above code is executed, the following result is displayed on the console:

Minimum number of coins: 6

8. Review

In this lecture, we learned how to solve the change-making problem using a greedy algorithm. The key of the greedy algorithm is to make the choice deemed optimal at each step. This algorithm can be very useful for solving various problems.

9. Practice Problems

You can further practice greedy algorithms through other assignments such as:

Receive the types of coins that can be used from a given amount and find the minimum number of coins.
Write a program that can adjust the value of individual coins arbitrarily.
Research and apply improved algorithms for performance enhancement.

10. Conclusion

The greedy algorithm is a powerful tool that can provide solutions to many problems. Through the problem presented in this lecture, I hope you have gained an understanding of the concepts of algorithms as well as practice in code implementation. I encourage you to continue learning about various algorithms to grow into a better programmer.