Category: Python Coding Test

Hello! In this post, we will explore the Union-Find algorithm and solve algorithmic problems using it. The Union-Find is a very useful data structure for managing disjoint sets, providing the ability to quickly determine the connectivity of multiple items and to merge sets.

What is Union-Find?

Union-Find consists of two main functions:

• Union: An operation that merges the sets containing two elements
• Find: An operation that finds which set a specific element belongs to

Through these two operations, we can easily manage the relationships between various elements and efficiently solve complex connectivity problems. It is particularly useful in graph problems and network connectivity issues.

How Union-Find Works

Union-Find mainly maximizes efficiency using two techniques:

1. Path Compression

When performing a Find operation, the path is compressed to reduce the height of the tree. This decreases the time complexity when performing multiple Find operations.

2. Union by Rank

While performing the Union operation, we consider the ‘rank’ (height) of the sets, attaching the lower rank set to the higher rank set. This method also reduces the depth of the trees, enhancing operational efficiency.

Problem: Counting the Number of Connected Components

Consider the following problem:

Given n nodes and m edges, find the number of connected components of nodes. The nodes are represented by integers from 0 to n-1, and edge information is given in the form of (a, b).

Input Example

    5 3
    0 1
    1 2
    3 4
    

Output Example

    2
    

Solution Process

To solve this problem, we will use the Union-Find data structure to organize the relationships between each node. We will follow these steps:

Step 1: Initialize the Parent Array

Each node is initialized to have itself as its parent. In other words, we create a parent array and set each node to point to itself.

    parent = [0, 1, 2, 3, 4]  # Initialized according to the number of nodes
    

Step 2: Perform Union Operations

Based on the given edge information, we connect the nodes through Union operations. This combines connected sets into one.

Step 3: Count Connected Sets Using Find Operations

By performing Find operations on each node, we check which set they belong to and count the number of unique root nodes before printing the result.

Implementation

Now, let’s implement the above steps in Python code.

    class UnionFind:
        def __init__(self, size):
            self.parent = list(range(size))
            self.rank = [1] * size
        
        def find(self, p):
            if self.parent[p] != p:
                # Path compression
                self.parent[p] = self.find(self.parent[p])
            return self.parent[p]
        
        def union(self, p, q):
            rootP = self.find(p)
            rootQ = self.find(q)
            
            if rootP != rootQ:
                # Union by rank
                if self.rank[rootP] > self.rank[rootQ]:
                    self.parent[rootQ] = rootP
                elif self.rank[rootP] < self.rank[rootQ]:
                    self.parent[rootP] = rootQ
                else:
                    self.parent[rootQ] = rootP
                    self.rank[rootP] += 1

    # Usage Example
    def count_connected_components(n, edges):
        uf = UnionFind(n)
        
        # Perform Union with edge information
        for u, v in edges:
            uf.union(u, v)
        
        # Count the number of unique roots and return the number of connected components
        root_set = set(uf.find(i) for i in range(n))
        return len(root_set)

    # Input handling
    n = 5
    edges = [(0, 1), (1, 2), (3, 4)]
    print(count_connected_components(n, edges))  # Output: 2
    

Interpreting Results

When executing the above code, it outputs 2. This indicates that there are two sets of nodes that are connected in the given graph.

Time Complexity Analysis

When using Union-Find, the time complexity of each operation approaches O(α(n)), where α is the inverse Ackermann function. Since this function grows extremely slowly, we can consider it to take close to constant time in practical terms.

Conclusion

In this post, we examined the Union-Find data structure and methods for solving problems using it. We confirmed that Union-Find can efficiently solve complex connectivity problems, encouraging you to practice various applications.

Thank you!

Topological Sorting is a method of sorting nodes in a Directed Acyclic Graph (DAG). It arranges all edges in such a way that they point from the upper node to the lower node. This sorting is mainly used in determining the order of tasks, dependencies, and various programming problems.

Problem Description

Given the number of classes N and a list of edges indicating the precedence relationships between classes, the problem is to determine the order in which the classes can be taken using the topological sorting algorithm.

Input Format

N = 6
edges = [(2, 1), (3, 1), (4, 1), (6, 4), (5, 2), (5, 3)]

Output Format

1 2 3 4 5 6 (One possible order in which the classes can be taken)

Problem Solving Process

1. Understanding the Problem

The topological sorting problem is to establish the precedence relationships through the given nodes (N) and edge information (edges), and then sort all the nodes. Here, edges is represented in the form of (A, B), indicating that A must be taken before B can be taken.

2. Handling Input Parameters

To implement topological sorting, we first need to construct the graph’s adjacency list and the in-degree array. The in-degree array counts the number of classes each node must attend.

from collections import deque

