C++ Coding Test Tutorials 보관

C++ Coding Test Course, Hacking Efficiently

Problem Description

Given an integer array, write a program to determine whether it can be divided into two subsets with equal sums.

This problem is known as the ‘Subset Sum Problem’. It can be solved using Dynamic Programming.

Input Format

The first line contains the size of the array N (1 ≤ N ≤ 20).
The second line contains N integers of the array (each integer is between 0 and 10000).

Output Format

If it is possible to partition the subsets, print “YES”; otherwise, print “NO”.

Example Input

        4
        1 5 11 5

Example Output

YES

Approach to Solve the Problem

To solve this problem, you should follow these steps:

Calculate the sum of the input array.
If the sum is odd, it is impossible for the two subsets to have equal sums, so return “NO”.
If the sum is even, set the target value to half of the sum and use dynamic programming to determine if it can be achieved.
Set up a state table and check if each number can be used to form the target value.

C++ Code

#include <iostream>
#include <vector>
using namespace std;

bool canPartition(vector<int>& arr) {
    int sum = 0;
    for (int num : arr) sum += num;
    if (sum % 2 != 0) return false;

    int target = sum / 2;
    vector<bool> dp(target + 1, false);
    dp[0] = true;

    for (int num : arr) {
        for (int j = target; j >= num; j--) {
            dp[j] = dp[j] || dp[j - num];
        }
    }

    return dp[target];
}

int main() {
    int N;
    cin >> N;
    vector<int> arr(N);
    for (int i = 0; i < N; i++) {
        cin >> arr[i];
    }
    
    cout << (canPartition(arr) ? "YES" : "NO") << endl;
    return 0;
}

Code Explanation

The above code works as follows:

First, it calculates the total sum of the number array.
It checks if the sum is odd. If it is odd, it returns “NO”.
If the sum is even, it sets the target value to half of the sum and initializes the dynamic programming array.
By iterating through each number, it checks if it can create the target value.
Ultimately, it prints “YES” if the target value can be created; otherwise, it prints “NO”.

Time Complexity

The time complexity of this algorithm is O(N * target), where N is the number of input numbers and target is half of the total sum of the input array. This determines the number of operations that can be used to create different subsets.

Conclusion

This concludes the code and explanation for the Subset Sum Problem. Such algorithmic problems often appear in coding tests, so it is good to practice them frequently. In the next lecture, we will cover more complex problems and their solutions.

Questions and Feedback

If you have any questions about the code you wrote or any parts you find difficult to understand, feel free to leave a comment!

C++ Coding Test Course, Assigning Meeting Rooms

Assigning Meeting Rooms

Problem Description

There are N meetings that need to be conducted, each with a start time and an end time.
How can we assign meeting rooms to maximize the number of meetings?
In other words, an algorithm needs to be implemented to assign meeting rooms such that the meetings do not overlap.

Input: A list is given containing the start and end times of each meeting.
For example, there can be a list like [(0, 30), (5, 10), (15, 20)].

Output: Print the maximum number of meetings that can be scheduled.

Approach to the Problem

This problem is a typical greedy algorithm problem.
First, sort the meetings based on their end times,
then use the approach of proceeding with the meeting that ends the quickest and selecting the next meeting accordingly.

This way, we can make optimal meeting assignments without overlaps.
A meeting can only be conducted if its start time is greater than or equal to the end time of the previous meeting.

Step-by-Step Solution Process

Receive all meeting information.
Sort the meetings based on their end times.
Initialize a variable to count the maximum number of meetings.
Iterate through the meetings and add them if possible.
Print the total number of meetings that can be scheduled.

C++ Code Implementation

#include 
#include 
#include 

using namespace std;

// Structure for meeting information
struct Meeting {
    int start;
    int end;
};

// Function to sort meetings based on their end times
bool compare(Meeting m1, Meeting m2) {
    return m1.end < m2.end;
}

