Category: C# Coding Test Tutorials

One important process to develop algorithmic problem-solving skills is to understand and implement various sorting algorithms.
In this session, we will learn how to practice sorting algorithms in the C# language through a problem called ‘Sorting Numbers’.

Problem Description

Write a program that sorts given integers in ascending order.
The input consists of the first line with the number of integers N (1 ≤ N ≤ 100,000),
and the second line provides N integers.
These integers are numbers with an absolute value of less than or equal to 1,000,000, and the same number may appear multiple times.

Input Example

    5
    5 3 2 1 4
    

Output Example

    1
    2
    3
    4
    5
    

Problem Solving Process

1. Understanding the Problem

The first thing to do to solve the problem is to thoroughly understand the given problem.
After confirming the number of values that need sorting and the range of these numbers, we must decide which sorting algorithm is most suitable.

2. Choosing a Sorting Algorithm

Based on the conditions of the given problem, choose the most suitable sorting algorithm. For example,
commonly used sorting algorithms include bubble sort, selection sort, insertion sort, quick sort, and merge sort.

In the case where the size of N can be up to 100,000, it is advisable to use a sorting algorithm with a time complexity of O(N log N),
such as quick sort or merge sort.
However, it should also be noted that using built-in sorting methods in C# is efficient enough.

3. Implementation in C#

C# allows easy sorting of arrays through the Array.Sort() method.
By using this, we can easily solve the problem without needing to implement the sorting algorithm ourselves.

Implementation Steps

1. Receive input from the user.
2. Store the received input values in an array.
3. Sort the array using the Array.Sort() method.
4. Output the sorted array.

4. Writing the Code

Below is the full code using C#.

    using System;
    using System.Linq;

    class Program
    {
        static void Main()
        {
            int N = int.Parse(Console.ReadLine());
            int[] numbers = new int[N];
            
            for (int i = 0; i < N; i++)
            {
                numbers[i] = int.Parse(Console.ReadLine());
            }
            
            Array.Sort(numbers);
            
            foreach (var number in numbers)
            {
                Console.WriteLine(number);
            }
        }
    }
    

5. Code Explanation

The code above executes through the following processes.

1. First, it takes the integer N as input to determine the size of the array.
2. Then, it receives N integers sequentially and stores them in the numbers array.
3. It calls the Array.Sort() method to sort the numbers array.
4. Finally, it outputs each element of the sorted array.

6. Time Complexity Analysis

The time complexity of the given problem is O(N log N), which is due to the chosen sorting algorithm (in the case of quick sort).
As the size of the input increases, the time required for sorting also increases proportionally, but
this algorithm operates efficiently in most cases.
The space complexity is O(N), which requires additional memory space to store the received array.

7. Conclusion

In this chapter, we solved the sorting numbers problem using C#.
We learned to understand the concept of sorting algorithms and how to efficiently solve problems using built-in methods.
It is also recommended to try implementing various sorting algorithms yourself.
Next time, we will deal with a more complex problem.
Thank you for reading until the end!

At this point where coding tests are gaining more and more popularity, algorithm problems are a topic that must be thoroughly understood. In this article, we will dive deep into the Merge Sort algorithm. Merge Sort is one of the sorting algorithms that generally performs well and is based on the ‘Divide and Conquer’ strategy. This article will explain the principles of Merge Sort, its implementation, and how to utilize Merge Sort through practical problems.

1. Overview of Merge Sort

Merge Sort works by splitting the list, sorting each part, and then merging them. It can be effectively used in various situations where the advantages of data structures and time complexity need to be considered. Merge Sort has a time complexity of O(n log n) in average, worst, and best cases, and it is a stable sorting algorithm. This means it maintains the relative order of data with the same value.

1.1. How Merge Sort Works

Merge Sort proceeds through the following steps:

1. Divide the list in half and recursively sort each sublist.
2. Merge the sorted sublists to create a single sorted list.

This process continues until the length of the list is 1, after which it is rearranged back together. The diagram below shows the basic flow of Merge Sort:

2. Implementation of Merge Sort

