C++ Coding Test Tutorials 보관 - Page 9 of 28

C++ Coding Test Course, Implementing Absolute Value Heap

In this lecture, we will address an algorithm problem that involves implementing an absolute value heap. This problem is one of the frequently asked types in C++ programming and can be solved using a priority queue. An absolute value heap is a data structure that sorts based on the absolute value of a specific number.

Problem Description

An absolute value heap supports the following operations:

Insert an integer x into the heap.
Remove and return the integer with the smallest absolute value from the heap. If there are multiple numbers with the same absolute value, the smaller value is returned. If the heap is empty, return 0.

Input

The first line contains the number of operations N (1 ≤ N ≤ 100,000). The next N lines contain the operations to be performed. The operations are divided into two types:

Insert: 0 x (−10⁹ ≤ x ≤ 10⁹) format, which inserts x into the absolute value heap.
Delete: specified with 0, removes and returns the integer with the smallest absolute value from the absolute value heap.

Output

Print the results of the delete operations, one per line.

Example Input

Example Output

Approach to the Problem

To solve this problem, we will use a priority queue. The C++ standard library provides std::priority_queue, which operates as a max heap by default. However, we need to create a min heap based on absolute values. Therefore, we will customize std::priority_queue to implement this.

Heap Implementation

To implement the absolute value heap, we will define the following comparison function:

struct Compare {
    bool operator()(int a, int b) {
        if (abs(a) == abs(b)) {
            return a > b; // Choose the smaller value if the absolute values are the same
        }
        return abs(a) > abs(b); // Choose based on absolute value
    }
};

Based on the above comparison function, we can define the priority queue and perform insert and delete operations.

C++ Code Implementation

#include 
#include 
#include 
#include 

using namespace std;

// Define comparison operator
struct Compare {
    bool operator()(int a, int b) {
        if (abs(a) == abs(b)) {
            return a > b; // Choose the smaller value if the absolute values are the same
        }
        return abs(a) > abs(b); // Choose based on absolute value
    }
};

int main() {
    int N;
    cin >> N;

    priority_queue, Compare> pq; // Customized priority queue
    
    for (int i = 0; i < N; i++) {
        int x;
        cin >> x;
        if (x == 0) {
            // Delete operation
            if (pq.empty()) {
                cout << 0 << endl; // Print 0 if empty
            } else {
                cout << pq.top() << endl; // Print the smallest value from the absolute value heap
                pq.pop(); // Delete from the heap
            }
        } else {
            // Insert operation
            pq.push(x); // Add value to the heap
        }
    }

    return 0;
}

Code Explanation

The above C++ code implements the absolute value heap:

It uses the Compare structure to set the priority within the priority_queue.
Within the main function, it reads input, deletes data from the heap when receiving 0, and inserts other numbers into the heap.

Time Complexity Analysis

The time complexity of this algorithm is as follows:

Insert operation: O(log N)
Delete operation: O(log N)

Therefore, for N operations, the overall time complexity is O(N log N).

Conclusion

In this lecture, we learned how to implement an absolute value heap in C++, and how to efficiently manage data using a priority queue. This problem is one of the important concepts in coding tests, so I hope you will deepen your understanding through practice.

C++ Coding Test Course, Finding the Critical Path

Hello. In this lecture, we will discuss “Finding the Critical Path,” which is one of the algorithm problems frequently asked in C++ coding tests. This problem helps in understanding important concepts related to graph theory.

Problem Definition

In the given directed graph, each vertex has a specific time to perform a task. The critical path refers to the total task time of the longest path among all paths that visit all vertices, from the starting vertex to the destination vertex.

Problem Description

Given the number of vertices n and the number of edges m, the task time for each vertex i is given as t[i]. The problem is to find the maximum task time of a path that satisfies the following conditions.

Input:
n, m
t[0], t[1], ..., t[n-1]
Edges: (u1, v1), (u2, v2), ..., (um, vm)
Output:
Maximum task time

Example Input

Example Output

Problem-Solving Strategy

1. Graph Representation

First, we construct the graph in the form of an adjacency list based on the given information. This allows us to easily manage movements to connected vertices from each vertex.

2. Finding the Longest Path

We can use DFS (Depth-First Search) or the properties of a DAG (Directed Acyclic Graph) to find the longest path. As we visit each vertex, we keep track of the maximum task time of the longest path.