// Function to assign meeting rooms
int maxMeetings(vector &meetings) {
    // Sort based on end times
    sort(meetings.begin(), meetings.end(), compare);
    
    int count = 0;
    int lastEndTime = 0;

    for (const auto &meeting : meetings) {
        if (meeting.start >= lastEndTime) {
            // Proceed with the meeting
            count++;
            lastEndTime = meeting.end; // Update the last end time
        }
    }

    return count;
}

int main() {
    vector meetings = {{0, 30}, {5, 10}, {15, 20}};
    
    int result = maxMeetings(meetings);
    
    cout << "Maximum number of meetings that can be assigned: " << result << endl;
    return 0;
}

Explanation for Each Step

First, we use a structure to store the start and end times of the meetings.
An important point in greedy algorithms is that we need to sort each meeting by their end times.

After sorting, we use a loop to check each meeting.
If the start time of the current meeting is greater than or equal to the end time of the previous meeting,
we can conduct this meeting, so we increase the count and update the last end time.

After checking all meetings, the final counted value will be the maximum number of meetings that can be scheduled.

Test Cases

We can create several test cases to test the above code.

vector test1 = {{1, 3}, {2, 5}, {4, 6}}; // Expected result: 2
vector test2 = {{1, 10}, {2, 3}, {4, 5}, {6, 8}}; // Expected result: 3
vector test3 = {{1, 2}, {3, 4}, {5, 6}}; // Expected result: 3

You can execute each test case and compare it with the expected results
to verify if the code is functioning correctly.

Conclusion

In this tutorial, we learned how to solve the problem of assigning meeting rooms using C++.
We understood how the greedy algorithm provides an optimal solution and demonstrated that by considering
the start and end times of various meetings, we can schedule the maximum number of meetings.

I encourage you to understand and apply this algorithm to solve more complex problems.
Developing a habit of solving various algorithm problems will improve your coding skills.

C++ Coding Test Course, Finding the Minimum Number of Multiplications for Matrix Multiplication

Problem Description

There is a problem of finding the minimum number of operations required to multiply a given set of matrices.
If matrix A has a size of pq and matrix B has a size of qr, the number of operations required to multiply these two matrices is p * q * r.
We need to determine the order of matrix multiplication to minimize the total number of multiplication operations.

Problem Definition

Given n matrices with sizes as follows, find the minimum number of multiplication operations needed to multiply these matrices.

Input

The first line contains the number of matrices n (1 ≤ n ≤ 100).
The next n lines contain the size p_i × q_i of each matrix.

Output

Print the minimum number of operations required to multiply the matrices.

Example

Input:

Output:

Solution Process

1. Understanding the Basic Concept

Matrix multiplication is determined by the dimensions of the two matrices. Multiplying matrix A (p×q) and matrix B (q×r) results in matrix C (p×r).
The number of operations needed is p * q * r. If multiple matrices are provided, it is important to find the optimal multiplication order.

2. Utilizing Dynamic Programming

This problem can be solved using dynamic programming. We can construct a DP table to determine the optimal order of matrix multiplication.
Let dp[i][j] represent the minimum number of operations required to multiply from the ith matrix to the jth matrix.

3. Filling the DP Table

1. dp[i][i] = 0 (No operations are needed when multiplying a matrix with itself.)
2. When multiplying two or more matrices, divide the calculation based on the intermediate matrix.
3. The order of matrix multiplication is determined as follows.

for length from 2 to n:
    for i from 1 to n-length+1:
        j = i + length - 1
        dp[i][j] = ∞
        for k from i to j-1:
            cost = dp[i][k] + dp[k+1][j] + dimensions[i-1]*dimensions[k]*dimensions[j]
            dp[i][j] = min(dp[i][j], cost)

4. Python Implementation and C++ Code

Let’s implement the above algorithm in C++.

#include 
#include 
#include 

using namespace std;

