Author: root

python coding test course, breadth-first search

Breadth-First Search (BFS) is a method for exploring graphs or trees, starting from a vertex and visiting all its adjacent vertices first, followed by the unvisited adjacent vertices. It can also be used as a shortest path search algorithm in certain cases. Today, we will proceed with a deep problem-solving approach along with the basic concept of BFS.

Problem: Numbering Complexes

Problem Description

In a given n x n array consisting of 0s and 1s, 1 represents the location of a house and 0 represents the absence of a house. Write a program that assigns each complex a unique number to distinguish all the houses. The size of a complex is defined as the number of houses belonging to it.

Input

n (1 ≤ n ≤ 25)
An n x n array composed of 0s and 1s

Output

Print the size of each complex in ascending order

Example Input

7
0 0 1 0 0 1 1
0 0 1 0 1 1 1
0 1 1 0 0 0 0
0 0 0 0 1 0 0
1 1 1 0 1 1 0
0 0 0 0 0 0 0
0 0 1 0 0 0 0

Example Output

1
7

Problem Approach

To solve this problem, we will use the BFS algorithm to explore the graph. By traversing the provided 2D array, whenever we encounter a house (1), we will count all the connected houses using BFS to calculate the size of the complex. In the next step, we will explain the concept of BFS in detail.

Breadth-First Search (BFS) Concept

BFS is implemented using a queue. It follows the following process:

  1. Add the starting node to the queue and mark it as visited.
  2. Remove a node from the queue and add all its adjacent nodes (that have not yet been visited) to the queue, marking them as visited.
  3. If the queue is not empty, return to step 2.

Coding Implementation

I will write code to solve the problem using the BFS algorithm. 


from collections import deque

def bfs(x, y, n, graph, visited):
    queue = deque()
    queue.append((x, y))
    visited[x][y] = True

    directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    size = 1  # store the size of the complex

    while queue:
        cx, cy = queue.popleft()  # current position
        for dx, dy in directions:
            nx, ny = cx + dx, cy + dy
            if 0 <= nx < n and 0 <= ny < n and not visited[nx][ny] and graph[nx][ny] == 1:
                visited[nx][ny] = True
                queue.append((nx, ny))
                size += 1  # increase the count of connected houses

    return size  # return the size of the complex

def find_complexes(n, graph):
    visited = [[False] * n for _ in range(n)]
    complexes = []

    for i in range(n):
        for j in range(n):
            if graph[i][j] == 1 and not visited[i][j]:
                size = bfs(i, j, n, graph, visited)
                complexes.append(size)

    return sorted(complexes)  # return the sizes in ascending order

# Example input
n = 7
graph = [
    [0, 0, 1, 0, 0, 1, 1],
    [0, 0, 1, 0, 1, 1, 1],
    [0, 1, 1, 0, 0, 0, 0],
    [0, 0, 0, 0, 1, 0, 0],
    [1, 1, 1, 0, 1, 1, 0],
    [0, 0, 0, 0, 0, 0, 0],
    [0, 0, 1, 0, 0, 0, 0]
]

complex_sizes = find_complexes(n, graph)
print(len(complex_sizes))  # print the number of complexes
for size in complex_sizes:
    print(size)  # print the size of each complex

Code Explanation

The above code demonstrates how to calculate the size of complexes using BFS. The main functions are find_complexes and bfs.

  • bfs(x, y, n, graph, visited): Executes BFS starting from the point (x, y) to calculate the size of the corresponding complex. It records each visited house using a queue and aggregates all connected houses.
  • find_complexes(n, graph): Iterates through the given graph, finds houses (1), invokes BFS, and stores the calculated complex sizes in a list.

Conclusion

Breadth-First Search (BFS) is a useful search method that can be utilized in various fields. I hope you learned how to solve problems using BFS through this lecture. Understanding and applying the code during the problem-solving process will greatly assist you in your coding tests.

Additional Practice Problems

Try solving the following problems:

  • Finding the shortest path between specific nodes in the given graph
  • Solving a maze problem using BFS

References

Python Coding Test Course, Sorting Digits in Descending Order

1. Problem Definition

The goal of this problem is to sort the given digits in descending order to form the largest possible number. The input number is an integer, and our task is to return the largest number possible using the digits of this number.

Example Input/Output

  • Input: 2183
  • Output: 8321

2. Approach to the Problem

