Category: Python Coding Test

Hello! Today we will take a closer look at one of the algorithm problems that often appears in Python coding tests, “Counting Stair Numbers”. Through this problem, we will learn the concept of dynamic programming and the process of solving problems.

Problem Description

A stair number is defined by the following rules:

• A stair number is composed of digits from 0 to 9.
• The digits of two adjacent positions must differ by exactly 1. For example, 234 is valid, but 235 or 123 are not valid.
• The first digit of a stair number cannot be 0.

Given a natural number N, how many stair numbers of length N exist? For example, if N is 2, there are 9 possible stair numbers: 10, 12, 21, 23, 32, 34, 43, 45, 54, 65, 76, 78, 87, 89, 98, totaling 15.

Input Format

The first line contains the number of digits in the stair number N (1 ≤ N ≤ 100).

Output Format

The first line should output the number of N-digit stair numbers modulo 1,000,000,000.

Example Input

2

Example Output

15

Problem Solving Strategy

This problem can be solved using dynamic programming. Stair numbers can be categorized according to the rules of the problem, and for each digit, we consider the possible number combinations to derive the results. Now, let’s look at the specific solution process.

Step 1: State Definition

To find N-digit stair numbers, we define a DP array. We use dp[n][k] to represent the number of stair numbers of length n whose last digit is k. Here, n is the number of digits, and k is the last digit (0 to 9).

Step 2: Initial Condition Setting

The stair numbers of length 1 are from 1 to 9. Therefore, we set dp[1][0] = 0 (0 cannot be the first digit), and dp[1][1] = dp[1][2] = ... = dp[1][9] = 1.

Step 3: Deriving the Recursion Formula

To construct stair numbers of length n, we add one digit to stair numbers of length n-1. If the last digit is 0, it can lead to 1, and if the last digit is 9, it can lead to 8. Therefore, we get the following recursion formulas:

dp[n][0] = dp[n-1][1]
dp[n][k] = dp[n-1][k-1] + dp[n-1][k+1] (1 <= k <= 8)
dp[n][9] = dp[n-1][8]

Step 4: Calculating the Final Result

The N-digit stair numbers can be found by summing up the cases for all digits from 0 to 9. The final result is calculated as sum(dp[N]).

Implementation

Now, let’s implement all of this logic in Python code:

def count_stair_numbers(n):
    # Constant for modular arithmetic
    MOD = 1000000000

    # Initialize DP table
    dp = [[0] * 10 for _ in range(n + 1)]

    # When the length is 1
    for i in range(1, 10):
        dp[1][i] = 1

    # Fill the DP table
    for i in range(2, n + 1):
        dp[i][0] = dp[i - 1][1] % MOD
        for j in range(1, 9):
            dp[i][j] = (dp[i - 1][j - 1] + dp[i - 1][j + 1]) % MOD
        dp[i][9] = dp[i - 1][8] % MOD

    # Calculate the result
    result = sum(dp[n]) % MOD
    return result

# User Input
n = int(input("Enter the value of N: "))
print(count_stair_numbers(n))

Conclusion

Today, through the “Counting Stair Numbers” problem, we have understood the basic concepts of dynamic programming and explored the process of solving problems using Python code. I hope this will enhance your algorithm problem-solving skills. Stay tuned for the next tutorial where we will cover another interesting algorithm problem!

Problem Description

This is a problem of finding a path from the starting point to the endpoint in a given 2D array. This array consists of passages and obstacles, where passages are represented by 0 and obstacles by 1.

The goal is to determine whether there is a path from the given starting point to the endpoint and to output the possible path. Movement is allowed in four directions: up, down, left, and right.

Problem Definition

    def find_path(maze, start, end):
        """
        :param maze: 2D list representing the maze
        :param start: Tuple of (x, y) coordinates for the start point
        :param end: Tuple of (x, y) coordinates for the end point
        :return: List of tuples representing the path or None if no path exists
        """
    

Problem Example

    maze = [
        [0, 1, 0, 0, 0],
        [0, 1, 0, 1, 0],
        [0, 0, 0, 1, 0],
        [1, 1, 0, 0, 0],
        [0, 0, 0, 1, 1]
    ]
    start = (0, 0)  # Starting point
    end = (4, 4)    # Endpoint
    

Expected result:
[(0, 0), (1, 0), (2, 0), (2, 1), (2, 2), (3, 2), (4, 2), (4, 3), (4, 4)]

Solution Approach

