Category: C# Coding Test Tutorials

Problem Description

Given two strings A and B, the task is to find the Longest Common Subsequence (LCS) of these strings. A subsequence is a sequence derived from another sequence where the order of characters is preserved, allowing for deletion. In other words, a subsequence of A must exist in B.

For example, if string A is “ABCBDAB” and B is “BDCAB”, then the longest common subsequence is “BCAB”. This LCS problem requires efficient algorithms across various fields.

Problem Input

The lengths N and M of the two strings A and B (1 ≤ N, M ≤ 1000) and the strings A and B are provided.

Problem Output

Output the length of the longest common subsequence.

Problem Solving Process

1. Understanding Dynamic Programming

This problem can be solved using Dynamic Programming (DP). DP is a technique to improve efficiency by breaking down complex problems into smaller subproblems. Here, a DP array is used to store and calculate the LCS lengths between each pair of characters.

2. Initializing the DP Array

First, initialize a two-dimensional DP array based on the lengths of the strings A and B. DP[i][j] represents the length of the longest common subsequence of the first i characters of A and the first j characters of B.

    int[,] dp = new int[N + 1, M + 1];
    

3. DP State Transition

The DP rules are as follows:

• If the i-th character of A and the j-th character of B are the same: dp[i][j] = dp[i - 1][j - 1] + 1
• If the i-th character of A and the j-th character of B are different: dp[i][j] = Math.Max(dp[i - 1][j], dp[i][j - 1])

4. Final Result

After populating the DP array, dp[N][M] will contain the length of the longest common subsequence.

Code Implementation

    using System;

    class Program
    {
        static void Main(string[] args)
        {
            string A = "ABCBDAB";
            string B = "BDCAB";
            int N = A.Length;
            int M = B.Length;

            int[,] dp = new int[N + 1, M + 1];

            for (int i = 1; i <= N; i++)
            {
                for (int j = 1; j <= M; j++)
                {
                    if (A[i - 1] == B[j - 1])
                    {
                        dp[i, j] = dp[i - 1, j - 1] + 1;
                    }
                    else
                    {
                        dp[i, j] = Math.Max(dp[i - 1, j], dp[i, j - 1]);
                    }
                }
            }

            Console.WriteLine("Length of the longest common subsequence: " + dp[N, M]);
        }
    }
    

Test Cases

Example Input

    A: ABCBDAB
    B: BDCAB
    

Example Output

    Length of the longest common subsequence: 4
    

Time Complexity Analysis

The time complexity of this dynamic programming algorithm is O(N * M), and the space complexity is also O(N * M). This ensures satisfactory performance even when the lengths of the two strings are 1000.

Conclusion

The Longest Common Subsequence (LCS) problem is a key problem that illustrates how to determine relationships in various fields of computer science. It has been confirmed that it can be solved efficiently using dynamic programming. This method frequently appears in coding tests, so it is important to understand it well and practice.

Hello everyone. Today, we will learn how to solve the “Finding Cities at a Specific Distance” problem using C#. This problem often appears in coding tests and utilizes graph and BFS (Breadth-First Search) algorithms. Therefore, this course will be a great help in enhancing your understanding of graph theory and algorithms.

Problem Description

Let me introduce a problem based on given conditions.

Problem:

There are N cities and M bidirectional roads. Each city is numbered from 1 to N. When there is a road connecting two cities A and B, the length of the road connecting A and B is always considered as 1. Given a specific city X and distance K, you need to output all cities that are exactly at distance K.

Input Format:
The first line contains the number of cities N, the number of roads M, distance K, and starting city X.
Following that, M lines will contain the two cities connected by each road.

Output Format:
Output the numbers of the cities at distance K in ascending order.
If there are no such cities, output -1.

Input Example

4 4 2 1
1 2
1 3
2 3
2 4

Output Example

4

Problem Analysis

To solve this problem, we need a method to represent and search the graph.
Each city can be represented as a vertex, and roads as edges.
We need to find a specific distance using BFS or DFS algorithms.
In this case, we are looking for distance K, so BFS is more suitable because it explores from the closest nodes, thus naturally applying the concept of distance.

Problem Solving Process

Step 1: Define Data Structures

First, we will use lists and a queue to represent cities and roads.
– The list will store the roads connected to each city.
– The queue is the data structure necessary for performing BFS.

Step 2: Create the Graph

We will take city and road information as input to create an adjacency list.
To use the data starting from index 1, we will set the size to N + 1.