def topological_sort(N, edges):
    # Initialize graph and in-degree
    graph = [[] for _ in range(N + 1)]
    in_degree = [0] * (N + 1)
    
    # Register edge information in the graph and in-degree
    for u, v in edges:
        graph[u].append(v)
        in_degree[v] += 1

3. Designing the Topological Sorting Algorithm

Now, let’s design the algorithm to perform topological sorting. We will add nodes with an in-degree of 0 to a queue, and as we remove nodes one by one from the queue, we will decrease the in-degrees of the nodes connected to that node. Nodes whose in-degree becomes 0 after the decrease will be added back to the queue. This process will be repeated until the queue is empty. Ultimately, we will return the sorted order of nodes.

    # Add nodes with in-degree of 0 to the queue
    queue = deque()
    for i in range(1, N + 1):
        if in_degree[i] == 0:
            queue.append(i)

    result = []
    
    while queue:
        current = queue.popleft()
        result.append(current)
        
        for neighbor in graph[current]:
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                queue.append(neighbor)

    return result

4. Writing and Executing the Complete Code

Now let’s integrate the entire code to write the final code. We can pass the processed input values to the function to check the results.

N = 6
edges = [(2, 1), (3, 1), (4, 1), (6, 4), (5, 2), (5, 3)]

sorted_order = topological_sort(N, edges)
print("Order of classes that can be taken:", sorted_order)

5. Results and Evaluation

Running the above code will allow us to find an order of classes that can be taken through topological sorting. Due to the nature of the graph, multiple correct answers may arise. Therefore, if the algorithm is functioning correctly, it is necessary to broadly validate the validity of the results.

6. Code and Algorithm Optimization

The time complexity of the topological sorting algorithm is O(V + E), where V is the number of vertices and E is the number of edges. This algorithm can operate efficiently even with large datasets, making it a useful tool for employment coding tests.

Conclusion

Topological sorting is a useful algorithm in graph theory, applicable to various problems. In this lecture, we implemented topological sorting using Python and provided content suitable for practical coding tests. We hope you will continue to understand and utilize such algorithmic problems in depth.

References

• Topological sorting – Wikipedia
• Topological sorting – GeeksforGeeks
• BOJ 2263 – Tree Traversal

Hello, everyone! In this lecture, we will explore in detail how to implement an algorithm to solve the Traveling Salesman Problem (TSP). The TSP is about finding the path that visits all given cities at the minimum cost and then returns to the starting city. This problem is one of the classic combinatorial optimization problems and has various approaches.

1. Problem Description

Given N cities and the movement cost between each pair of cities, the goal is to find a minimum cost path that visits each city exactly once and returns to the starting city. We will use the following input and output format to solve this problem.

Input

• The first line contains the number of cities N (1 ≤ N ≤ 10).
• From the second line onward, an N x N adjacency matrix is given, where the value in the i-th row and j-th column of the matrix represents the cost to move from city i to city j. If movement between two cities is impossible, the cost is 0.

Output

• Output the minimum cost to visit all cities and return to the starting city.

2. Problem Solving Process

There are various algorithms to solve this problem, but here we will describe an approach using DFS (Depth-First Search) and Memoization. The following are the steps to solve the problem.

Step 1: Understand the Problem

To solve the TSP problem, all possible paths need to be explored. While a complete search can calculate the minimum cost by considering all possibilities, the number of combinations increases exponentially as the number of cities increases, hence an efficient method is required.

Step 2: Record Visited Cities with Bitmask

You can use a bitmask to record whether each city has been visited. For instance, with four cities, you can represent each city as a bit, creating combinations from 0b0000 to 0b1111. This method makes it easy to check whether a city has been visited or not.

Step 3: Implement DFS and Memoization

Using DFS to explore all paths while calculating costs, we will employ memoization techniques to store already calculated paths to avoid redundant calculations. Below is the Python code implementing this:

from sys import maxsize

def tsp(curr_city, visited, n, cost_matrix, memo):
    if visited == (1 << n) - 1:  # All cities visited
        return cost_matrix[curr_city][0] or maxsize  # Return to starting city or maxsize if not possible

    if memo[curr_city][visited] != -1:
        return memo[curr_city][visited]  # Return already computed cost

    min_cost = maxsize
    for city in range(n):
        if visited & (1 << city) == 0:  # City not visited
            new_cost = cost_matrix[curr_city][city] + tsp(city, visited | (1 << city), n, cost_matrix, memo)
            min_cost = min(min_cost, new_cost)

    memo[curr_city][visited] = min_cost
    return min_cost

def solve_tsp(n, cost_matrix):
    memo = [[-1] * (1 << n) for _ in range(n)]
    return tsp(0, 1, n, cost_matrix, memo)  # Start from city 0 with only city 0 visited

