Category: C++ Coding Test Tutorials

In this lecture, we will explain how to calculate the area of a polygon using C++. The algorithm problem is given as follows.

Problem Description

Calculate the area of the polygon formed by the given points. The vertices of the polygon are provided in either clockwise or counterclockwise order, and the coordinates of the points are integers. The area of the polygon can be calculated using the following formula:

Area = (1/2) * | Σ (x_i * y_i+1 – x_i+1 * y_i) |

Here, (x_i, y_i) are the coordinates of the ith vertex of the polygon, and (x_n, y_n) is the last vertex of the polygon. The number of vertices of the polygon is 3 or more.

Input

• The first line contains the number of vertices N of the polygon (3 ≤ N ≤ 10⁵).
• The next N lines contain the x and y coordinates of each vertex as integers. (-10⁹ ≤ x, y ≤ 10⁹)

Output

Print the area of the polygon rounded to two decimal places.

Example Input

4
0 0
4 0
4 3
0 4

Example Output

12.00

Algorithm for Problem Solving

The algorithm for calculating the area of a polygon proceeds as follows.

1. Receive the input and store the coordinates.
2. Calculate the area of the polygon using the area formula.
3. Round the calculated area to two decimal places and output it.

1. Input Reception

First, the user must enter the number of vertices of the polygon and their coordinates. For this, we will use a vector to store the coordinates.

2. Area Calculation

To calculate the area according to the given formula, we will iterate through the given points and perform the calculations.

3. Formatting the Output

Since the output must be displayed to two decimal places, we can use C++’s iomanip header’s setprecision and fixed to format the output.

C++ Code Example

#include 
#include 
#include 

using namespace std;

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

    vector> points(N);
    for (int i = 0; i < N; i++) {
        cin >> points[i].first >> points[i].second;
    }

    double area = 0;
    for (int i = 0; i < N; i++) {
        int j = (i + 1) % N;  // Next point, the last point connects to the first point
        area += points[i].first * points[j].second;
        area -= points[j].first * points[i].second;
    }

    area = abs(area) / 2.0; // Take the absolute value and divide by 2.

    cout << fixed << setprecision(2) << area << endl;

    return 0;
}

Code Explanation

The above code performs the following steps to calculate the area of the polygon:

• Input Reception: First, it receives the number of vertices N and the coordinates of each vertex. To store the coordinates, vector> is used.
• Area Calculation: It calculates the area using the given area formula. The vertex indices are managed with i and j, and it implements the connection from the last point back to the first point.
• Output: It utilizes fixed and setprecision to print the calculated area to two decimal places.

Time Complexity

The time complexity of the above algorithm is O(N). This is because it visits each vertex once to calculate the area. Therefore, it executes quickly even when N is up to 10⁵.

Conclusion

Through this lecture, you learned how to efficiently calculate the area of a polygon using C++. This will greatly help in developing your algorithm problem-solving skills. Please practice with more diverse problems in the future!

Hello everyone! Today, I will explain the Breadth-First Search (BFS) algorithm, which often appears in coding tests. In this lecture, we will explore the fundamental concepts of BFS and solve a sample algorithm problem using it.

What is BFS?

Breadth-First Search (BFS) is one of the algorithms used to explore nodes in graph theory. BFS starts from one node, explores all adjacent nodes, and then explores adjacent nodes in the next step. This allows us to solve shortest path problems or calculate the shortest distance.

Characteristics of BFS

• Uses Queue data structure: BFS employs a queue data structure to store nodes to be explored.
• Guarantees shortest path: BFS guarantees the shortest path in graphs with uniform weights.
• Levels are explored in order: BFS explores each level sequentially, so it searches from nearby nodes to distant nodes.

Problem Description

Now let’s look at a simple problem utilizing BFS.

Problem: 01-Calculating Shortest Distance Using Breadth-First Search

Write a program that calculates the shortest distance from a specific starting node to all other nodes in a given undirected graph. The input includes the number of nodes in the graph, the number of edges, and the two nodes of each edge.

Input Format

The first line contains the number of nodes N (1 ≤ N ≤ 10^5) and the number of edges M (1 ≤ M ≤ 2 * 10^5).
The next M lines represent the two nodes u, v (1 ≤ u, v ≤ N) of each edge.
The last line gives the starting node S.

Output Format

Output the shortest distance to each node, separated by spaces.
If a node is not connected, output -1.

Solution Process

Let’s take a step-by-step look at how to solve the problem using BFS.

Step 1: Graph Representation