This problem can be solved using Depth-First Search (DFS) or Breadth-First Search (BFS) algorithms. Here, I will explain how to find a path using DFS.

Depth-First Search (DFS) Algorithm

DFS explores all possible paths to determine if the endpoint is reachable. During the path search, it keeps track of visited nodes to prevent revisiting.

Implementation Steps

Step 1: Basic Setup

First, define the maze and the starting and ending points through basic setup.

    maze = [
        [0, 1, 0, 0, 0],
        [0, 1, 0, 1, 0],
        [0, 0, 0, 1, 0],
        [1, 1, 0, 0, 0],
        [0, 0, 0, 1, 1]
    ]
    start = (0, 0)
    end = (4, 4)
    

Step 2: Define the DFS Function

Implement a function to find the path using DFS.

    def dfs(maze, current, end, path, visited):
        if current == end:
            return path
        
        x, y = current
        visited.add(current)

        for dx, dy in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
            next_x, next_y = x + dx, y + dy
            
            if 0 <= next_x < len(maze) and 0 <= next_y < len(maze[0]):
                if maze[next_x][next_y] == 0 and (next_x, next_y) not in visited:
                    result = dfs(maze, (next_x, next_y), end, path + [(next_x, next_y)], visited)
                    if result is not None:
                        return result
        
        visited.remove(current)
        return None
    

Step 3: Implement the Path Finding Function

Finally, implement the path finding function to call DFS.

    def find_path(maze, start, end):
        visited = set()
        return dfs(maze, start, end, [start], visited)
    

Step 4: Output the Result

Call the function to output the result.

    path = find_path(maze, start, end)
    print("Path:", path)
    

Complete Code

    def dfs(maze, current, end, path, visited):
        if current == end:
            return path
        
        x, y = current
        visited.add(current)

        for dx, dy in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
            next_x, next_y = x + dx, y + dy
            
            if 0 <= next_x < len(maze) and 0 <= next_y < len(maze[0]):
                if maze[next_x][next_y] == 0 and (next_x, next_y) not in visited:
                    result = dfs(maze, (next_x, next_y), end, path + [(next_x, next_y)], visited)
                    if result is not None:
                        return result
        
        visited.remove(current)
        return None

    def find_path(maze, start, end):
        visited = set()
        return dfs(maze, start, end, [start], visited)

    maze = [
        [0, 1, 0, 0, 0],
        [0, 1, 0, 1, 0],
        [0, 0, 0, 1, 0],
        [1, 1, 0, 0, 0],
        [0, 0, 0, 1, 1]
    ]
    start = (0, 0)
    end = (4, 4)
    path = find_path(maze, start, end)
    print("Path:", path)
    

Conclusion

In this article, we examined a method using the DFS algorithm to solve the problem of finding a path in a 2D array. The code was structured to explore paths through DFS at each step and return results when conditions are met. Such basic pathfinding problems can be utilized as a foundation to tackle more complex problems.

Today, we will solve an algorithm problem for game development using Python. In this tutorial, we will enhance our problem-solving skills through algorithm problems and learn various techniques and concepts that can be applied to real game development.

Problem Description

Problem: “Strange Grid” Game

A grid-shaped game board is given, where each cell contains an integer. In the game, the player starts from outside the boundary of the board and can move up to 3 cells. However, the score that the player can move is calculated as the sum of the values of each cell. The player must choose moves in such a way that they ultimately have a score of 0 or more. Find the possible maximum score while visiting all the cells of the game board.

Input

        First line: Size of the grid N (1 ≤ N ≤ 10)
        Next N lines: Each element of the grid (−100 ≤ element ≤ 100)
    

Output

        Maximum achievable score
    

Example Input

    3
    10 -1 2
    -5 20 3
    2 -3 -4
    

Example Output

    32
    

Problem Analysis

This problem requires using the ‘DFS (Depth First Search)’ technique to explore all possible paths and find the maximum score among them. First, we need to define the moving paths for each cell in the grid. According to the given rules, let us explore all possible paths from the starting point to find the highest total score.

Problem Solving Process

1. Set Up Basic Structure

To solve the problem, we will implement DFS using a recursive function. The recursive function will explore all possible paths from the current position. Here is the basic framework.

def dfs(x, y, score):
    # Function to explore all possible paths from the current position and return the maximum score
    pass
    

2. Implement Path Exploration Logic

Now, we should be able to calculate the positions when moving up, down, left, and right from each cell. To do this, we will use a direction array. We can use the following direction array to explore paths.