Let’s implement Merge Sort in C#. The basic implementation is as follows:

using System;

class MergeSort
{
    // Main method
    static void Main(string[] args)
    {
        int[] array = {38, 27, 43, 3, 9, 82, 10};

        Console.WriteLine("Before sorting: " + string.Join(", ", array));
        MergeSortAlgorithm(array, 0, array.Length - 1);
        Console.WriteLine("After sorting: " + string.Join(", ", array));
    }

    // Merge Sort algorithm
    static void MergeSortAlgorithm(int[] array, int left, int right)
    {
        if (left < right)
        {
            int mid = (left + right) / 2;

            // Division
            MergeSortAlgorithm(array, left, mid);
            MergeSortAlgorithm(array, mid + 1, right);

            // Merging
            Merge(array, left, mid, right);
        }
    }

    // Merge method
    static void Merge(int[] array, int left, int mid, int right)
    {
        // Create two sub-arrays
        int[] leftArray = new int[mid - left + 1];
        int[] rightArray = new int[right - mid];

        for (int i = 0; i < leftArray.Length; i++)
            leftArray[i] = array[left + i];

        for (int j = 0; j < rightArray.Length; j++)
            rightArray[j] = array[mid + 1 + j];

        int k = left;
        int a = 0;
        int b = 0;

        // Merging the arrays
        while (a < leftArray.Length && b < rightArray.Length)
        {
            if (leftArray[a] <= rightArray[b])
            {
                array[k] = leftArray[a];
                a++;
            }
            else
            {
                array[k] = rightArray[b];
                b++;
            }
            k++;
        }

        // Merging remaining elements
        while (a < leftArray.Length)
        {
            array[k] = leftArray[a];
            a++;
            k++;
        }

        while (b < rightArray.Length)
        {
            array[k] = rightArray[b];
            b++;
            k++;
        }
    }
}

2.1. Code Explanation

• MergeSortAlgorithm: This method divides the array in half and sorts it through recursive calls. After sorting the left and right sub-arrays, it calls the Merge method to merge them.
• Merge: This method receives two sub-arrays and merges them into a final sorted array. It uses pointers to compare the elements of the two sub-arrays and adds the smaller value to the final array.

3. Problem Example

Now let’s consider a simple problem where we can apply the Merge Sort algorithm.

Problem: Sort an Integer List

Write a method to sort the given list of integers in ascending order. The input consists of an array of integer values between 1 and 1,000,000, and can have up to 1,000 elements. Solve the problem using Merge Sort.

Input Example

{8, 3, 1, 7, 0, 10, 2}

Output Example

{0, 1, 2, 3, 7, 8, 10}

3.1. Problem Solving Process

To solve the above problem using the Merge Sort algorithm, we can use the previously written Merge Sort algorithm as is. Filling in the code here and testing with multiple input values will also be helpful.

using System;

class SortingExample
{
    static void Main(string[] args)
    {
        int[] array = {8, 3, 1, 7, 0, 10, 2};
        MergeSort(array);
        Console.WriteLine("Sorted array: " + string.Join(", ", array));
    }

    // Method to call Merge Sort
    static void MergeSort(int[] array)
    {
        MergeSortAlgorithm(array, 0, array.Length - 1);
    }

    // [Add the MergeSortAlgorithm and Merge methods here]
}

With the methods written like this, we can sort the given list of integers in ascending order. It is advisable to verify the algorithm’s validity through various tests with multiple input values.

4. Advantages and Disadvantages of Merge Sort

4.1. Advantages

• Stable sorting: Data with the same value is sorted while maintaining its original order.
• Predictable performance: Guarantees O(n log n) complexity even in the worst case.
• Handling large datasets: Consistent performance with large datasets and easy implementation for external sorting.

4.2. Disadvantages

• Additional space requirements: Requires additional memory for sorting.
• Inefficient for small data: Simple sorting methods may be faster for small datasets.

5. Conclusion