Step 3: Implement BFS

We will implement the BFS function starting from the departure city X.
We will find cities at distance K and store the results.

Step 4: Output Results

Sort the result list and output it.
If there are no cities at distance K, output -1.

C# Code Implementation

Here is the C# code to solve the given problem.

using System;
using System.Collections.Generic;
using System.Linq;

public class Program
{
    static List[] graph;
    static bool[] visited;
    static List result;
    
    public static void Main(string[] args)
    {
        // Input
        string[] input = Console.ReadLine().Split(' ');
        int N = int.Parse(input[0]); // Number of cities
        int M = int.Parse(input[1]); // Number of roads
        int K = int.Parse(input[2]); // Distance
        int X = int.Parse(input[3]); // Starting city
        
        // Initialize graph
        graph = new List[N + 1];
        for (int i = 1; i <= N; i++)
        {
            graph[i] = new List();
        }
        
        // Input road information
        for (int i = 0; i < M; i++)
        {
            input = Console.ReadLine().Split(' ');
            int a = int.Parse(input[0]);
            int b = int.Parse(input[1]);
            graph[a].Add(b);
            graph[b].Add(a);
        }
        
        // BFS and result generation
        visited = new bool[N + 1];
        result = new List();
        BFS(X, 0, K);
        
        // Output results
        result.Sort();
        if (result.Count == 0)
        {
            Console.WriteLine(-1);
        }
        else
        {
            foreach (int city in result)
            {
                Console.WriteLine(city);
            }
        }
    }
    
    static void BFS(int start, int distance, int K)
    {
        Queue> queue = new Queue>();
        queue.Enqueue(new Tuple(start, distance));
        visited[start] = true;
        
        while (queue.Count > 0)
        {
            var current = queue.Dequeue();
            int currentCity = current.Item1;
            int currentDistance = current.Item2;
            
            // If a city at distance K is found
            if (currentDistance == K)
            {
                result.Add(currentCity);
                continue;
            }
            
            // Explore adjacent cities
            foreach (var neighbor in graph[currentCity])
            {
                if (!visited[neighbor])
                {
                    visited[neighbor] = true;
                    queue.Enqueue(new Tuple(neighbor, currentDistance + 1));
                }
            }
        }
    }
}

Code Explanation

I will briefly explain the process of solving the problem through the C# code above.

• Data Input: Read the values for the number of cities, number of roads, distance K, and starting city X from the first line, and input M road information.
• Graph Construction: Construct an adjacency list to represent cities as vertices and roads as edges.
• BFS Algorithm Implementation: Use a Queue to execute BFS and calculate the distance to each city.
• Output Results: Return the sorted results, and if there are no cities matching distance K, output -1.

Conclusion

In this lecture, we learned how to solve the “Finding Cities at a Specific Distance” problem using C#.
I hope you felt the importance of graph data structures and search algorithms through the distance-based exploration process using BFS.
In the next lecture, we will solve even more diverse problems together.

Problem Description

This is a problem to determine whether it is possible to create a sequence sorted in ascending order by using a stack from the given sequence. The input sequence should be able to be output in order from the smallest number. If it’s not possible, “NO” should be printed; if it is possible, “YES” should be printed.

Example Cases

• Input: 5
• Input Sequence: 5 1 2 3 4
• Output: YES

• Input: 7
• Input Sequence: 1 2 5 3 4 6 7
• Output: NO

Approach

This problem can be solved using the properties of a stack. A stack follows a Last In First Out (LIFO) structure, where the last element added is the first to be removed. Thus, to sort the sequence in ascending order, the input numbers need to be stored in the stack and removed only when necessary.

Step 1: Input Processing

First, the given sequence needs to be read. The length of the sequence and the elements of that sequence are received.

Step 2: Storing Elements in the Stack

While processing the input numbers sequentially, they need to be compared with the current number to output. We use the stack to store the current number so that it can be output starting from the smallest one.

Step 3: Output Condition Checking

If a number larger than the one we need to output is stacked, then it can no longer be retrieved, so “NO” is printed. After processing all elements, if possible, “YES” is printed.

C# Code Implementation

Below is the code implementing the algorithm explained above in C# language.

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        int n = int.Parse(Console.ReadLine());
        Stack stack = new Stack();
        int current = 1;

        for (int i = 0; i < n; i++)
        {
            int num = int.Parse(Console.ReadLine());

            while (current <= num)
            {
                stack.Push(current);
                current++;
            }

            if (stack.Count == 0 || stack.Pop() != num)
            {
                Console.WriteLine("NO");
                return;
            }
        }

        Console.WriteLine("YES");
    }
}
    

