JavaScript Coding Test Course, Greedy Algorithm

A Greedy Algorithm is an algorithm that makes the most suitable choice at every moment to find the optimal solution. It aims to make choices that seem optimal at each step to optimize the overall problem, although this choice does not always guarantee the optimal solution to the entire problem. However, it is often used because there are many cases where the greedy algorithm can easily solve problems.

Problem: Coin Change

You are the shopkeeper, and you need to give the customer change in coins. The shop has the following coins available:

• 500 won coin
• 100 won coin
• 50 won coin
• 10 won coin

You want to use the optimal number of coins to give change to the customer. If the customer requests 1260 won in change, you can give the coins as follows:

• 2 pieces – 500 won
• 2 pieces – 100 won
• 1 piece – 50 won
• 1 piece – 10 won

In total, you will give out 6 coins. The input and output format of the program is as follows:

Input

First line: Amount of change to give N (1 <= N <= 10,000)

Output

Minimum number of coins

Problem Solving Process

1. Understanding the Problem

To solve the problem, we need to minimize the number of coins for the given amount. We approach the problem by starting with the highest denomination of coins and recalculating the remaining amount.

2. Algorithm Design

By applying the greedy algorithm, we proceed with the following steps:

• Check the given amount N.
• Sort the coin values from largest to smallest.
• Use the value of each coin to reduce the amount.
• Count the number of coins used each time a coin is used.
• Repeat this process until the remaining amount is 0.

3. Code Implementation

Now, let’s write the JavaScript code to solve the problem.

function minCoins(N) {
    const coins = [500, 100, 50, 10]; // Coin values
    let count = 0; // Coin count

    for (let i = 0; i < coins.length; i++) {
        // Calculate how many of the current coin can be used by dividing by N
        count += Math.floor(N / coins[i]);
        // Subtract the used amount from N
        N %= coins[i]; 
    }
    
    return count;
}

// Example usage
const amount = 1260; // Requested change
console.log(`Minimum number of coins: ${minCoins(amount)}`); // Output: 6

4. Code Explanation

In the above code:

• The minCoins function receives the change amount through the parameter N.
• The coins array lists the coin values from largest to smallest.
• Through a for loop, we check each coin value and calculate the number of usable coins using Math.floor(N / coins[i]).
• After using the coin, the remaining amount is updated with N %= coins[i].
• Finally, the total number of coins is returned.

5. Functionality Check

Now, we will run various test cases using the above code to check its functionality. Let’s test various inputs.

console.log(minCoins(5000)); // Output: 10
console.log(minCoins(1000)); // Output: 2
console.log(minCoins(560));  // Output: 2
console.log(minCoins(9999)); // Output: specific value

Conclusion

In this lesson, we solved the coin change problem using a greedy algorithm. The greedy algorithm is very useful for simple problems and helps solve various issues, such as coin problems or knapsack problems. Moving forward, try to solve various greedy algorithm problems to gain more experience.