3. Utilizing Dynamic Programming (DP)

In particular, the problem of finding the critical path can be efficiently solved using dynamic programming. We accumulate and record the maximum of all reachable paths for each vertex.

C++ Code Implementation

#include 
#include 
#include 
using namespace std;

vector timeTaken; // Task time for each vertex
vector> graph; // Graph adjacency list
vector dp; // DP array

int dfs(int node) {
    if (dp[node] != -1) return dp[node];
    int maxTime = 0;
    for (int next : graph[node]) {
        maxTime = max(maxTime, dfs(next));
    }
    dp[node] = maxTime + timeTaken[node];
    return dp[node];
}

int main() {
    int n, m;
    cin >> n >> m;
    
    timeTaken.resize(n);
    graph.resize(n);
    dp.assign(n, -1);
    
    for (int i = 0; i < n; i++) {
        cin >> timeTaken[i];
    }
    
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        graph[u].push_back(v);
    }

    int result = 0;
    for (int i = 0; i < n; i++) {
        result = max(result, dfs(i));
    }

    cout << result << endl;
    return 0;
}

Code Explanation

The above code explores the graph in a DFS manner to calculate the maximum task time of the critical path. The main elements are as follows:

Graph Creation: The graph is constructed in the form of an adjacency list through the input edges.
DFS Function: Starting from each vertex, it recursively explores the connected vertices and computes the time of the longest path.
DP Array: A DP array is utilized to apply memoization techniques to avoid revisiting the same vertex multiple times.

Time Complexity

The time complexity of this algorithm is O(n + m). Here, n is the number of vertices, and m is the number of edges. In the worst case, since all vertices must be visited once, this level of complexity is generally efficient.

Conclusion

In this lecture, we learned how to solve the critical path problem using C++. Through the concepts of graph theory, dynamic programming, and DFS, we can address this type of problem. I hope you will practice various algorithm problems to improve your programming skills further.

C++ Coding Test Course, Finding Binomial Coefficient 2

Hello! In this lecture, we will delve deeper into the concept of Binomial Coefficient. The binomial coefficient is an important concept in combinatorics and represents the number of ways to choose k elements from a given set of n elements. The problem we will address in this lecture is known as the “nCr” or “binomial coefficient” problem, and we will explore efficient implementation methods.

Problem Description

The problem is as follows:

Given integers n and k, output the binomial coefficient C(n, k). (Note: 0 ≤ k ≤ n ≤ 1000)

Definition of Binomial Coefficient

The binomial coefficient C(n, k) is defined as:

C(n, k) = n! / (k! * (n - k)!)

Here, n! denotes n factorial, meaning the product of n × (n-1) × … × 1. According to this definition, calculating the binomial coefficient requires computing factorials. However, when n is 1000, n! becomes a very large number, so an efficient method is needed rather than directly calculating it.

Calculating Binomial Coefficient Using Dynamic Programming

One of the more efficient methods for calculating the binomial coefficient is to use dynamic programming. In this process, we will look at how to efficiently compute the binomial coefficient.

Recurrence Relation

C(n, k) can also be expressed using the following recurrence relation:

C(n, k) = C(n-1, k-1) + C(n-1, k) (Note: k > 0)
C(n, 0) = 1 (when k is 0)
C(n, n) = 1 (when k is n)

Based on this recurrence relation, the binomial coefficient can be calculated recursively, but this approach can lead to redundant calculations making it inefficient. Therefore, we will use memoization or dynamic programming techniques for the computation.

Code Implementation

Below is a dynamic programming code written in C++ to compute the binomial coefficient:


#include 
#include 

using namespace std;

long long binomialCoefficient(int n, int k) {
    vector> C(n + 1, vector(k + 1, 0));
  
    // C(n, 0) = 1
    for (int i = 0; i <= n; i++) {
        C[i][0] = 1;
    }
  
    // C(n, k) = C(n - 1, k - 1) + C(n - 1, k)
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= min(i, k); j++) {
            C[i][j] = C[i - 1][j - 1] + C[i - 1][j];
        }
    }
  
    return C[n][k];
}

int main() {
    int n, k;
    cout << "Enter n and k: ";
    cin >> n >> k;
    cout << "C(" << n << ", " << k << ") = " << binomialCoefficient(n, k) << endl;
    return 0;
}

Code Explanation