This problem involves extracting the individual digits of the number and then sorting them in descending order. In Python, we can easily perform such sorting operations using the sort() method of a list. The specific steps are as follows:

  1. Convert the integer to a string.
  2. Split the string into individual digits (characters) to create a list.
  3. Sort the list in descending order.
  4. Merge the sorted list back into a string, convert it to an integer, and return it.

3. Algorithm Implementation

Now, let’s solve the problem using Python code based on the above approach.

def sort_digits_descending(n):
    # Step 1: Convert integer to string
    str_n = str(n)
    
    # Step 2: Convert string to list
    digits = list(str_n)
    
    # Step 3: Sort the list in descending order
    digits.sort(reverse=True)
    
    # Step 4: Merge the sorted list back into a string and convert to integer
    sorted_n = int(''.join(digits))
    
    return sorted_n

4. Code Explanation

The function sort_digits_descending takes the parameter n and performs the entire process. Each step works as follows:

  • String Conversion: Converts the integer to a string using str(n).
  • List Conversion: Converts each character (digit) of the string into a list using list(str_n).
  • Sorting: Sorts the list in descending order using sort(reverse=True).
  • Merging: Merges the list back into a string using "".join(digits), and converts it to an integer using int() before returning it.

5. Test Cases

Let’s use several test cases to verify that our function works correctly.

print(sort_digits_descending(2183)) # 8321
print(sort_digits_descending(1450)) # 5410
print(sort_digits_descending(9876543210)) # 9876543210
print(sort_digits_descending(0)) # 0
print(sort_digits_descending(1001)) # 1100

6. Result Analysis

After checking the results of each test case, we found that the expected output was returned in all cases. The function was implemented very simply and efficiently using Python’s built-in features.

7. Optimization and Considerations

The code written above has a time complexity of O(m log m) for sorting the digits, where m is the number of digits in the input integer. Since the maximum number of digits for integers is limited to 10, there are no performance issues, but it may be necessary to consider making it valid for larger numbers or reducing complexity for efficiency.

8. Conclusion

We have implemented an algorithm to sort the given integer in descending order to create the largest possible value. In this process, we were able to solve the problem simply with the use of Python’s list methods and string manipulation features. Future considerations for additional optimization and alternative approaches are encouraged. This will help improve problem-solving skills in coding tests.

python coding test course, sum of remainders

Hello everyone! In this lecture, we will look at one of the algorithm problems frequently encountered in coding tests using Python, which is ‘Calculating the Remainder of the Sum’. This problem is a good example that helps in understanding and using modular operations and processing large amounts of data.

Problem Description

You are tasked with solving the problem of finding the remainder when the sum of subarrays of an array A consisting of N integers is divided by K. A subarray is defined as a contiguous set of numbers defined by a starting index and an ending index of the array.

For example, if the array A is [3, 1, 4, 1, 5] and K is 2, you need to find the remainder when the sum of all subarrays is divided by K. This problem requires basic math and programming skills and can be solved using various approaches.

Input

  • The first line contains two integers N (1 ≤ N ≤ 100,000) and K (1 ≤ K ≤ 10,000).
  • The second line contains N integers A[1], A[2], …, A[N] (0 ≤ A[i] ≤ 109).

Output

Print the number of subarrays whose sums give a remainder of 0 when divided by K.

Example

    Input
    5 2
    3 1 4 1 5

    Output
    4

Approach

To solve this problem, the following approaches can be utilized.

1. Understanding the Definition of Subarrays

A subarray is a set of consecutive elements from the original array, so you need to generate all possible subarrays from the given array, then calculate the sum of each subarray and check the remainder when divided by K.

2. Efficient Calculation Method

Directly computing subarrays can result in a time complexity of O(N2), which is inefficient in the worst case. Therefore, you can solve this problem in O(N) using cumulative sums and hash maps.

3. Using Cumulative Sums and Modular Operations

Calculate the cumulative sum and store the remainder when divided by K. If the same remainder value appears, you can utilize the fact that the sum of the subarray between those indices can be divided by K.

Code Example

    
    def count_subarrays_with_zero_modulo(n, k, arr):
        count = 0
        mod_count = [0] * k
        current_sum = 0
        
        for num in arr:
            current_sum += num
            mod = current_sum % k
            
            if mod < 0:  # Python's mod can be negative, adjust it
                mod += k
            
            # If current modulo is zero, we can count it
            if mod == 0:
                count += 1
            
            # Add the number of times this modulo has appeared before
            count += mod_count[mod]
            mod_count[mod] += 1
            
        return count

    # Example usage
    n = 5
    k = 2
    arr = [3, 1, 4, 1, 5]
    result = count_subarrays_with_zero_modulo(n, k, arr)
    print(result)  # Output: 4

