Category: Python Coding Test

Hello! Today, we will learn how to solve geometric problems that are frequently asked in Python coding tests. Geometric problems mainly include calculations of areas, perimeters, intersections, distances, etc., and are an important part of algorithm problem-solving. In this course, we will explain commonly asked problems based on basic geometric concepts and look at step-by-step approaches to successfully solve them.

Problem: Determine if two line segments intersect

This problem involves determining whether two given line segments intersect.

Problem Definition

Determine whether the given two line segments AB and CD intersect. Each line segment is defined by two points as follows:

• Line segment AB: Point A(x1, y1), Point B(x2, y2)
• Line segment CD: Point C(x3, y3), Point D(x4, y4)

Input Format

Four integers x1, y1, x2, y2, x3, y3, x4, y4 are given.

Output Format

If the segments intersect, print “YES”. Otherwise, print “NO”.

Problem Approach

To determine whether two line segments intersect, we must use the geometric concept of ‘direction of the segments’. By calculating the direction for each point of the two segments, we can verify whether they intersect.

1. Direction Calculation

To calculate the direction for line segments AB and CD, we use the following formula:

def direction(px, py, qx, qy, rx, ry):
    return (qx - px) * (ry - py) - (qy - py) * (rx - px)

This function calculates the direction for points P, Q, R and returns a positive, negative, or zero value.

2. Intersection Determination

We can determine that line segments AB and CD intersect when the endpoints have different directions. That is, the following conditions must be satisfied:

• The product of direction(A, B, C) and direction(A, B, D) is greater than 0, and the product of direction(C, D, A) and direction(C, D, B) is also greater than 0.

These conditions can be combined to integrate the entire logic into one function.

3. Code Implementation

Let’s implement the entire code based on what we have explained so far.

def ccw(px, py, qx, qy, rx, ry):
    return (qx - px) * (ry - py) - (qy - py) * (rx - px) > 0

def is_intersect(x1, y1, x2, y2, x3, y3, x4, y4):
    d1 = ccw(x1, y1, x2, y2, x3, y3)
    d2 = ccw(x1, y1, x2, y2, x4, y4)
    d3 = ccw(x3, y3, x4, y4, x1, y1)
    d4 = ccw(x3, y3, x4, y4, x2, y2)

    if d1 != d2 and d3 != d4:
        return "YES"

    return "NO"

# Example input
x1, y1, x2, y2 = map(int, input().split())
x3, y3, x4, y4 = map(int, input().split())

print(is_intersect(x1, y1, x2, y2, x3, y3, x4, y4))

Conclusion

In this lecture, we implemented an algorithm to determine whether two line segments intersect. Geometric problems are based on basic mathematical theories, and understanding algorithms is necessary. By practicing with various examples, you will gain confidence in solving geometric problems. I hope you will encounter more algorithm problems in the future and improve your coding skills through them.

Thank you!

Hello! Today, we will learn about the Radix Sort algorithm in Python. Radix Sort is one of the sorting algorithms with very favorable space and time complexity, and it is particularly useful for sorting data types such as integers or strings. In this lecture, we will explain the principle of Radix Sort, its implementation method, and how to use Radix Sort through practical problems in detail.

What is Radix Sort?

Radix Sort is a method of sorting that considers each digit of a given number (tens, hundreds, etc.). Radix Sort proceeds in the following steps:

1. Start from the lowest digit and distribute based on each digit.
2. Gather the distributed numbers to create a sorted list.
3. Move to the next digit and repeat the process.

Radix Sort is generally implemented in two ways: LSD (Least Significant Digit) and MSD (Most Significant Digit). This lecture will focus on the LSD method, which starts from the smallest digit.

Time Complexity of Radix Sort

The time complexity of Radix Sort is O(nk), where n is the number of numbers to be sorted and k is the number of digits in the largest number. Radix Sort is classified as a stable sort, which means that the relative order of elements with the same value does not change.

Problem: Sorting Using Radix Sort

Now, let’s solve a problem that applies Radix Sort to sort given integers. The problem is as follows:

Problem Solving Process

Now, let’s implement Radix Sort to solve the above problem. First, we will write a helper function called counting_sort that sorts based on each digit as follows. This function sorts the array based on the given digit.