1. vector> C(n + 1, vector(k + 1, 0));: Declares and initializes a 2D vector to store the binomial coefficients.

2. C[i][0] = 1;: Initializes the first column using the fact that the binomial coefficient is always 1 when n is 0.

3. Fills the 2D vector C by calculating each value according to the rules.

4. Finally, it returns C[n][k] to output the result.

Example Execution

Now, let's run the code above:

Enter n and k: 5 2
C(5, 2) = 10

In the example above, when n = 5 and k = 2, the value of C(5, 2) was correctly calculated as 10.

Time Complexity Analysis

Since the binomial coefficient is derived using dynamic programming in the above code, the time complexity is O(n * k). In the worst case where n = 1000, this complexity is manageable. The space complexity is O(n * k), representing the space required to store the C vector.

Conclusion

In this lecture, we effectively calculated the binomial coefficient using dynamic programming. Understanding and practicing the binomial coefficient is essential as it is an important concept in various fields such as combinatorics and probability theory. Practice with various test cases to enhance your ability to solve problems dynamically.

I hope this lecture was helpful, and I look forward to seeing you in the next lecture!

C++ Coding Test Course, Finding Binomial Coefficient 1

Hello! In this post, we will discuss the algorithm problem “Calculating Binomial Coefficient,” which frequently appears in C++ coding tests. This problem is closely related to combinations and requires both mathematical foundation and coding ability. Additionally, understanding various solutions and the algorithms involved will greatly assist in preparing for job interviews.

Problem Definition

The binomial coefficient we seek is defined by the following formula for given integers n and k:

C(n, k) = n! / (k! * (n-k)!)

Here, n! denotes the factorial of n. The task is to compute the binomial coefficient C(n, k) given n and k. For instance, when n=5 and k=2, C(5, 2) is 10.

Input and Output of the Problem

The input for the problem consists of two integers n and k, while the output is the value of C(n, k).

Input Format

First line: two integers n (0 ≤ n ≤ 30) and k (0 ≤ k ≤ n)

Output Format

Output the value of C(n, k) on one line

Solution Process

Now, let’s examine the step-by-step approach to solve the problem. We can essentially use three approaches.

1. Recursive Approach

The binomial coefficient can be defined recursively. In other words, we can use the following recurrence relation:

C(n, k) = C(n-1, k-1) + C(n-1, k)

The base cases are C(n, 0) = 1 (for all n) and C(n, n) = 1 (for all n). Given the parameters n and k, we can recursively calculate the binomial coefficient using this recurrence. However, this approach is inefficient due to a lot of redundant computations.

Example of Recursive Implementation


#include 
using namespace std;

// Recursive function to find the binomial coefficient C(n, k)
int binomialCoefficient(int n, int k) {
    // Base cases
    if (k == 0 || k == n) return 1;
    // Recursive call
    return binomialCoefficient(n - 1, k - 1) + binomialCoefficient(n - 1, k);
}

int main() {
    int n, k;
    cout << "Enter n and k: ";
    cin >> n >> k;
    cout << "C(" << n << ", " << k << ") = " << binomialCoefficient(n, k) << endl;
    return 0;
}

2. Dynamic Programming

The recursive approach has a time complexity of O(2^n), which is inefficient. To improve this, we can use dynamic programming. This method avoids redundant calculations by storing already computed values through techniques like memoization or tabulation to enhance efficiency.

Example of Dynamic Programming Implementation


#include 
using namespace std;

// Function to calculate binomial coefficient using DP
int binomialCoefficientDP(int n, int k) {
    int C[n + 1][k + 1];

    // Calculate the binomial coefficient using a bottom-up approach
    for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= min(i, k); j++) {
            if (j == 0 || j == i)
                C[i][j] = 1;
            else
                C[i][j] = C[i - 1][j - 1] + C[i - 1][j];
        }
    }
    return C[n][k];
}

int main() {
    int n, k;
    cout << "Enter n and k: ";
    cin >> n >> k;
    cout << "C(" << n << ", " << k << ") = " << binomialCoefficientDP(n, k) << endl;
    return 0;
}

3. Factorial Method

The final method involves calculating the binomial coefficient directly using factorials. This approach calculates C(n, k) by implementing the mathematical formula directly.

Example of Factorial Implementation


#include 
using namespace std;

// Function to return the factorial of a number
int factorial(int n) {
    if (n == 0) return 1;
    return n * factorial(n - 1);
}