Code Explanation

The C# code above works as follows:

• int n = int.Parse(Console.ReadLine());
  Takes the length of the sequence as input from the user.
• Stack stack = new Stack();
  Initializes the stack.
• int current = 1;
  Represents the current number to be outputted.
• For each input number in a loop:
• while (current <= num)
  If the current number is less than or equal to the input number, add the current number to the stack and increase the current number.
• if (stack.Count == 0 || stack.Pop() != num)
  Pop the top number from the stack and compare it with the input number. If the stack is empty or they are different, print “NO”.
• After processing all numbers, print “YES”.

Complexity Analysis

The time complexity of this algorithm is O(n). Each number is pushed and popped from the stack only once. The space complexity is also O(n) since in the worst case, all numbers might be stacked.

Conclusion

This problem is a typical one that can be solved using the properties of a stack. Such stack problems often appear in coding tests, so it’s important to have a good understanding of how stacks and queues operate. In this tutorial, we learned how to create a sequence in ascending order using a stack. Practicing these fundamental algorithms is essential for solving various problems.

Additional Practice Problems

Try solving other algorithm problems using stacks:

• Parenthesis Balancing Problem
• Postfix Notation Calculator

Reference Material

If you want to learn more algorithms, refer to the following materials:

• Geeks for Geeks – Stack
• Introduction to Stack in C#

Hello! In this article, we will discuss one of the algorithm problems that frequently appears in coding tests, the Path Finding problem. This tutorial will explain the definition of the problem, the solution, C# code implementation, and more. We will start with the fundamentals of the necessary algorithms and explore how to apply complex pathfinding algorithms.

Problem Definition

The problem is as follows:

Find the shortest path from the starting point S to the endpoint E in a given 2D grid. The grid consists of 0s and 1s, where 0 represents a traversable cell and 1 represents a wall. The path can only move to adjacent cells in up, down, left, or right directions. If a path exists, return the length of the shortest path; if not, return -1.

Example

Here are the example inputs and outputs:

Input:
grid = [
  [0, 0, 1, 0, 0],
  [0, 0, 0, 0, 1],
  [0, 1, 1, 0, 0],
  [0, 0, 0, 0, 0],
  [1, 1, 1, 1, 0]
]
start = (0, 0)  // Position of S
end = (4, 4)    // Position of E

Output:
Length of the shortest path = 8

Approach to Problem Solving

There are various methods to solve the problem, but we will use the BFS (Breadth-First Search) algorithm. BFS is very effective in solving shortest path problems. It explores the current node and its adjacent nodes in turn, returning the shortest path after exploring all nodes.

Algorithm Explanation

The basic structure of the BFS algorithm is as follows:

1. Put the starting point in the queue and mark it as visited.
2. Repeat while the queue is not empty:
• Dequeue the current position from the queue.
• If the current position is the endpoint, return the length of the shortest path.
• Check all adjacent cells of the current position:
• If the cell is traversable and not visited, add it to the queue and mark it as visited.
3. If the endpoint is not reached after exploring all paths, return -1.

C# Code Implementation

Now, let’s implement the algorithm described above in C# code.

using System;
using System.Collections.Generic;

class Program {
    public static int ShortestPath(int[,] grid, (int, int) start, (int, int) end) {
        int rows = grid.GetLength(0);
        int cols = grid.GetLength(1);
        
        int[] directions = {0, 1, 0, -1, 0}; // Up, Down, Left, Right movements

        Queue<((int, int), int)> queue = new Queue<((int, int), int)>();
        bool[,] visited = new bool[rows, cols];
        
        queue.Enqueue((start, 0)); // (position, length of the path)
        visited[start.Item1, start.Item2] = true;

        while (queue.Count > 0) {
            var (current, length) = queue.Dequeue();

            if (current == end) {
                return length;
            }

            for (int i = 0; i < 4; i++) {
                int newRow = current.Item1 + directions[i];
                int newCol = current.Item2 + directions[i + 1];

                if (newRow >= 0 && newRow < rows && newCol >= 0 && newCol < cols && 
                    grid[newRow, newCol] == 0 && !visited[newRow, newCol]) {
                    
                    queue.Enqueue(((newRow, newCol), length + 1));
                    visited[newRow, newCol] = true;
                }
            }
        }

        return -1; // If unable to reach the endpoint
    }

