Category: C++ Coding Test Tutorials

1. DFS (Depth First Search) Algorithm

DFS is one of the algorithms for traversing graphs, also known as depth-first search. It starts from a vertex of the graph and continues to explore deeper into adjacent vertices. When no further depth can be explored, it returns to the last visited vertex to explore other adjacent vertices.

1.1 Characteristics of DFS

• Can be easily implemented using a stack or recursion.
• Visits every vertex once, so the time complexity is O(V + E), where V is the number of vertices and E is the number of edges.
• Requires additional memory to store information about visited vertices during execution.

1.2 Implementation of DFS

                
#include <iostream>
#include <vector>
#include <stack>

using namespace std;

void DFS(int start, vector &visited, const vector> &adj) {
    stack s;
    s.push(start);

    while (!s.empty()) {
        int node = s.top();
        s.pop();

        if (!visited[node]) {
            visited[node] = true;
            cout << node << ' ';

            for (int i = adj[node].size() - 1; i >= 0; --i) {
                if (!visited[adj[node][i]]) {
                    s.push(adj[node][i]);
                }
            }
        }
    }
}
                
            

2. BFS (Breadth First Search) Algorithm

BFS is one of the algorithms for traversing graphs, also known as breadth-first search. It starts from a vertex of the graph and visits all adjacent vertices first before progressing deeper.

2.1 Characteristics of BFS

• Implemented using a queue.
• Visits every vertex once, so the time complexity is O(V + E).
• Suitable for finding the shortest path.

2.2 Implementation of BFS

                
#include <iostream>
#include <vector>
#include <queue>

using namespace std;

void BFS(int start, vector &visited, const vector> &adj) {
    queue q;
    visited[start] = true;
    q.push(start);

    while (!q.empty()) {
        int node = q.front();
        q.pop();
        cout << node << ' ';

        for (int i = 0; i < adj[node].size(); ++i) {
            if (!visited[adj[node][i]]) {
                visited[adj[node][i]] = true;
                q.push(adj[node][i]);
            }
        }
    }
}
                
            

3. Problem: Graph Traversal (Application of DFS and BFS)

Problem description: Write a program to count the number of connected components in a given disconnected graph. Given the vertices and edges of the graph, use DFS and BFS algorithms to explore the sets of connected vertices and calculate the number of connected components.

3.1 Input Format

The first line will contain the number of vertices N (1 <= N <= 1000) and the number of edges M (1 <= M <= 100,000). The following M lines will contain the edge information.

3.2 Output Format

Output the number of connected components.

3.3 Example

                
Input:
5 3
1 2
2 3
4 5

Output:
2
                
            

3.4 Solution Process

This problem can be solved by using both DFS and BFS algorithms to count the number of connected components.

1. Represent the graph in the form of an adjacency list.
2. Initialize a visited array to record visited vertices.
3. Iterate through each vertex; every time an unvisited vertex is found, use DFS or BFS to visit all vertices included with that vertex.
4. Increase the count every time a connected component is found and finally print the count.

3.5 C++ Code Example

                
#include <iostream>
#include <vector>
#include <stack>
#include <queue>

using namespace std;

void DFS(int start, vector &visited, const vector> &adj) {
    stack s;
    s.push(start);

    while (!s.empty()) {
        int node = s.top();
        s.pop();

        if (!visited[node]) {
            visited[node] = true;

            for (int i = 0; i < adj[node].size(); ++i) {
                if (!visited[adj[node][i]]) {
                    s.push(adj[node][i]);
                }
            }
        }
    }
}

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

    vector> adj(N + 1);
    vector visited(N + 1, false);

    for (int i = 0; i < M; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u); // Add in both directions for undirected graph.
    }

    int componentCount = 0;

    for (int i = 1; i <= N; i++) {
        if (!visited[i]) {
            DFS(i, visited, adj);
            componentCount++;
        }
    }

    cout << componentCount << endl;
    
    return 0;
}
                
            

Problem Description

DDR stands for Dance Dance Revolution, where players move their feet to the arrows appearing on the screen while dancing.
In this data structure and algorithm problem, we need to simulate specific situations that may occur in DDR and
write a program to calculate the appropriate movements based on the given arrow pattern.

Problem: The given string represents an arrow pattern. Each element of the array indicates the direction of an arrow,
where ‘U’ means up, ‘D’ means down, ‘L’ means left, and ‘R’ means right.
The player must process at least K arrows while ignoring duplicate arrows.
Write a program that returns the number of distinct directions the player has moved.

Input: A string and an integer K (1 ≤ K ≤ 1000)