In this post, we explored the Merge Sort algorithm in detail. We looked at how it can be utilized in the actual problem-solving process through specific implementations. Merge Sort can effectively serve for efficient and stable sorting, making it a very useful tool for solving various algorithm problems. In the next post, we will cover various algorithms as well. Thank you!

Author: [Author Name] | Date: [Date]

Introduction

Algorithms play a very important role in coding tests. In particular, graph algorithms are one of the frequently encountered topics in evaluating problem-solving abilities. In this article, we will take a closer look at how to represent a graph using C# and the process of solving algorithm problems using graphs.

What is a Graph?

A graph is a data structure consisting of nodes (or vertices) and edges that represent the relationships between them. A graph can be divided into two main elements:

• Vertices: The nodes of the graph.
• Edges: The connections between the vertices.

A graph can be directed (directed graph) or undirected (undirected graph). It can also be classified as connected graph and disconnected graph.

Methods of Graph Representation

There are several ways to represent a graph, but the two commonly used methods are the Adjacency Matrix and the Adjacency List.

1. Adjacency Matrix

The adjacency matrix uses an n x n sized 2D array to represent the graph according to the number of vertices. If vertex i and vertex j are connected, it is set as matrix[i][j] = 1 (for a directed graph) or matrix[i][j] = matrix[j][i] = 1 (for an undirected graph). The advantage of the adjacency matrix is that it can check the existence of edges in O(1) time complexity. However, it may lead to memory waste in sparse graphs, where there are many vertices with few connections.

2. Adjacency List

The adjacency list uses a list of connected vertices for each vertex to represent the graph. Each vertex has a list containing the information of connected vertices, which uses less memory but takes O(V) (where V is the number of vertices) time to find vertices connected to a specific vertex. For graphs with a small number of vertices, the adjacency list is more advantageous than the adjacency matrix.

Algorithm Problem: Finding the Shortest Path

Problem Description

Given the node and edge information of a graph, implement an algorithm to find the shortest path distance from a specific starting node to all other nodes. This problem can be solved using Dijkstra’s algorithm.

Input Format

            - First line: Number of vertices V and number of edges E
            - From the second line: E lines of edge information u v w (weight w from vertex u to vertex v)
            - Last line: Starting vertex S
        

Sample Input

            5 6
            1 2 2
            1 3 3
            2 3 1
            2 4 4
            3 5 1
            4 5 2
            1
        

Sample Output

            0
            2
            3
            6
            4
        

Solution Process

Dijkstra’s algorithm proceeds by using a priority queue to select the node with the shortest distance found so far and updating the distances of the nodes adjacent to that node.

1. Initialize the graph in the form of an adjacency list.
2. Use a priority queue to initialize the distances from the starting vertex.
3. Select the vertex with the shortest distance from the priority queue and update the distances of all vertices connected to that vertex.
4. Repeat steps 2-3 until all vertices are processed.

C# Code Implementation

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

class Program
{
    static void Main(string[] args)
    {
        var input = Console.ReadLine().Split();
        int V = int.Parse(input[0]); // Number of vertices
        int E = int.Parse(input[1]); // Number of edges

        List> edges = new List>();
        for (int i = 0; i < E; i++)
        {
            var edgeInput = Console.ReadLine().Split();
            int u = int.Parse(edgeInput[0]) - 1; // 0-indexed
            int v = int.Parse(edgeInput[1]) - 1; // 0-indexed
            int w = int.Parse(edgeInput[2]);
            edges.Add(Tuple.Create(u, v, w));
        }
        
        int startVertex = int.Parse(Console.ReadLine()) - 1; // 0-indexed
        Dijkstra(V, edges, startVertex);
    }