dx = [0, 1, 0, -1] # Left and Right
dy = [1, 0, -1, 0] # Up and Down

3. Implement Recursive Function

Now let’s recursively move within the DFS function and calculate the scores. We will check the possibility of movement based on the size of the grid and the current score, and set the boundary condition.

def dfs(x, y, score, visited):
    if x < 0 or x >= N or y < 0 or y >= N or visited[x][y]:
        return score
    
    visited[x][y] = True
    score += grid[x][y] # Add the score of the current position to the current score.
    
    max_score = score
    for i in range(4):
        new_x = x + dx[i]
        new_y = y + dy[i]
        max_score = max(max_score, dfs(new_x, new_y, score, visited))
    
    visited[x][y] = False # Backtracking
    return max_score

4. Implement Main Function

To start exploring all paths, we need to define the main function. In this function, we will read the grid input and start DFS exploration. Finally, we output the maximum score.

def main():
    global grid, N
    N = int(input())
    grid = [list(map(int, input().split())) for _ in range(N)]
    
    visited = [[False]*N for _ in range(N)]
    max_total_score = 0
    
    # Start DFS from all positions.
    for i in range(N):
        for j in range(N):
            max_total_score = max(max_total_score, dfs(i, j, 0, visited))
    
    print(max_total_score)

5. Full Code

The complete code that integrates all parts is as follows.

def dfs(x, y, score, visited):
    if x < 0 or x >= N or y < 0 or y >= N or visited[x][y]:
        return score
    
    visited[x][y] = True
    score += grid[x][y]
    
    max_score = score
    for i in range(4):
        new_x = x + dx[i]
        new_y = y + dy[i]
        max_score = max(max_score, dfs(new_x, new_y, score, visited))
    
    visited[x][y] = False
    return max_score

def main():
    global grid, N
    N = int(input())
    grid = [list(map(int, input().split())) for _ in range(N)]
    
    visited = [[False]*N for _ in range(N)]
    max_total_score = 0
    
    for i in range(N):
        for j in range(N):
            max_total_score = max(max_total_score, dfs(i, j, 0, visited))
    
    print(max_total_score)

if __name__ == "__main__":
    main()

Conclusion

Through this problem, we learned how to utilize DFS to explore paths and maximize points in a game environment. By solving coding problems through algorithms, we can enhance our effectiveness as game developers.

Additional Learning Resources

Referencing the following materials can provide deeper learning:

• Official Python Tutorial
• GeeksforGeeks Algorithm Tutorial
• LeetCode Problem Solving

Problem Description

In our neighborhood, there are N people. Each person has their own nickname, and some of them tell lies to each other. A lie is simply the act of leaving ‘their nickname’ to the other person and breaking a promise. You want to find the nicknames of those who actually lied in this situation.

Information is provided about the N people as follows:

• Their own nickname
• The number of lies they told to each other

Input Format

The first line contains N (1 ≤ N ≤ 100,000). From the second line onward, N lines contain each person’s nickname and the number of lies that person told.

Output Format

Print the nicknames of liars one per line. If there are no liars, print the message “No liars found.”

Example

    Input:
    3
    Younghee 1
    Cheolsu 0
    Minsu 2

    Output:
    Younghee
    Minsu
    

Solution

To solve this problem, we need to identify each individual’s nickname and the number of lies they told based on the given input. The process of solving the problem using the provided data structure is as follows:

Step 1: Data Structure Design

To handle each person’s information, we will use a list to store the nicknames of the people and the number of lies they told. In this case, we should use a tuple or dictionary to store each person’s information.

Step 2: Collect Input Data

When receiving input from the user, we first read the number of people N, and then for the next N lines, we read each person’s information. In this process, we separate and store each piece of information.

Step 3: Extract Liars

To extract liars, we need to store the nicknames of all individuals whose number of lies is greater than 0. We will use a conditional statement to check the number of lies for each individual.

Step 4: Output Results

Finally, we will print the extracted list of nicknames. If the list is empty, we will print the message “No liars found.”

Code Implementation

Now, let’s implement the code based on the above logic:

def find_liars(n, people):
    liars = []
    
    for name, lies in people:
        if lies > 0:
            liars.append(name)
    
    if liars:
        return liars
    else:
        return ["No liars found."]

if __name__ == "__main__":
    n = int(input("Enter the number of people: "))
    people = []

    for _ in range(n):
        entry = input("Enter name and number of lies: ").split()
        name = entry[0]
        lies = int(entry[1])
        people.append((name, lies))

    result = find_liars(n, people)
    for liar in result:
        print(liar)