We will use an adjacency list to represent the graph. The adjacency list stores the other nodes connected to each node in a list format. This allows efficient memory usage.

Step 2: Implementing BFS

BFS explores adjacent nodes using a queue. The exploration order is as follows:

1. Insert the starting node into the queue and initialize the distance to 0.
2. Remove a node from the queue and check all nodes adjacent to that node.
3. If the explored node is unvisited, set its distance to the current node’s distance + 1 and insert it into the queue.
4. Repeat this process until the queue is empty.

Step 3: Writing the Code

Now, based on the above process, let’s write the C++ code.

#include 
#include 
#include 
#include 

using namespace std;

const int MAX_N = 100000;
vector graph[MAX_N + 1];
int dist[MAX_N + 1];

void bfs(int start, int n) {
    queue q;
    fill(dist, dist + n + 1, -1);  // Initialize distances
    dist[start] = 0;                // Set distance for the start node
    q.push(start);                   // Insert start node into the queue

    while(!q.empty()) {
        int current = q.front();
        q.pop();
        
        for(int neighbor : graph[current]) {
            if(dist[neighbor] == -1) { // Unvisited node
                dist[neighbor] = dist[current] + 1;
                q.push(neighbor);
            }
        }
    }
}

int main() {
    int N, M, S;
    cin >> N >> M;
    
    for(int i = 0; i < M; ++i) {
        int u, v;
        cin >> u >> v;
        graph[u].push_back(v);         // Add undirected edge
        graph[v].push_back(u);
    }
    cin >> S;

    bfs(S, N); // Call BFS

    for(int i = 1; i <= N; ++i) {
        cout << dist[i] << " ";       // Output distances
    }
    cout << endl;

    return 0;
}

Step 4: Executing the Code and Results

By executing the above code, we calculate and output the shortest distance from the starting node S to each node. For example, if the following input is given:

Input Example:

6 7
1 2
1 3
2 4
3 4
4 5
4 6
5 6
1

Output Example:

0 1 1 2 3 2 

Step 5: Conclusion

In this lecture, we explored the Breadth-First Search (BFS) algorithm, which often appears in C++ coding tests. BFS is useful for solving shortest path problems and can be applied to various challenges. By thoroughly understanding and utilizing this algorithm, you can achieve good results in coding tests.

I hope this lecture has been helpful for your job preparation. Thank you!

Problem Description

This is a problem of creating a new integer by sorting the digits of a given integer in descending order.
For example, if the given integer is 4213, the result after sorting the digits in descending order is 4321.
This type of problem is commonly encountered in C++ coding tests, and it tests the ability to solve problems based on an understanding of sorting algorithms.

Problem Input

An integer N (0 ≤ N ≤ 2,147,483,647) is given in the first line.

Problem Output

Output a new integer by sorting the digits of integer N in descending order.

Input Example

4213

Output Example

4321

Solution Process

To solve this problem, several steps must be followed.
The main steps are as follows.

1. Input

First, we need to receive an integer input.
In C++, we can use cin to take input from the user.
The received integer will later be converted to a character type for the purpose of separating the digits.

2. Digit Separation

After converting the input integer to a character array, we can separate each digit individually.
In C++, the to_string function can be used to convert an integer to a string.
Each character of the converted string can be stored in a vector.

3. Descending Sort

After separating the digits, they need to be sorted in descending order.
The sort function in C++ can be used, and a comparison function can be applied to perform the descending sort.
Specifically, since the digits are sorted as characters, the ASCII values of the numbers must be considered during sorting.

4. Integer Conversion

After sorting the digits, convert them back to a string and then to an integer to obtain the final result.
Finally, use cout to display the result.

Code Example

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>

using namespace std;

int main() {
    // 1. Input
    int N;
    cin >> N;

    // 2. Digit Separation
    string str = to_string(N);
    vector digits(str.begin(), str.end());

    // 3. Descending Sort
    sort(digits.begin(), digits.end(), greater());

    // 4. Integer Conversion
    string sorted_str(digits.begin(), digits.end());
    int result = stoi(sorted_str);

    // Output result
    cout << result << endl;

    return 0;
}
    

Result

When the above code is executed, you can see the result of sorting the digits of the input integer in descending order.
For example, when 4213 is inputted, the output will show 4321.

Exception Handling

To solve this problem, exceptional situations must also be considered.
For instance, if the input value is 0, the output should also be 0.
Therefore, when writing the code, handling these exceptional situations should also be added.

Exception Handling Code Example

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>

using namespace std;