    static void Dijkstra(int V, List> edges, int startVertex)
    {
        // Initialize the graph
        List>> graph = Enumerable.Range(0, V)
                                                        .Select(x => new List>())
                                                        .ToList();

        foreach (var edge in edges)
        {
            graph[edge.Item1].Add(Tuple.Create(edge.Item2, edge.Item3));
            graph[edge.Item2].Add(Tuple.Create(edge.Item1, edge.Item3)); // Undirected graph
        }

        // Initialize distance array
        int[] distances = new int[V];
        for (int i = 0; i < V; i++)
            distances[i] = int.MaxValue;
        distances[startVertex] = 0;

        // Initialize priority queue
        var priorityQueue = new SortedSet>();
        priorityQueue.Add(Tuple.Create(0, startVertex)); // (distance, vertex)

        while (priorityQueue.Any())
        {
            var current = priorityQueue.Min;
            priorityQueue.Remove(current);
            int currentDistance = current.Item1;
            int currentVertex = current.Item2;

            // Skip if a shorter path has already been found
            if (currentDistance > distances[currentVertex])
                continue;

            foreach (var neighbor in graph[currentVertex])
            {
                int neighborVertex = neighbor.Item1;
                int edgeWeight = neighbor.Item2;

                // Update distance
                if (distances[currentVertex] + edgeWeight < distances[neighborVertex])
                {
                    distances[neighborVertex] = distances[currentVertex] + edgeWeight;
                    priorityQueue.Add(Tuple.Create(distances[neighborVertex], neighborVertex));
                }
            }
        }

        // Output results
        for (int i = 0; i < V; i++)
        {
            if (distances[i] == int.MaxValue)
                Console.WriteLine("INF");
            else
                Console.WriteLine(distances[i]);
        }
    }
}
        

Conclusion

This course taught the basic concepts and methods of graph representation, and how to implement Dijkstra's algorithm in C# to solve the shortest path problem. Algorithm problems require continuous practice. I hope you find your own solutions by solving various problems.

Problem Description

This is a problem of finding the K-th shortest path between two given vertices in a graph. Common shortest path algorithms (such as Dijkstra’s algorithm, Bellman-Ford algorithm, etc.) find only one shortest path, but in this problem, we need to find the K-th shortest path between the given two vertices.

Input Format:

• The graph consists of vertices and edges, where each edge has a starting vertex, an ending vertex, and a weight.
• The number of vertices in the graph is N, the number of edges is M, and K is the rank of the shortest path to find.

Output Format:

• Print the length of the K-th shortest path. If the K-th shortest path does not exist, print -1.

Example

        Input: 
        4 5 2
        1 2 1
        1 3 2
        2 3 1
        2 4 3
        3 4 1

        Output:
        3
    

Problem Analysis

The algorithm used to solve this problem is a graph search utilizing a priority queue. It employs a modified approach to traditional shortest path algorithms to find the K-th shortest path. In particular, it explores the necessary paths using a combination of Dijkstra’s algorithm and a priority queue.

The process to solve the problem is as follows:

1. Receive the graph data and construct it in the form of an adjacency list.
2. Create a priority queue and start from the source vertex.
3. Explore paths using the priority queue and count the K-th shortest path.
4. Once the K-th shortest path is found, output its length.

C# Code Implementation

Below is the code implementing the above process in C#.

        
        using System;
        using System.Collections.Generic;

        class Program
        {
            static void Main(string[] args)
            {
                // Input
                var line = Console.ReadLine().Split();
                int N = int.Parse(line[0]); // Number of vertices
                int M = int.Parse(line[1]); // Number of edges
                int K = int.Parse(line[2]); // K-th shortest path

                // Initialize the graph
                var graph = new List<(int to, int cost)>[N + 1];
                for (int i = 0; i <= N; i++)
                {
                    graph[i] = new List<(int, int)>();
                }

                // Input edge information
                for (int i = 0; i < M; i++)
                {
                    line = Console.ReadLine().Split();
                    int a = int.Parse(line[0]);
                    int b = int.Parse(line[1]);
                    int cost = int.Parse(line[2]);
                    graph[a].Add((b, cost));
                }

                // Find the K-th shortest path
                var result = FindKthShortestPath(graph, N, K);
                Console.WriteLine(result);
            }

            static int FindKthShortestPath(List<(int to, int cost)>[] graph, int N, int K)
            {
                var pq = new SortedSet<(int cost, int node, int count)>();
                pq.Add((0, 1, 0)); // (cost, node, count)

                // List for the K-th shortest path
                var paths = new List[N + 1];
                for (int i = 0; i <= N; i++)
                {
                    paths[i] = new List();
                }

                while (pq.Count > 0)
                {
                    var (cost, node, count) = pq.Min;
                    pq.Remove(pq.Min);

                    paths[node].Add(cost);

                    // If the K-th shortest path is found, return
                    if (count == K - 1)
                    {
                        return cost;
                    }

                    // Explore edges
                    foreach (var edge in graph[node])
                    {
                        pq.Add((cost + edge.cost, edge.to, count + 1));
                    }
                }

                return -1; // If the K-th shortest path does not exist
            }
        }
        
        