int main() {
    int n;
    cin >> n;
    vector dimensions(n + 1);
    for (int i = 0; i < n; i++) {
        int p, q;
        cin >> p >> q;
        dimensions[i] = p;
        if (i == n - 1) dimensions[i + 1] = q; // last matrix's number of columns
    }

    vector> dp(n, vector(n, 0));

    for (int length = 2; length <= n; length++) {
        for (int i = 0; i < n - length + 1; i++) {
            int j = i + length - 1;
            dp[i][j] = INT_MAX;
            for (int k = i; k < j; k++) {
                int cost = dp[i][k] + dp[k + 1][j] + dimensions[i] * dimensions[k + 1] * dimensions[j + 1];
                dp[i][j] = min(dp[i][j], cost);
            }
        }
    }

    cout << dp[0][n - 1] << endl;
    return 0;
}

5. Time Complexity

The time complexity of this algorithm is O(n^3). This occurs because we need to consider all possible multiplication orders when there are n matrices.

6. Conclusion

The problem of minimizing matrix multiplication operations can be efficiently solved using dynamic programming.
This problem is very useful in developing algorithm problem-solving skills and is an important topic applicable in various fields.
By implementing this problem in C++, you can gain a deeper understanding of the concepts of algorithms and enhance your abilities to apply them in actual coding tests.

7. References

C++ Coding Test Course, Extended Euclidean Algorithm

Introduction

In modern development environments, various algorithms are necessary to solve numerous problems. Among them, algorithms that utilize mathematical techniques, particularly the “Extended Euclidean Algorithm,” are very useful tools. In this course, we will deeply explore the theory of the Extended Euclidean Algorithm and problems that frequently appear in coding tests. Through this content, you will systematically understand the Extended Euclidean Algorithm and develop the ability to solve practical problems using C++.

What is the Extended Euclidean Algorithm?

The Euclidean Algorithm is an algorithm for finding the greatest common divisor (GCD) of two integers a and b. The Extended Euclidean Algorithm goes a step further by finding integers x and y that express the GCD of a and b as a linear combination of a and b.

Mathematically, this can be expressed as follows:

gcd(a, b) = ax + by

Here, x and y are integers, and gcd(a, b) represents the greatest common divisor of a and b.

Necessity of the Extended Euclidean Algorithm

The Extended Euclidean Algorithm is mainly needed to solve problems such as:

Calculating modular multiplicative inverses
Solve linear Diophantine equations
Applications in cryptographic algorithms and hash algorithms

Problem Definition

Now, let’s define an algorithmic problem utilizing the Extended Euclidean Algorithm. The problem is as follows:

Given two integers a and b, find their greatest common divisor along with integers x and y that represent a and b as a linear combination.

For example, for a = 30 and b = 21, the greatest common divisor is 3, and it can be expressed as a linear combination of 30 and 21 as follows:

3 = 1 * 30 + (-1) * 21

Problem Solving Process

1. Algorithm Design

The basic idea of the Extended Euclidean Algorithm is to extend the Euclidean Algorithm to calculate the GCD along with the required x and y. The algorithm can be designed in the following manner:

Recursively call the function to calculate x and y values along with the GCD.
Set up the following relationship using the two numbers a and b:

gcd(a, b) = gcd(b, a % b)
As a base case, when b is 0, gcd(a, 0) = a and set x=1, y=0.
After the recursive call, update x and y to obtain the linear combination.

2. C++ Implementation

Here is the code implementing the above algorithm in C++:


#include <iostream>

using namespace std;

// Extended Euclidean Algorithm
int extended_gcd(int a, int b, int &x, int &y) {
    // Base case
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    
    int x1, y1; // Values after recursive call
    int gcd = extended_gcd(b, a % b, x1, y1);
    
    // Update x and y
    x = y1;
    y = x1 - (a / b) * y1;
    
    return gcd;
}