def counting_sort(arr, exp):
    n = len(arr)
    output = [0] * n  # List to store the sorted array
    count = [0] * 10  # List to count numbers from 0 to 9

    # Count the occurrences of each number based on the current digit
    for i in range(n):
        index = (arr[i] // exp) % 10
        count[index] += 1

    # Find the position of each number using cumulative sum
    for i in range(1, 10):
        count[i] += count[i - 1]

    # Create the sorted array
    for i in range(n - 1, -1, -1):
        index = (arr[i] // exp) % 10
        output[count[index] - 1] = arr[i]
        count[index] -= 1

    # Reflect the sorted result in the original array
    for i in range(n):
        arr[i] = output[i]

In the above code, the counting_sort function checks the current digit of each number in the input array, counts how many of each number correspond to that digit, and generates sorted results through cumulative sums. Now let’s write the main function to implement Radix Sort.

def radix_sort(arr):
    # Find the largest number in the array to determine the number of digits
    max_num = max(arr)

    # Start sorting from the smallest digit
    exp = 1
    while max_num // exp > 0:
        counting_sort(arr, exp)
        exp *= 10

Now, let’s look at the complete implementation of Radix Sort.

def radix_sort(arr):
    max_num = max(arr)  # Find the maximum value
    exp = 1  # Initialize the exponent of the digit
    while max_num // exp > 0:  # Repeat for the number of digits in the maximum value
        counting_sort(arr, exp)  # Call counting_sort for the current digit
        exp *= 10  # Move to the next digit

def counting_sort(arr, exp):
    n = len(arr)
    output = [0] * n  # List to store the sorted array
    count = [0] * 10  # List to count numbers from 0 to 9

    # Count the occurrences of each number based on the current digit
    for i in range(n):
        index = (arr[i] // exp) % 10
        count[index] += 1

    # Find the position of each number using cumulative sum
    for i in range(1, 10):
        count[i] += count[i - 1]

    # Create the sorted array
    for i in range(n - 1, -1, -1):
        index = (arr[i] // exp) % 10
        output[count[index] - 1] = arr[i]
        count[index] -= 1

    # Reflect the sorted result in the original array
    for i in range(n):
        arr[i] = output[i]

# Test code
arr = [170, 45, 75, 90, 802, 24, 2, 66]
print("Array before sorting:", arr)
radix_sort(arr)
print("Array after sorting:", arr)

Test Results

When the above code is executed, the following results appear:

Array before sorting: [170, 45, 75, 90, 802, 24, 2, 66]
Array after sorting: [2, 24, 45, 66, 75, 90, 170, 802]

By comparing the array before and after sorting, we can see that Radix Sort works well.

Advantages and Disadvantages of Radix Sort

Advantages

• It performs very quickly for specific types of data (integers, strings, etc.).
• Being a stable sort, the order of elements with the same value is preserved.
• It enables efficient sorting when interested in specific digits.

Disadvantages

• It consumes additional memory and requires an array of the same size as the original array.
• It is not suitable for data types other than integers or strings.
• If the range of data is very large, the time complexity may increase.

Conclusion

In this lecture, we learned in detail about Radix Sort and solved a problem of sorting an array through it. Radix Sort is a very useful sorting algorithm in specific situations, so it may frequently appear in algorithm exams. Therefore, it is important to clearly understand the principles of Radix Sort and its actual implementation. In the next session, we will learn about another useful sorting algorithm or data structure. Thank you for reading!

Problem Description

The problem we will address today is the Coin Change Problem. This problem involves finding the least number of coins needed to make a specific amount using various coins that we often encounter in real life.

Problem Definition

Write a function min_coins(coins, amount) that satisfies the following conditions:

• coins: A list of available coins (e.g., [1, 5, 10, 25])
• amount: The target amount to be formed

This function should return the minimum number of coins needed to make the given amount. If it is not possible to use the coins, it should return -1.

Understanding the Problem

To understand the problem more deeply, let’s look at a few examples.

Approach

To solve this problem, we will use a greedy algorithm. The greedy algorithm works by making the best choice in the current situation. Therefore, we will start by using the largest coins sequentially to try to form the target amount.

The specific steps of the algorithm are as follows:

1. Sort the available coins in descending order.
2. Compare the current amount with the coins and use as many coins as possible.
3. Repeat this process until the remaining amount is zero.
4. If the remaining amount is zero, return the number of coins, otherwise return -1.

Code Implementation

Now, let’s write the code based on this approach:

def min_coins(coins, amount):
    # Sort the coins in descending order
    coins.sort(reverse=True)
    
    count = 0  # Number of coins used
    
    for coin in coins:
        # Ignore if the current coin is greater than amount
        while amount >= coin:
            amount -= coin  # Subtract the coin value from amount
            count += 1  # Increase the coin count
            
    # Check if the final amount is 0
    return count if amount == 0 else -1
    

Testing

Now, let’s test the function we have written.

# Test cases
print(min_coins([1, 5, 10, 25], 63))  # 6
print(min_coins([2, 4], 5))             # -1
print(min_coins([5, 2, 1], 11))         # 3 (5 + 5 + 1)
    

Conclusion

We have solved the Coin Change Problem using the greedy algorithm. Through this problem, we learned the fundamental approach of the greedy algorithm and studied a common type of problem seen in coding tests.

I hope to deepen my understanding of the greedy algorithm by practicing more problems. Like the problem above, it is essential to practice how to sort data and use loops to find solutions. The greedy algorithm can be a useful tool for solving various problems.

Thank you!

The graph is a mathematical object composed of vertices and edges.
Graphs play a vital role in data structures and are an efficient way to solve various complex problems.
In this article, we will explain the basic concepts of graphs and cover how to represent and explore graphs using Python.

1. Basic Concepts of Graphs

A graph consists of nodes and the edges connecting those nodes. Graphs can be classified into two forms:

• Directed Graph: A graph where edges have direction. That is, when an edge points from A to B, there may not be an edge from B to A.
• Undirected Graph: A graph where edges do not have direction. An edge connecting A and B exists in both directions.

2. Representation Methods of Graphs

Graphs can be represented in various ways. The most common methods are:

1. Adjacency List: Represents the graph by maintaining a list of vertices connected to each vertex. This method is memory efficient.
2. Adjacency Matrix: Represents all vertices of the graph in a matrix form. Each element of the matrix indicates whether two vertices are connected.

3. Problem Solving: Representation of Graphs

Now, let’s solve a practical problem of representing a graph.

Problem Description

Write a program that receives the number of vertices and the information of edges, and represents the graph in both adjacency list and adjacency matrix forms based on the given information.

Input format:

• The first line contains the number of vertices N (1 ≤ N ≤ 100).
• The second line contains the number of edges M (1 ≤ M ≤ 1000).
• From the third line, the edge information (A, B) is given over M lines. A and B are integers from 1 to N, indicating they are connected.

Output format:

The first line should output the adjacency list, and the second line should output the adjacency matrix. Each vertex starts from 1.

4. Steps to Solve the Problem

The steps to solve the above problem are as follows:

4.1. Input Processing

First, receive the vertex and edge information from the user. Use the input() function in Python to receive input and convert it to the appropriate format.

4.2. Create Adjacency List

The adjacency list uses a list of lists to store the connected vertices for each vertex. Since the vertex numbers start from 1, an empty list is added in advance to match the list’s index.

4.3. Create Adjacency Matrix

The adjacency matrix uses a 2D array to store the connection status between vertices. The initial value is set to 0, and if an edge exists, it is set to 1. In the case of an undirected graph, when there is a connection A-B, both (A, B) and (B, A) in the matrix should be updated.

4.4. Output the Results

Finally, output the created adjacency list and adjacency matrix.

5. Code Implementation

def graph_representation():
    # Input
    N = int(input("Enter the number of vertices (1 ≤ N ≤ 100): "))
    M = int(input("Enter the number of edges (1 ≤ M ≤ 1000): "))
    
    # Initialize adjacency list
    adj_list = [[] for _ in range(N + 1)]
    
    # Initialize adjacency matrix
    adj_matrix = [[0] * (N + 1) for _ in range(N + 1)]
    
    # Input edge information
    for _ in range(M):
        A, B = map(int, input("Enter edge information (A B): ").split())
        adj_list[A].append(B)
        adj_list[B].append(A)  # Undirected graph
        adj_matrix[A][B] = 1
        adj_matrix[B][A] = 1  # Undirected graph
    
    # Output adjacency list
    print("Adjacency List:")
    for i in range(1, N + 1):
        print(f"{i}: {adj_list[i]}")
    
    # Output adjacency matrix
    print("Adjacency Matrix:")
    for i in range(1, N + 1):
        print(" ".join(map(str, adj_matrix[i][1:])))
        
# Function call
graph_representation()

6. Code Explanation

The above Python code consists of the following procedures:

• Input Processing: Receives the number of vertices and edges, and gets the information for each edge.
• Initialize Adjacency List: Creates an empty list according to the number of vertices N.
• Initialize Adjacency Matrix: Initializes a matrix of size N x N to 0.
• Input Edge Information and Update List/Matrix: Updates the adjacency list and matrix based on the input A, B in a loop.
• Output Results: Outputs the adjacency list and adjacency matrix respectively.

7. Example Execution

For example, if we have a graph with 5 vertices and 6 edges, the input and output would be as follows:

Enter the number of vertices (1 ≤ N ≤ 100): 5
Enter the number of edges (1 ≤ M ≤ 1000): 6
Enter edge information (A B): 1 2
Enter edge information (A B): 1 3
Enter edge information (A B): 2 4
Enter edge information (A B): 3 4
Enter edge information (A B): 4 5
Enter edge information (A B): 2 5
Adjacency List:
1: [2, 3]
2: [1, 4, 5]
3: [1, 4]
4: [2, 3, 5]
5: [2, 4]
Adjacency Matrix:
0 1 1 0 0
1 0 0 1 1
1 0 0 1 0
0 1 1 0 1
0 1 0 1 0

8. Conclusion

In this lecture, we learned about the concept of graphs and various representation methods. We also learned how to create adjacency lists and adjacency matrices through a problem, enhancing our understanding of the basic structure of graphs. There are many more problems to tackle, such as graph traversal (DFS, BFS), so I hope you build upon this knowledge and move to the next level.

Try solving various graph problems while studying algorithms. Thank you!