Category: Python Coding Test

Python Coding Test Course, 2 N Tile Filling

In today’s world, where programming and algorithms are becoming increasingly important, many companies require algorithm and coding tests as a prerequisite for employment. One of the popular problems is 2*N Tile Filling. In this article, I will analyze the problem and explain the process of solving it in detail. Through this problem, we will also learn the concept of dynamic programming (DP) and look at a Python code implementation using it.

Problem Description

The problem is as follows:

Find the number of ways to fill a 2 x n rectangular space with tiles of size 1 x 2 or 2 x 1.

For example, when n=3, the tiles can be filled in the following ways:

  • 3 vertical 1 x 2 tiles
  • 1 horizontal 1 x 2 tile and 2 vertical tiles
  • 2 horizontal 1 x 2 tiles and 1 vertical tile
  • 1 2 x 1 tile and 2 1 x 2 tiles
  • 3 vertical 2 x 1 tiles

The solution to this problem can be approached through dynamic programming. The key is to recursively divide the problem based on how each tile is placed and avoid duplicate calculations by storing results using the memoization technique.

Approach to Problem Solving

This problem can be solved based on the following rules:

  • Base case: For n=1, only the method of placing a 1 x 2 tile vertically is possible. Therefore, the number of cases is 1.
  • More general case: For n=2, there are two ways: either to place 2 horizontal 1 x 2 tiles or to place 1 vertical 2 x 1 tile. Thus, the number of cases is 2.
  • Recursive relationship: For n > 2, it can be divided in two ways:
    1. Place a 1 x 2 tile and fill the remaining 2 x (n-1) space
    2. Place a 2 x 1 tile and fill the remaining 2 x (n-2) space

    Therefore, the recursive relation can be expressed as:
    f(n) = f(n-1) + f(n-2)

Dynamic Programming Implementation

Now, let’s write a Python code to solve the problem using dynamic programming (DP) based on the recursive relationship above.


def tile_fill(n):
    # Initialize the DP array.
    dp = [0] * (n + 1)
    
    # Set the base cases.
    dp[0] = 1  # The case of filling nothing
    if n >= 1:
        dp[1] = 1  # The case of placing a 1 x 2 tile vertically
    
    # Fill the DP array.
    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]
    
    return dp[n]

Code Explanation

In the above code, we first initialize the DP array from 0 to n. After setting the values for f(0) and f(1) as base cases, we proceed to fill the values from f(2) to f(n) using a loop. Ultimately, the value of dp[n] represents the number of ways to fill the 2 x n rectangle.

Time Complexity Analysis

The time complexity of this algorithm is O(n). This is because in each iteration, the DP array only repeats as many times as the number of elements in the n structure. The space complexity is also O(n).

Summary

In this article, we learned how to utilize dynamic programming techniques through the 2*N Tile Filling Problem. By defining the problem, deriving solutions through repetitive formulas, and implementing this in code, we were able to develop algorithmic thinking. Similar problems may appear in actual coding tests, so it is advisable to practice consistently.

Problem Variations and Applications

If the given rectangular size were to change from 2 x N to another form, for example, to 3 x N, think about how you would approach it. Practicing variations of problems will significantly help in deepening algorithmic thinking.

In conclusion, when solving algorithm problems, it is important to decompose the problem and explore possible solutions. The 2*N tile filling problem is a good example of how to embody that kind of thinking.

python coding test course, 022 sorting numbers 3

Problem Overview

This problem requires writing an algorithm to sort N given numbers in ascending order. The range of the given numbers is from 1 to 10000, and each number is an integer greater than 0 and less than or equal to 10000. Therefore, we need to implement an efficient sorting algorithm considering this aspect.

Problem Description

Please write a program that sorts the given N numbers and prints one number per line. The maximum number of inputs can be 1,000,000. Thus, since we need to sort a large quantity of numbers, we must consider the time complexity.

Input

The first line of the input contains the number of elements N (1 ≤ N ≤ 1,000,000), followed by N lines each containing a number.

Output

Print the sorted numbers one per line.

Example Input

    5
    5
    4
    3
    2
    1

Example Output

    1
    2
    3
    4
    5

Problem Analysis

Given the constraints, we can use a sorting algorithm that is efficient in terms of time and space. Python’s built-in sorting functionality utilizes Timsort, which has a time complexity of O(N log N) in the average and worst-case scenarios. However, considering the range of numbers is limited (from 1 to 10000), we can also explore counting sort or bucket sort for this specific task.

Proposed Solution

We will use Counting Sort to solve this problem. Counting Sort works as follows:

  • Create a counting array to count the number of input numbers. The size of the array is set to 10001 (including 0~10000).
  • Store the occurrence count of each number in the counting array.
  • Iterate through the counting array to print each number in sorted order.

Code Implementation

import sys

def counting_sort(n, numbers):
    count = [0] * 10001  # Create size 10001 for numbers range from 0 to 10000

    for num in numbers:
        count[num] += 1  # Count occurrences of the numbers

    result = []
    for i in range(10001):
        while count[i] > 0:
            result.append(i)  # Add to result array based on count array values
            count[i] -= 1

    return result

if __name__ == "__main__":
    n = int(sys.stdin.readline())
    numbers = [int(sys.stdin.readline()) for _ in range(n)]
    
    sorted_numbers = counting_sort(n, numbers)
    print("\n".join(map(str, sorted_numbers)))

Main Points

  • Counting Sort is a stable sorting algorithm. This means that the relative position of elements with the same value is preserved.
  • This algorithm has a time complexity of O(N + K), where N is the size of the input and K is the range of the numbers.
  • The memory usage is also efficient as long as K is not too large.

Conclusion

By practicing the Counting Sort algorithm through this problem, we learned how to maximize sorting performance. Additionally, we acquired knowledge about basic input/output handling and array usage in Python. Understanding various sorting algorithms is a critical aspect of programming tests, and approaching problems in this way will be very helpful.

Additional Problems: Variations and Applications

Furthermore, you can try the following variations of the problem:

  • If you need to sort numbers that include negative values, how would you expand the input range and adjust the counting array indices?
  • Utilize various sorting algorithms to analyze the differences in time complexity when sorting the same set of numbers.
  • When the range of numbers (K) is very large, what algorithms can be used as alternatives to Counting Sort?