int main() {
    // 1. Input
    int N;
    cin >> N;

    // 0 Exception Handling
    if (N == 0) {
        cout << 0 << endl;
        return 0;
    }

    // 2. Digit Separation
    string str = to_string(N);
    vector digits(str.begin(), str.end());

    // 3. Descending Sort
    sort(digits.begin(), digits.end(), greater());

    // 4. Integer Conversion
    string sorted_str(digits.begin(), digits.end());
    int result = stoi(sorted_str);

    // Output result
    cout << result << endl;

    return 0;
}
    

Conclusion

In this lesson, we learned how to solve an algorithm problem that involves sorting digits in descending order.
We were able to solve the problem by using basic input/output and data structures in C++.
Problems of this type greatly aid in developing basic algorithmic skills.
Similar logic can be applied to other problems, so I hope you will practice by solving a variety of problems to improve your skills.

1. Problem Description

The given problem is as follows:

Implement an algorithm to find the size of the largest group of consecutive 1s in a two-dimensional array (N x M) composed of integers. A group is defined as a subset of 1s that are connected vertically or horizontally. Additionally, non-consecutive 1s are treated as different groups.

The size of the array (N, M) is between 1 and 100.

2. Problem Analysis

This problem is about using graph search algorithms like DFS (Depth-First Search) or BFS (Breadth-First Search) to find connected components. It can be solved by counting the number of connected 1s and keeping track of the maximum size of the group.

The input array can be represented in the following form:

    1 0 0 1 1
    1 1 0 0 0
    0 0 1 1 1
    0 1 0 0 0
    1 1 1 0 0
    

In this case, the size of the largest group will be 5.

3. Approach

We need to use depth-first search to find and count connected 1s. DFS is stack-based and can be implemented either recursively or explicitly with a stack. The following are the steps to solve the problem:

1. Iterate through the two-dimensional array and execute DFS when a 1 is found.
2. In DFS, explore connected 1s by moving vertically and horizontally and increase the count.
3. After exploring, compare and update the maximum group size.
4. Once the exploration is complete, return the final maximum group size.

4. Code Implementation

Below is the C++ code implementing the above approach:

#include 
#include 
#include 

using namespace std;

class Solution {
public:
    int N, M; // Size of the array
    vector> directions{{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; // Directions for up, down, left, right

    // Implementation of DFS
    int dfs(int x, int y, vector>& grid) {
        if (x < 0 || x >= N || y < 0 || y >= M || grid[x][y] == 0) {
            return 0; // Out of bounds or 0 case
        }

        grid[x][y] = 0; // Mark as visited
        int count = 1; // Count current 1

        // Recursive calls in four directions
        for (const auto& dir : directions) {
            count += dfs(x + dir[0], y + dir[1], grid);
        }

        return count;
    }

    int largestGroupSize(vector>& grid) {
        N = grid.size();
        M = grid[0].size();
        int maxSize = 0;

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (grid[i][j] == 1) { // When 1 is found
                    int groupSize = dfs(i, j, grid); // Call DFS
                    maxSize = max(maxSize, groupSize); // Update maximum group size
                }
            }
        }

        return maxSize;
    }
};

int main() {
    Solution sol;
    vector> grid = {
        {1, 0, 0, 1, 1},
        {1, 1, 0, 0, 0},
        {0, 0, 1, 1, 1},
        {0, 1, 0, 0, 0},
        {1, 1, 1, 0, 0}
    };

    int result = sol.largestGroupSize(grid);
    cout << "Size of the largest group: " << result << endl;
    return 0;
}

5. Code Explanation

The above C++ code is structured as follows:

1. Variable declaration: N and M store the size of the array, and directions defines movement directions for up, down, left, and right.
2. DFS function: The dfs function recursively counts the number of connected 1s starting from the current position. It checks for boundary conditions and visit status.
3. Main function: The largestGroupSize function iterates through the entire array, calling DFS every time a 1 is found to calculate the group size. It updates the maximum size and returns the final result.

6. Testing and Results

The above code can be tested with various cases. For example, we can change the size of groups or add new group structures to observe different results.

A successful result would be:

Size of the largest group: 5

7. Time Complexity Analysis

This algorithm has a time complexity of O(N * M) because each cell is visited once. The memory complexity is also O(N * M) due to the array and the recursive call stack.

8. Conclusion

In this lecture, we solved the problem of finding the maximum group size of connected 1s using depth-first search. DFS is a very useful algorithm for pathfinding problems and connected component identification, and it can be utilized in many algorithmic problems.

Next, we will discuss BFS and tackle various application problems. Thank you!