Output: The number of distinct directions the player has moved.

Problem Analysis

To understand the given problem clearly, we need to know exactly what direction each arrow points to.
We should not consider duplicate arrows, so we need a data structure that can keep the original order of elements while processing the string and removes duplicates.
Since the number of arrows is finite and consists only of uppercase ‘U’, ‘D’, ‘L’, ‘R’, this problem can be solved with simple string processing.

Approach

To approach the problem, we can consider the following steps:

1. Traverse the given string to check each arrow.
2. Add each arrow to a Set to automatically remove duplicate arrows.
3. Check the size of the Set to calculate the number of distinct directions the player has actually moved.

This approach has a time complexity of O(n), where n is the length of the given string.
Using a Set makes it easy to handle duplicates, and obtaining the final size of the Set is O(1).

C++ Code Implementation

#include 
#include 
#include 

int processArrows(const std::string &arrows, int K) {
    std::unordered_set uniqueArrows;
  
    // Traverse each arrow and add to the Set
    for (char arrow : arrows) {
        uniqueArrows.insert(arrow);
    }
  
    // Return the size of the Set regardless of whether it is less than K
    return uniqueArrows.size();
}

int main() {
    std::string arrows;
    int K;

    std::cout << "Enter the arrow pattern: ";
    std::getline(std::cin, arrows);
    std::cout << "Enter the value of K: ";
    std::cin >> K;

    int result = processArrows(arrows, K);
    std::cout << "Number of distinct directions the player has moved: " << result << std::endl;

    return 0;
}
            

Code Explanation

The above C++ code performs a simple simulation to solve the problem.
The processArrows function takes a String and K as arguments and handles the arrows.
Here, we use unordered_set to automatically remove duplicates.

First, we traverse the given arrow string character by character and add each arrow to the Set.
Since the Set does not allow duplicate elements, we can determine the number of distinct directions the player has
actually moved by checking the final size of the Set.

The main function takes the arrow pattern and K value as input from the user,
passes these values to the processArrows function, and finally prints the result.

Conclusion

In this post, we explained the process of solving a simple algorithm problem related to the DDR game using C++.
We analyzed the problem step-by-step, discussed the approach, and ultimately
solved the problem through effective code implementation.
This approach is very useful for solving various algorithm problems that need to be addressed in coding tests.

Problem Description

The 2*N tile filling problem is to find the number of ways to fill a given 2xN space with 1×2 tiles.
Tiles can be placed either horizontally or vertically, and the entire 2xN space must be completely filled.
The key to this problem is calculating the number of combinations, which can be solved using Dynamic Programming techniques.

Input Format

An integer N is given. (1 ≤ N ≤ 30)

Output Format

Output the number of ways to fill the 2xN space as an integer.

Problem Solving Process

To solve the 2*N tile filling problem, we need to find the pattern of the problem through several examples.
First, let’s consider the cases when N is 1 and when N is 2.

Example

• N = 1:
  • 1 way: Place 1 tile vertically
• N = 2:
  • 2 ways: Place 2 tiles horizontally or place 2 tiles vertically

Here, we can discover the following pattern.
As N increases, each case can be divided as follows.

– If we place a tile horizontally in the Nth position, N-1 positions remain.
– If we place a tile vertically in the Nth position, N-2 positions remain.

Therefore, the recurrence relation can be expressed as:

                dp[n] = dp[n-1] + dp[n-2]
            

When setting this recurrence relation, we need to establish initial values.
dp[1] = 1 (1×2 tile placed vertically), dp[2] = 2 (either 2 horizontal tiles or 2 vertical tiles) is established.

Now, let’s write a C++ program to calculate the number of ways based on this recurrence relation by taking N as input.

C++ Code Implementation

                
                #include 
                using namespace std;

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

                    int dp[31] = {0};
                    dp[1] = 1;
                    dp[2] = 2;

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

                    cout << dp[N] << endl;
                    return 0;
                }
                
            

The code above creates a dp array for the given N and uses dynamic programming techniques to calculate the number of ways for each case.
Finally, it outputs dp[N] to determine the number of ways to fill the 2xN space with tiles.

Time Complexity

The time complexity of this algorithm is O(N).
This is because the for loop runs N times.
The space complexity is also O(N) due to the use of the dp array.

Conclusion

The 2*N tile filling problem is a typical example of dynamic programming.
The key is to break the problem down into smaller parts to create a recurrence relation that can be solved recursively.
As this problem is frequently encountered in coding tests, it is important to understand and practice it repeatedly.