Category: C++ Coding Test Tutorials

In this course, we will cover geometric algorithm problems to prepare for coding tests. Geometric problems involve analyzing the conditions of given points, lines, and planes, and finding the optimal solution through this process. In particular, we will learn how to effectively solve these problems using C++.

Problem Description

Problem: Calculate the distance between the given two points A(x1, y1) and B(x2, y2). The distance formula is as follows:

distance = sqrt((x2 - x1)^2 + (y2 - y1)^2)

Through this problem, we will practice implementing basic mathematical formulas in C++. Additionally, we will learn the importance of data typing and numerical operations through distance calculations when given two points.

Problem Solving Process

1. Input: Receive the coordinates of the two points from the user.

#include 
#include  // Library for using the sqrt function

using namespace std;

int main() {
    double x1, y1, x2, y2;
    
    cout << "Enter the x and y coordinates of point A: ";
    cin >> x1 >> y1;
    cout << "Enter the x and y coordinates of point B: ";
    cin >> x2 >> y2;

    return 0;
}

2. Distance Calculation: Apply the distance formula using the input coordinates.

double distance = sqrt(pow(x2 - x1, 2) + pow(y2 - y1, 2));

3. Output Result: Print the calculated distance on the screen.

cout << "The distance between point A and point B is: " << distance << "." << endl;

Complete Code

Combining the above processes, the final code is as follows:

#include <iostream>
#include <cmath>

using namespace std;

int main() {
    double x1, y1, x2, y2;

    cout << "Enter the x and y coordinates of point A: ";
    cin >> x1 >> y1;
    cout << "Enter the x and y coordinates of point B: ";
    cin >> x2 >> y2;

    double distance = sqrt(pow(x2 - x1, 2) + pow(y2 - y1, 2));
    cout << "The distance between point A and point B is: " << distance << "." << endl;

    return 0;
}

Conclusion

In this course, we covered a simple geometric algorithm problem. We implemented a basic algorithm to calculate the distance between two points using C++. In the next lesson, we plan to deal with more complex geometric problems or learn problem-solving methods using various data structures.

In this article, we will discuss the concept and implementation of Radix Sort, as well as detail the process through practical problems.

1. Overview of Radix Sort

Radix Sort is a special type of sorting algorithm that is effective when the data to be sorted consists of integers or strings within a specific range. Unlike typical sorting algorithms, Radix Sort sorts based on “digits.” Through this, Radix Sort has a time complexity of O(d(n + k)), where d is the number of digits, n is the number of data to be sorted, and k is the range of values.

2. Principle of Radix Sort

Radix Sort is performed through the following process:

1. Starting from the least significant digit, numbers are sorted based on each digit.
2. Sorting is repeated for each digit.
3. Once sorting is completed for all digits, a fully sorted array is obtained.

Radix Sort is typically implemented as a stable sorting algorithm, meaning that the order of elements with the same value retains their relative positions.

3. Implementation of Radix Sort

Let’s implement Radix Sort in C++. Here is the basic implementation of Radix Sort:

#include <iostream>
#include <vector>

using namespace std;

// Function for sorting based on a specific digit
void countingSort(vector<int> &arr, int exp) {
    int n = arr.size();
    vector<int> output(n);
    int count[10] = {0}; // Range of numbers is 0~9

    // Count occurrences of each digit
    for (int i = 0; i < n; i++) {
        count[(arr[i] / exp) % 10]++;
    }

    // Calculate cumulative sum
    for (int i = 1; i < 10; i++) {
        count[i] += count[i - 1];
    }

    // Build the output array
    for (int i = n - 1; i >= 0; i--) {
        output[count[(arr[i] / exp) % 10] - 1] = arr[i];
        count[(arr[i] / exp) % 10]--;
    }

    // Store the result in the original array
    for (int i = 0; i < n; i++) {
        arr[i] = output[i];
    }
}

// Radix Sort function
void radixSort(vector<int> &arr) {
    // Find the maximum value
    int maxVal = *max_element(arr.begin(), arr.end());

    // Sort by each digit
    for (int exp = 1; maxVal / exp > 0; exp *= 10) {
        countingSort(arr, exp);
    }
}