Code Explanation

The code above simply returns the entire process. At each step, it stores the information entered by the people and determines the nicknames of those who lied based on this information.

Function Explanation

• find_liars(n, people): Accepts the given number of people and their information, returning a list of nicknames of those who lied.
• if __name__ == "__main__":: The main program execution part, which processes the input received from the user.

Conclusion

Through this problem, we solved a common type of problem in coding tests based on understanding simple data structures and lists. I hope the process of solving this problem helps you in preparing for coding tests.

One of the common problems that often appears in coding tests is finding the largest square in a two-dimensional array. This problem can be defined as follows.

Problem Definition

Given a binary matrix (a two-dimensional array consisting of 0s and 1s), find the area of the largest square composed of 1s.

For example, let’s assume we have the following matrix.

    [
        [1, 0, 1, 0, 0],
        [1, 0, 1, 1, 1],
        [1, 1, 1, 1, 1],
        [1, 0, 0, 1, 0]
    ]
    

In the matrix above, the largest square is the area from (1, 1) to (3, 3), with an area of 9.

Problem Approach and Solution Process

To solve this problem, we can use the Dynamic Programming method. This methodology breaks the problem down into smaller subproblems and uses the results to derive the final outcome.

Approach Using Dynamic Programming

1. First, we will get the size of the given matrix and define a 2D array dp for dynamic programming. Each element of this dp array will represent the length of one side of the largest square at a specific position.

2. Initialization: Initialize each element of the dp array to 0. However, the first row and first column of the given matrix should be set to 1 only for positions in the original matrix where there is a 1.

3. Filling the dp array: By examining each element of the binary matrix, if the value at a specific position (i, j) is 1, then dp[i][j] is set to the minimum of dp[i-1][j], dp[i][j-1], dp[i-1][j-1] plus 1. This is how we calculate the sides of the largest square.

4. Result: We need to find the largest value in the dp array, and the square of this value will be the area of the square we are looking for.

Implementation of Dynamic Programming

Now, let’s write a Python code based on the above method.

    
def maximalSquare(matrix):
    if not matrix:
        return 0

    max_square_len = 0
    rows = len(matrix)
    cols = len(matrix[0])
    dp = [[0] * cols for _ in range(rows)]

    for i in range(rows):
        for j in range(cols):
            if matrix[i][j] == '1':
                if i == 0 or j == 0:
                    dp[i][j] = 1
                else:
                    dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1

                max_square_len = max(max_square_len, dp[i][j])

    return max_square_len * max_square_len
    
    

Code Explanation

The first line of the code checks whether the given matrix is empty. If it is empty, the result is 0.

Next, it retrieves the number of rows and columns in the matrix and creates the dp array. This array has the same size as the given binary matrix and is initialized to 0.

Using a loop, we iterate through each element, processing only when the current element is 1. During this process, we fill the dp array using the previously mentioned relationships. Here, we always track and update the length of the largest square’s side.

Finally, we return the area of the largest square.

Complexity Analysis

The above algorithm has a time complexity of O(n * m), where n is the number of rows in the matrix and m is the number of columns. The space complexity is O(n * m), which is the space needed to store the dp array.

Let’s Try with an Example

Now, let’s use this function to find the largest square in the given matrix.

    
matrix = [
    ["1", "0", "1", "0", "0"],
    ["1", "0", "1", "1", "1"],
    ["1", "1", "1", "1", "1"],
    ["1", "0", "0", "1", "0"]
]
print(maximalSquare(matrix))  # 9
    
    

Conclusion

This problem is one of the frequently encountered types in coding tests. If you can understand and solve this problem well through practice, it will greatly help you to solve similar problems. Moreover, the ability to understand and apply the principles of dynamic programming is useful for solving various algorithmic problems.

Additionally, you can also tackle more complex variations of this problem by extending the binary matrix into more intricate forms. For example, there are various types of problems where the structure of 0s and 1s changes in the given matrix, or where you need to find different shapes of squares or rectangles that satisfy given conditions.

Moving Forward

Continue to practice solving more algorithm problems and optimizing by considering time complexity, space complexity, and so on. Deepening your understanding of frequently used data structures and algorithms is also very important. Furthermore, as you encounter various problems, your problem-solving skills will naturally improve.

We hope to help you grow your coding skills through many algorithm courses in the future!