int main() {
    int a, b;
    int x, y;
    
    cout << "Enter two numbers (a b): ";
    cin >> a >> b;
    
    int gcd = extended_gcd(a, b, x, y);
    
    cout << "Greatest Common Divisor: " << gcd << endl;
    cout << "x: " << x <<, " y: " << y << endl;
    
    return 0;
}

3. Code Explanation

The above code implements the Extended Euclidean Algorithm to return the greatest common divisor along with x and y for the given two numbers a and b.

extended_gcd function: Takes two numbers and x, y as parameters and calculates the GCD along with x and y values.
main function: Receives input from the user for two numbers, calls the extended_gcd function, and outputs the results.

Test Cases

To test the implemented algorithm, let’s use several test cases. For example:

a	b	Greatest Common Divisor (GCD)	x	y
30	21	3	1	-1
48	18	6	1	-2
56	15	1	-2	7

Conclusion

In this course, we explored the theory of the Extended Euclidean Algorithm along with the problem-solving process using C++. The Extended Euclidean Algorithm is not only used for finding the greatest common divisor but is also widely applicable to solving various mathematical problems. Based on this fundamental theory, I hope you develop the ability to tackle more complex algorithmic problems.

C++ Coding Test Course, Calculating Average

Topic: Calculating the Average

In this lesson, we will cover the average calculation problem, which is frequently presented in coding tests. We will explain the definition of the problem and the solution step-by-step, and ultimately implement it in C++ code.

Problem Definition

Write a program to calculate the average of all elements in a given integer array. The length of the array is N, and all elements in the array are integers. The average value should be rounded to two decimal places, with the integer and decimal parts separated by a ‘.’.

Input Format:

The first line contains the length of the array N (1 ≤ N ≤ 1000).
The second line contains N integers in the array (each integer is between -10,000 and 10,000), separated by spaces.

Output Format:

Output the average value rounded to two decimal places.

Example

Input:
5
10 20 30 40 50

Output:
30.00

Problem Solving Method

The procedure to solve this problem is as follows:

Read N from the input to determine the length of the array.
When reading the integer array, sum each element.
Divide the sum by N to find the average.
Format the output to two decimal places.

C++ Code Implementation

Now, let’s write C++ code that follows the above procedure:


#include 
#include  // For std::setprecision
#include 

using namespace std;

int main() {
    int N;
    cout << "Enter the length of the array: ";
    cin >> N; // Input the length of the array

    vector arr(N); // Declare a vector of size N
    int sum = 0;

    cout << "Enter the elements of the array separated by spaces: ";
    for (int i = 0; i < N; ++i) {
        cin >> arr[i]; // Input array elements
        sum += arr[i]; // Sum the elements
    }

    double average = static_cast(sum) / N; // Calculate the average
    cout << "Average: " << fixed << setprecision(2) << average << endl; // Format to two decimal places

    return 0;
}

Code Explanation

#include <iostream>: This is a library for input and output in C++.
#include <iomanip>: This is a header file necessary for specifying output formats. It is used here to set the number of decimal places.
vector arr(N): This declares an integer array of size N using C++’s dynamic array, vector.
sum: This variable stores the sum of the inputted array elements.
cin >> arr[i]: This assigns the user-inputted value to each element of the array.
average: This calculates the average by dividing the total sum by N. It also casts this sum to double to maintain decimal places.
std::fixed & std::setprecision(2): This sets the formatting for outputting up to two decimal places.

Complexity Analysis

The time complexity of this problem is O(N). The computation time increases in proportion to the input size, as each element is visited only once to calculate the sum. The space complexity is also O(N), as it uses N spaces to store the input data.

Conclusion

In this lesson, we learned to calculate the average value and practiced basic input/output and vector usage in C++. It is important to systematically approach a problem by breaking it down into steps, and to anticipate and handle potential errors at each step, which is a good habit in coding tests. Continue to practice various problems to improve your algorithm skills!