// Main function
int main() {
    vector<int> arr = {170, 45, 75, 90, 802, 24, 2, 66};
    radixSort(arr);
    
    cout << "Sorted array: ";
    for (int i : arr) {
        cout << i << " ";
    }
    
    return 0;
}
        

This code demonstrates the basic flow of Radix Sort. The countingSort function counts the occurrences for each digit and sorts the elements based on that. The radixSort function calls countingSort for each digit and returns the final sorted array.

4. Example Problem Solved with Radix Sort

Now, let’s present an algorithm problem that can be solved using Radix Sort.

Problem: Sort the given list of integers using Radix Sort.

Input: [170, 45, 75, 90, 802, 24, 2, 66]

Output: [2, 24, 45, 66, 75, 90, 170, 802]

Problem-solving process

1. Find the maximum value, which is confirmed to be 802. This value determines the highest digit.
2. Start with the least significant digit and call countingSort for each digit in the order of 1’s place, 10’s place, and 100’s place.
3. After sorting each digit, the final array will be sorted.

Try solving the problem using Radix Sort!

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.

In modern algorithm problem solving, graphs are a very important and fundamental data structure. In this article, we will explain the representation of graphs and learn how to solve related problems using C++.

What is a graph?

A graph is a data structure composed of vertices and edges, which is useful for expressing various relationships. For instance, graphs can be utilized in various scenarios such as relationships between users in a social network, connections between cities in a road network, and links between web pages.

Methods of graph representation

Graphs are generally represented in two ways: Adjacency Matrix and Adjacency List. Each method has its own advantages and disadvantages, so it is important to choose the appropriate method according to the nature of the problem.

1. Adjacency Matrix

An adjacency matrix is a way to represent a graph using a two-dimensional array. The size of the matrix is V x V (where V is the number of vertices), and each element of the matrix (i, j) indicates whether there is an edge between vertex i and vertex j.

        // Declaration of adjacency matrix in C++
        const int MAX = 100; // Maximum number of vertices
        int adj[MAX][MAX]; // Adjacency matrix
        int V; // Number of vertices
        

The advantage of an adjacency matrix is that it allows you to check the existence of a specific edge in O(1) time. However, in terms of memory, it uses the square of V, making it inefficient when there are many vertices but few edges.

2. Adjacency List

An adjacency list is a method that uses a list of vertices connected to each vertex. This is more suitable for sparse graphs.

        // Declaration of adjacency list in C++
        #include 
        #include 
        using namespace std;

        vector adj[MAX]; // Adjacency list
        int V; // Number of vertices
        

The adjacency list uses memory more efficiently and requires O(E) time to traverse the list of edges.

Problem: Finding Connected Components

In this problem, you need to find all components that are interconnected in the given directed graph. In other words, you need to identify the set of vertices that can be reached starting from a single vertex.

Problem Description

Given the number of vertices V and the number of edges E, with each edge provided as a pair of two vertices, write a program to find and output all connected components in this graph.

Input Format

• First line: Number of vertices V (1 ≤ V ≤ 1000)
• Second line: Number of edges E (0 ≤ E ≤ 10000)
• Next E lines: Each line represents an edge in the form (u, v)

Output Format

Output the number of connected components and the vertices of each component in ascending order.

Problem-solving Process

To solve the problem, we will use an adjacency list to store the graph and find connected components using depth-first search (DFS).

Step 1: Constructing the Adjacency List

First, we need to take the input and construct the adjacency list. We will input the number of vertices and edges and complete the list representing the relationships through each edge.

Step 2: Finding Connected Components with DFS