Time Complexity Analysis

The time complexity of this algorithm is O((M + N) log N). The reasons are:

1. Adding and removing nodes from the priority queue takes log N time.
2. As it explores all edges and nodes, it performs O(M + N) iterations, which corresponds to the overall size of the graph.

Conclusion

In this lecture, we implemented code based on the basic concept of graph search to solve the problem of finding the K-th shortest path. By learning how to find the K-th shortest path through a modified approach to shortest path methods, I hope to foster strategic thinking in various algorithmic problems.

In the next lecture, we will cover more complex graph search problems. If you have any questions or feedback, please leave a comment!

Problem Description

Find all prime numbers less than or equal to the given natural number N.

A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself. For example, 2, 3, 5, 7, 11, 13, 17, 19 are prime numbers.

Input

A natural number N (2 ≤ N ≤ 10,000,000)

Output

Print all prime numbers less than or equal to N, one per line

Example

Input:
10

Output:
2
3
5
7

Problem Solving Strategy

One of the most well-known algorithms for finding prime numbers is the Sieve of Eratosthenes. This algorithm helps efficiently find all prime numbers within a given range.

The Sieve of Eratosthenes algorithm works as follows:

1. Create an array containing all numbers from 2 to N.
2. Since 2 is prime, remove all multiples of 2 from the array as they cannot be prime.
3. Next, select the first remaining prime number, which is 3, and remove all multiples of 3.
4. Repeat this process until the end of the array. The remaining numbers are primes.

C# Implementation

Let’s implement a program to find prime numbers in C# using the above method:

using System;

class Program
{
    static void Main(string[] args)
    {
        // Get N from the user
        Console.Write("Enter a natural number N (2 ≤ N ≤ 10,000,000): ");
        int N = int.Parse(Console.ReadLine());

        // Initialize a vector array for prime checking
        bool[] isPrime = new bool[N + 1];

        // Initialize all numbers as prime
        for (int i = 2; i <= N; i++)
        {
            isPrime[i] = true;
        }

        // Sieve of Eratosthenes algorithm
        for (int i = 2; i * i <= N; i++)
        {
            if (isPrime[i])
            {
                // Set multiples of i to false
                for (int j = i * i; j <= N; j += i)
                {
                    isPrime[j] = false;
                }
            }
        }

        // Print results
        Console.WriteLine($"The following are prime numbers less than or equal to {N}:");
        for (int i = 2; i <= N; i++)
        {
            if (isPrime[i])
            {
                Console.WriteLine(i);
            }
        }
    }
}

Code Explanation

• Getting Input: Requests the user to input N. Converts the received value to an integer.
• Initializing Prime Array: Creates a boolean array initialized to true, assuming all numbers up to N are prime.
• Implementing Sieve of Eratosthenes: Uses two nested loops to set non-prime numbers to false. The outer loop starts from 2, and the inner loop sets multiples of i to false.
• Outputting Results: Finally, finds indices in the array that are still true and outputs the corresponding prime numbers.

Complexity Analysis

The time complexity of this algorithm is O(n log log n) and its space complexity is O(n). This makes it very efficient for finding large ranges of prime numbers.

Conclusion

In this course, we introduced an algorithm for finding prime numbers and explained how to implement it using C#. The Sieve of Eratosthenes is a very efficient prime detection algorithm that often appears in actual coding tests. Understanding the concept of prime numbers and implementing the algorithm will greatly enhance your programming skills.