// Function to calculate the binomial coefficient
int binomialCoefficientFactorial(int n, int k) {
    return factorial(n) / (factorial(k) * factorial(n - k));
}

int main() {
    int n, k;
    cout << "Enter n and k: ";
    cin >> n >> k;
    cout << "C(" << n << ", " << k << ") = " << binomialCoefficientFactorial(n, k) << endl;
    return 0;
}

Comparison and Optimization

The time complexities of the three methods are as follows:

Recursive Approach: O(2^n)
Dynamic Programming: O(n * k)
Factorial Calculation: O(n)

Thus, when n and k are small, using factorials is simple and fast, but as n and k grow, dynamic programming becomes more efficient. It's important to note that the factorial approach can lead to overflow for large values of n.

Conclusion

In this post, we have explored the problem of calculating the binomial coefficient. There are various methods to solve this problem, and it is crucial to choose an appropriate method by considering the advantages and disadvantages of each. Understanding algorithms is beneficial not only for coding tests but also for actual development.

In the next post, we will cover more complex problems utilizing the binomial coefficient, so stay tuned!

In summary, the binomial coefficient problem is a good example of the integration of mathematics and algorithms, remaining an important topic not only for job preparation but also for algorithm studies. I hope you gain experience by solving various problems.

Thank you for reading!

C++ Coding Test Course, Finding Incomplete Numbers

This article will explain how to find binary friends (binary numbers without consecutive 1s) using C++. This problem will serve as a good practice to enhance algorithm problem-solving skills.

Problem Description

A binary friend refers to a binary number composed of 0s and 1s that does not have consecutive 1s. For example, 0, 1, 10, 100, 101 are binary friends. However, 11, 111, and 1100 are not. The problem is to find how many binary friends of n digits exist for a given natural number n.

Input

The first line contains a natural number n (1 ≤ n ≤ 45).

Output

Output the count of binary friends with n digits.

Approach and Solution Method

To solve this problem, we will utilize the properties of the Fibonacci sequence. The ways to create a binary friend can be divided as follows:

If the leftmost bit of the n-digit binary friend is 0, the remaining bits become (n-1)-digit binary friends.
If the leftmost bit of the n-digit binary friend is 1, the next bit must be 0, thus the remaining bits will become (n-2)-digit binary friends.

Therefore, the count of binary friends can be defined as follows:

f(n) = f(n-1) + f(n-2)

Here, f(n) represents the count of n-digit binary friends. The initial values can be set as follows:

f(1) = 2 (0, 1)
f(2) = 3 (00, 01, 10)

Thus, to find n binary friends, we can utilize the method of calculating the Fibonacci sequence. Now, let’s implement the actual code in C++.

Code Implementation


#include <iostream>

using namespace std;

long long findBinaryFriend(int n) {
    long long *dp = new long long[n + 1];
    dp[1] = 2; // 1-digit binary friend
    dp[2] = 3; // 2-digit binary friend

    for (int i = 3; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }

    return dp[n];
}

int main() {
    int n;
    cout << "Enter a natural number n (1≤n≤45): ";
    cin >> n;

    if (n >= 1 && n <= 45) {
        cout << n << " digit binary friend's count is: " << findBinaryFriend(n) << "." << endl;
    } else {
        cout << "Invalid input." << endl;
    }

    return 0;
}

Code Explanation

The above code is a program that calculates the count of n-digit binary friends for a given n. First, it creates a dynamic array and allocates memory setting the initial values. Then, it proceeds from 3 to n, finding the binary friends for each digit by summing the previous two terms.

Finally, in the main function, it takes input from the user for n and, under the appropriate conditions, outputs the count of binary friends. Do not forget to free the allocated array for memory management in any case.

Testing and Validation

It is important to test the code after writing it. Check the results for the following input values:

n = 1: Result is 2 (0, 1)
n = 2: Result is 3 (00, 01, 10)
n = 3: Result is 5 (000, 001, 010, 100, 101)
n = 4: Result is 8
n = 5: Result is 13

You should confirm that the correct results are output for such inputs. It is advisable to verify by manually counting binary friends for each n value.

Conclusion

In this class, we learned how to solve the binary friend problem using C++. This problem is a good example of the Fibonacci sequence and dynamic programming. You can develop your algorithm problem-solving skills through this problem, so practice with various input values.