Whenever a search occurs, we mark the visited vertex, and repeat this until there are no more vertices to visit, thereby finding the components. The implementation of DFS can be easily done recursively.

        #include 
        #include 
        #include 

        using namespace std;

        vector adj[1001]; // Adjacency list
        bool visited[1001]; // Visit check
        vector> components; // Store connected components

        void dfs(int v, vector &component) {
            visited[v] = true; // Mark as visited
            component.push_back(v); // Add to the component

            for (int u : adj[v]) {
                if (!visited[u]) {
                    dfs(u, component); // Recursion
                }
            }
        }

        int main() {
            int V, E;
            cin >> V >> E;

            for (int i = 0; i < E; i++) {
                int u, v;
                cin >> u >> v; // Input edge
                adj[u].push_back(v); // Construct adjacency list
                adj[v].push_back(u); // Assuming an undirected graph
            }

            // Finding connected components for each vertex
            for (int i = 1; i <= V; i++) {
                if (!visited[i]) {
                    vector component;
                    dfs(i, component); // DFS search
                    components.push_back(component); // Store found component
                }
            }

            // Output results
            cout << components.size() << "\n"; // Number of connected components
            for (const auto &component : components) {
                sort(component.begin(), component.end()); // Sort the component
                for (int v : component) {
                    cout << v << " "; // Output vertices
                }
                cout << "\n";
            }

            return 0;
        }
        

The above code implements the logic to find and output connected components from the input graph. It sorts and outputs each component in ascending order.

Conclusion

We have examined the representation of graphs and the process of solving problems using DFS. Graphs play an important role in various algorithm problems, and learning them is fundamental to achieving good results in coding tests. I hope this course enhances your basic understanding of graphs and your problem-solving skills.

Approach to the Problem

The range sum problem can be solved in various ways, but an efficient approach is to use
Prefix Sum. With prefix sums, you can calculate the sum for the given range
[left, right] in O(1) time complexity.

The basic idea is to precompute and store the sum for each index in the array.
With this, the sum of a specific range can be calculated as follows.

sum(left, right) = prefixSum[right] - prefixSum[left - 1]

Here, prefixSum[i] is the sum from the start of the array to the i-th element.
This method has a time complexity of O(N) since it involves one traversal of the array, and afterwards, each range sum can be computed in O(1).

Implementation

Code

#include <iostream>
#include <vector>

using namespace std;

class SubarraySum {
public:
    SubarraySum(const vector<int>& arr) {
        int n = arr.size();
        prefixSum.resize(n + 1);
        prefixSum[0] = 0; // prefixSum[0] is initialized to 0.
        
        for (int i = 1; i <= n; i++) {
            prefixSum[i] = prefixSum[i - 1] + arr[i - 1];
        }
    }

    int getSum(int left, int right) {
        return prefixSum[right] - prefixSum[left - 1];
    }

private:
    vector<int> prefixSum; // Array to store the prefix sum.
};

int main() {
    int n; // Size of the array
    cout << "Enter the size of the array: ";
    cin >> n;
    vector<int> arr(n);
    cout << "Enter the elements of the array: ";
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }

    SubarraySum subarray(arr);

    int left, right;
    cout << "Enter the left boundary of the range (starting from 1): ";
    cin >> left;
    cout << "Enter the right boundary of the range: ";
    cin >> right;

    int result = subarray.getSum(left, right);
    cout << "The sum of the range [" << left << ", " << right << "] is: " << result << endl;

    return 0;
}
    

Code Explanation

Class Definition

The SubarraySum class provides the functionality to calculate range sums.
The constructor of this class initializes the prefix sum based on the array elements provided.
It defines a variable n to store the size of the array and creates the prefixSum array (including one for [0]).

Prefix Sum Calculation

Through the for loop inside the constructor, the array is traversed to store
the sums up to each index in the prefixSum array.
This is unique because it has a size of one more than the array size, starting from the first index.

Range Sum Calculation

The getSum(int left, int right) method returns the range sum using the provided left and right indices. It easily calculates the range sum using
prefixSum[right] - prefixSum[left - 1].

Testing and Usage

With this code, users can input the left and right boundaries of the range and easily calculate
the sum of that range. This algorithm runs smoothly even as the input array size increases,
allowing for the range sum to be processed quickly in O(1) time complexity.

Conclusion

The range sum problem is widely used in various applications, and
this prefix sum approach demonstrates its utility in areas like data analysis and statistical processing.
This simple yet effective method can enhance the efficiency of problem-solving.

I hope this lecture aids you in preparing for your C++ coding tests!