Result Analysis

In the above code, the function count_subarrays_with_zero_modulo counts the number of subarrays in the array whose sum is divisible by K. In this process, it calculates the sum at each index using cumulative sums, and counts occurrences of the same remainder using a hash map. By doing this, we can solve the problem with a time complexity of O(N).

Conclusion

Through this lecture, you learned about the approach to solving the remainder sum problem and acquired efficient coding techniques. These techniques can be applied in various situations requiring large-scale data processing and will significantly enhance your algorithm problem-solving skills.

Additionally, try to gain experience by attempting solutions for similar problems. In the next lecture, we will meet with another interesting topic. Thank you!

python coding test course, depth-first search

1. Introduction to Depth-First Search (DFS)

Depth-First Search (DFS) is one of the graph exploration algorithms that explores as deep as possible from a given node and, when there are no more nodes to explore, backtracks to the last visited node to explore other paths. This method is used for various purposes depending on the structure of the graph and is applied in tree traversal, connected component exploration, pathfinding problems, and more.

The operation of DFS is as follows:

  • Add the starting node to the stack.
  • Pop a node from the stack and explore it.
  • Mark the explored node as visited.
  • Add all unvisited adjacent nodes to the stack.
  • Repeat the above process while the stack is not empty.

2. Problem Description

Problem: Counting the Number of Islands

In the given 2D array grid, ‘1’ represents land, and ‘0’ represents water.
An island is a set of connected lands vertically or horizontally.
Write a function to count the number of islands. 

            Input: 
            grid = [
                ["1","1","0","0","0"],
                ["1","1","0","0","0"],
                ["0","0","1","0","0"],
                ["0","0","0","1","1"]
            ]
            Output: 3

3. Problem Solving Process

3.1. Understanding the Problem

To solve the problem, we first need to identify the sections of connected land (i.e., islands).
Each island can be identified using DFS, by traversing the land and also exploring adjacent land,
thereby confirming all parts of the island.

3.2. Designing the Data Structure

We will use a stack to implement DFS.
To efficiently manage resources, we will use a boolean array to keep track of the visited status of all elements in the 2D array.

3.3. Implementing DFS

            def dfs(grid, visited, i, j):
                # Exit if out of bounds or already visited
                if i < 0 or i >= len(grid) or j < 0 or j >= len(grid[0]) or visited[i][j] or grid[i][j] == '0':
                    return
                # Mark the current position as visited
                visited[i][j] = True
                
                # Explore up, down, left, right
                dfs(grid, visited, i - 1, j)  # Up
                dfs(grid, visited, i + 1, j)  # Down
                dfs(grid, visited, i, j - 1)  # Left
                dfs(grid, visited, i, j + 1)  # Right

3.4. Implementing the Final Function

            def numIslands(grid):
                if not grid:
                    return 0
                
                visited = [[False for _ in range(len(grid[0]))] for _ in range(len(grid))]
                island_count = 0
                
                # Explore all nodes in the grid
                for i in range(len(grid)):
                    for j in range(len(grid[0])):
                        if grid[i][j] == '1' and not visited[i][j]:
                            dfs(grid, visited, i, j)
                            island_count += 1  # Found a new island
                            
                return island_count

3.5. Testing the Code

            grid = [
                ["1","1","0","0","0"],
                ["1","1","0","0","0"],
                ["0","0","1","0","0"],
                ["0","0","0","1","1"]
            ]

            print(numIslands(grid))  # Should print 3.

4. Review of Problem Solving

We solved the problem using DFS, with a time complexity of O(N * M), where N is the number of rows and M is the number of columns.
Since we visit each node at most once, this can be considered an efficient method.
Additionally, the space complexity is also O(N * M), due to the additional space used for the visiting list.

While DFS can use a large amount of memory, it can often be more effective than BFS depending on the nature or size of the problem.
Particularly beneficial in pathfinding problems or problems distinguishing connected components, the advantages of DFS can be utilized.

5. Conclusion

In this lecture, we explored the basic concept of DFS and the problem-solving approach.
DFS can be applied to various problems, so based on this lecture, please try solving different issues.
Thank you.

Python Coding Test Course, Exploring Geometry

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!