    public static void Main() {
        int[,] grid = {
            {0, 0, 1, 0, 0},
            {0, 0, 0, 0, 1},
            {0, 1, 1, 0, 0},
            {0, 0, 0, 0, 0},
            {1, 1, 1, 1, 0}
        };
        
        var start = (0, 0);
        var end = (4, 4);
        int result = ShortestPath(grid, start, end);
        Console.WriteLine("Length of the shortest path: " + result);
    }
}

Code Review

The above code demonstrates how to find a path using the BFS algorithm. Let’s take a closer look at each part of the code.

Variable Explanation

• rows and cols: Store the number of rows and columns in the grid.
• directions: Define the directions for up, down, left, and right movements.
• queue: A queue for BFS that stores pairs of (position, length of the path).
• visited: A 2D array that keeps track of whether each cell has been visited.

Functioning of the Queue

We dequeue the current position from the queue and check all adjacent cells, adding them to the queue if they are traversable. This process continues until we find the shortest path.

Performance Analysis

The time complexity of this algorithm is O(V + E), where V is the number of vertices (all cells in the 2D grid) and E is the number of edges (the number of adjacent cells). The space complexity is O(V), which accounts for the space required for the BFS queue and visit tracking.

Conclusion

In this article, we discussed the pathfinding problem using C#. We explained the process of finding the shortest path using the BFS algorithm and implemented it in code. When solving algorithmic problems, it is important to understand the problem accurately and select the appropriate algorithm for the approach. I hope you can improve your skills through various problems!

Thank you!

In this course, we will cover coding test problems using C#.
The topic is “Finding the minimum value among prime and palindrome numbers within a given range.”
This problem emphasizes algorithmic thinking and allows you to learn various approaches to writing efficient code.

Problem Description

Given an integer N,
the task is to find all prime and palindrome numbers among the integers from 1 to N and determine the minimum value among them.
A prime number is a positive integer greater than 1 that has no positive divisors other than 1 and itself,
and a palindrome number is a number that reads the same forward and backward.

Input

– Integer N (1 ≤ N ≤ 1,000,000)

Output

– Print the minimum value among the prime and palindrome numbers.
– If there are no such numbers, you should print -1.

Algorithm Analysis

To solve this problem, we can approach it in the following steps:

1. Prime Check: Implement an algorithm to check if numbers within the given range are prime.
2. Palindrome Check: Write a function to check if each number is a palindrome.
3. Finding Minimum: Collect the numbers that are both prime and palindrome, then return the minimum value.

C# Code Implementation

Below is the code to solve the problem using C#.

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        int N = int.Parse(Console.ReadLine());
        int minPrimePalindrome = int.MaxValue;

        for (int i = 2; i <= N; i++)
        {
            if (IsPrime(i) && IsPalindrome(i))
            {
                minPrimePalindrome = Math.Min(minPrimePalindrome, i);
            }
        }

        Console.WriteLine(minPrimePalindrome == int.MaxValue ? -1 : minPrimePalindrome);
    }

    static bool IsPrime(int number)
    {
        if (number < 2) return false;
        for (int i = 2; i <= Math.Sqrt(number); i++)
        {
            if (number % i == 0) return false;
        }
        return true;
    }

    static bool IsPalindrome(int number)
    {
        string str = number.ToString();
        int len = str.Length;
        for (int i = 0; i < len / 2; i++)
        {
            if (str[i] != str[len - 1 - i]) return false;
        }
        return true;
    }
}
    

Code Explanation

1. Main Method: For the input integer N, it iterates through numbers from 2 to N.
It checks if each number is both prime and a palindrome, and finds the minimum value among them.

2. IsPrime Method: Determines whether the given number is prime.
If the number is less than 2, it returns false as it is not prime,
and it checks for divisibility from 2 to √number to determine its primality.

3. IsPalindrome Method: Converts the given number to a string and
checks if it is a palindrome by comparing characters from the front and back.
It returns true if all characters match.

Time Complexity

The time complexity of this algorithm is O(N√N).
This is because checking numbers up to N involves O(√N) time for primality testing for each number.
Therefore, as the input range increases, the computation time is affected, so it is important to consider this when writing the code.

Conclusion

Through the problems covered in this course, we have learned how to determine prime numbers and check for palindromes.
Understanding primes and palindromes is a common topic in coding tests,
so it is advisable to practice thoroughly.
Additionally, I recommend building your skills through a variety of practice problems.