# Example usage
if __name__ == "__main__":
    n = 4  # Number of cities
    cost_matrix = [
        [0, 10, 15, 20],
        [10, 0, 35, 25],
        [15, 35, 0, 30],
        [20, 25, 30, 0]
    ]
    result = solve_tsp(n, cost_matrix)
    print(f"Minimum cost: {result}")
    

Step 4: Code Explanation

The code above consists of the following main functions:

• tsp(curr_city, visited, n, cost_matrix, memo): Takes the current city, a bitmask of visited cities, the number of cities, the cost matrix, and a list for memoization to calculate the minimum cost.
• solve_tsp(n, cost_matrix): Initializes the memoization list and performs the TSP function.

Step 5: Time Complexity Analysis

The time complexity of the above algorithm is O(n^2 * 2^n). Here, n is the number of cities, and 2^n is the number of combinations of all bitmasks. Thus, as the number of cities increases, the amount of computation can increase dramatically, so in practice, the number of cities is limited to no more than 10.

3. Conclusion

In this lecture, we explored the concepts and algorithm implementation methods for the Traveling Salesman Problem (TSP). The TSP problem is a good example to utilize various problem-solving techniques and helps cultivate thinking that can be applied to other algorithmic problems through deep understanding.

If you encounter a TSP-related problem in a coding test, it would be beneficial to approach it as discussed above. Now, I encourage you to practice more so you can solve this problem independently. Thank you!

Hello! Today, we will introduce and explain the algorithm problem ‘Finding Next Greater Element’, which is very useful for job seekers. This problem will greatly help in understanding and utilizing the concept of stacks. So, shall we begin?

Problem Description

Problem Description: This is a problem of finding the “next greater element” for each element in the given array. The “next greater element” refers to the first element that is greater than the current element on its right. If such an element does not exist, it is represented as -1.

Input: The first line contains a natural number N (1 ≤ N ≤ 1,000,000), and the second line contains N natural numbers A₁, A₂, …, A_N (1 ≤ A_i ≤ 1,000,000).

Output: Print the next greater element for each element, one per line.

Example

Input:

5
2 1 3 4 5

Output:

3
3
4
5
-1

Problem Solving Strategy

One of the most effective ways to solve this problem is by using a stack. A stack is a Last In, First Out (LIFO) data structure that can be utilized effectively in solving this problem.

Approach Using a Stack

1. Create an empty stack.
2. Traverse the given array from right to left, performing the following for each element:
1. Compare the current element with the top element of the stack.
2. If the top element of the stack is greater than the current element, that element is the next greater element. Store the next greater element for the current element.
3. If the top element of the stack is smaller than or equal to the current element or if the stack is empty, pop elements from the stack.
4. Add the current element to the stack.
3. After traversing all elements, print the result array storing the next greater elements.

Code Implementation

Now, let’s implement the above algorithm in Python code.

def find_next_greater_element(arr):
    n = len(arr)
    result = [-1] * n  # Result array to store next greater elements
    stack = []  # Create a stack

    # Traverse the array from right to left
    for i in range(n - 1, -1, -1):
        # Compare with the top element of the stack
        while stack and stack[-1] <= arr[i]:
            stack.pop()  # Pop from the stack
        
        # If the stack is not empty, record the next greater element
        if stack:
            result[i] = stack[-1]
        
        # Add the current element to the stack
        stack.append(arr[i])

    return result

# Input handling
n = int(input())
arr = list(map(int, input().split()))

# Finding next greater elements
result = find_next_greater_element(arr)

# Print results
for r in result:
    print(r)

Code Explanation

The code above defines a function that finds the next greater element for each element in the given array. The function follows these steps:

1. Calculate the length of the input array and initialize the result array.
2. Iterate through the given array from right to left.
3. Check the top element of the stack for comparison with the current element.
4. If the top element of the stack is less than or equal to the current element, pop elements from the stack. This ensures only values greater than the current element remain in the stack.
5. If the stack is not empty, the top element of the stack is the next greater element for the current element. Record this in the result array.
6. Add the current element to the stack.

Complexity Analysis

The time complexity is O(N). Each element is added to and removed from the stack once, resulting in a total of N operations. The space complexity is O(N), considering the space needed for the result array and the stack.

Example Result

Let's check some test cases for the code. We will use the example provided above to find the next greater elements.

# Input example
# 5
# 2 1 3 4 5

print(find_next_greater_element([2, 1, 3, 4, 5]))  # Output: [3, 3, 4, 5, -1]

Conclusion

In this session, we explored the process of solving the 'Finding Next Greater Element' problem. We efficiently solved the problem using a stack and applied the principle through actual code. This method of problem-solving is very useful in real coding tests and algorithm interviews, so be sure to practice it.

Next time, I will come back with another algorithm problem. Thank you!