Category: Kotlin coding test

Overview

Topological Sort is an algorithm for linearly ordering vertices in a directed graph. This algorithm is mainly used for problems that express dependencies of tasks. For example, it is useful for solving various problems such as course prerequisites, task scheduling, etc.

Problem Description

The following is a problem utilizing Topological Sort.

Problem: Course Prerequisite Problem

In university, to complete course A, courses B and C must be completed first. Given several courses and completion conditions, write a program in Kotlin to determine the order of classes required to complete all courses. There can be multiple valid class orders. The goal is to return all possible class orders.

Input Format

• The first line contains an integer N (1 ≤ N ≤ 20): the number of courses.
• The second line contains an integer M (0 ≤ M ≤ 100): the number of prerequisite pairs.
• The next M lines contain two integers in the form of ‘A B’, meaning that to finish course ‘A’, course ‘B’ must be completed first.

Output Format

Output the order of course completion in a single line separated by spaces. If there are multiple valid orders of completion, only output the lexicographically smallest course order.

Solution Process

1. Understanding the Problem

To solve the problem, we must first understand the concept of Topological Sort. In the graph, vertices represent courses, and edges represent prerequisites. We can construct a directed graph that indicates which courses must be completed in order to take others.

2. Constructing the Graph

Based on the given courses and prerequisites, construct the graph. Each course becomes a node, and prerequisites are represented as directed edges.

val graph = mutableMapOf>()
val inDegree = IntArray(N + 1) // Stores the in-degree of each course

3. Calculating In-Degree

Calculate the in-degree of each course. The in-degree represents the number of courses that must be completed before reaching that course.

for (i in 0 until M) {
    val a = readLine()!!.split(' ').map { it.toInt() }
    graph.getOrPut(a[1]) { mutableListOf() }.add(a[0])
    inDegree[a[0]]++
}

4. Implementing Topological Sort Algorithm

Topological Sort can be implemented using BFS. Starting from nodes with an in-degree of 0, visit these nodes in order while decrementing their in-degrees. If any node’s in-degree becomes 0 during this process, add it to the queue.

fun topologicalSort(N: Int): List {
    val result = mutableListOf()
    val queue: Queue = LinkedList()

    // Add nodes with in-degree of 0 to the queue
    for (i in 1..N) {
        if (inDegree[i] == 0) {
            queue.add(i)
        }
    }

    while (queue.isNotEmpty()) {
        // Remove vertex from queue for lexicographical sorting
        val current = queue.poll()
        result.add(current)

        // Process the outgoing edges from the current vertex
        for (next in graph[current] ?: listOf()) {
            inDegree[next]--
            if (inDegree[next] == 0) {
                queue.add(next)
            }
        }
    }

    return result
}

5. Final Code

The final code including the Topological Sort functionality is as follows.

fun main() {
    val (N, M) = readLine()!!.split(' ').map { it.toInt() }

    val graph = mutableMapOf>()
    val inDegree = IntArray(N + 1)

    // Initialize graph and in-degrees
    for (i in 0 until M) {
        val (a, b) = readLine()!!.split(' ').map { it.toInt() }
        graph.getOrPut(b) { mutableListOf() }.add(a)
        inDegree[a]++
    }

    // Perform Topological Sort
    val result = topologicalSort(N)
    
    // Output the result
    println(result.joinToString(" "))
}

Conclusion

Topological Sort is a very useful algorithm for solving various graph problems. It shines especially in situations where dependencies must be taken into account, such as in course prerequisite problems. In this lesson, we examined the basic concepts of Topological Sort and followed a step-by-step problem-solving process. I hope you continue to enhance your Kotlin skills through various algorithm problems.

Problem Description

Write a program to find a specific integer in a given integer array. The function has the following signature:

fun findNumber(arr: IntArray, target: Int): Boolean

The input arr is an integer array, and target is the integer we want to find.
If target exists in the array, it should return true, otherwise it should return false.

Example

Input

arr = [1, 2, 3, 4, 5]
target = 3

Output

true

Input

arr = [1, 2, 3, 4, 5]
target = 6

Output

false

Solution Approach

To solve this problem, we need to search the array to check if the target number exists. There are several array search algorithms, but here we will use the most basic linear search.
By sequentially checking each element of the array, we return true when the target number is found.

If we check all the way to the end of the array, we return false. This approach has a time complexity of O(n), which increases with the length of the array.
However, if the array is sorted, we can use a binary search algorithm to reduce the time complexity to O(log n). For simplicity, we will implement linear search here.

Code Implementation

Now, let’s write code in Kotlin to solve this problem.

fun findNumber(arr: IntArray, target: Int): Boolean {
        for (number in arr) {
            if (number == target) {
                return true
            }
        }
        return false
    }

Code Explanation

The code above runs a loop on all elements of the array arr. It compares each element with target, and if they are the same, it returns true.
If target is not found by the end of the loop, it returns false.

Complexity Analysis

The time complexity of this algorithm is O(n). This is because the time taken to search increases proportional to the size n of the array.
The space complexity is O(1) since no additional memory is used. This means it has optimal space complexity.

Test Cases

Additional Test Cases

val testArray = intArrayOf(10, 20, 30, 40, 50)
println(findNumber(testArray, 30)) // true
println(findNumber(testArray, 60)) // false
println(findNumber(intArrayOf(), 1)) // false
println(findNumber(intArrayOf(5), 5)) // true
println(findNumber(intArrayOf(5), 10)) // false

Conclusion

Through this example, we learned how to write a simple search algorithm using Kotlin. Linear search is the most basic rule of integration,
and it is important to choose the appropriate algorithm according to the amount of data and complexity in actual projects.
This helps develop the ability to solve various types of problems.

Hello, in this lecture we will learn how to solve the Traveling Salesman Problem using Kotlin.

1. Problem Definition

The Traveling Salesman Problem is the problem of finding the shortest possible route that visits each city once and returns to the original city. The input consists of the travel costs between cities, and the goal is to output a route that visits all cities at the minimum cost.

2. Problem Approach

The Traveling Salesman Problem is known to be NP-hard. Common solutions include brute force, dynamic programming, binary search, and greedy algorithms. However, in special cases dealing with small datasets, it can be solved using brute force.

The approach to solving this problem is as follows:

1. Represent the distances or costs between all cities in a table format.
2. Generate all possible routes.
3. Calculate the total cost of each route to find the minimum value.

3. Kotlin Code for Problem Solving

Now let’s write a code to solve this problem using Kotlin. The code below demonstrates a basic approach to solving the Traveling Salesman Problem:

fun main() {
    val n = 4 // Number of cities
    val cost = arrayOf(
        intArrayOf(0, 10, 15, 20),
        intArrayOf(10, 0, 35, 25),
        intArrayOf(15, 35, 0, 30),
        intArrayOf(20, 25, 30, 0)
    )

    val visited = BooleanArray(n)
    visited[0] = true // Set the starting point to the first city
    val result = tsp(0, 1, cost, visited, 0, n)
    println("Minimum cost is: $result")
}

fun tsp(current: Int, count: Int, cost: Array, visited: BooleanArray, totalCost: Int, n: Int): Int {
    if (count == n) {
        return totalCost + cost[current][0] // Return to the starting city after visiting all cities
    }

    var minCost = Int.MAX_VALUE
    
    for (i in 0 until n) {
        if (!visited[i]) { // If the city has not been visited
            visited[i] = true // Mark city as visited
            val newCost = tsp(i, count + 1, cost, visited, totalCost + cost[current][i], n)
            minCost = Math.min(minCost, newCost) // Calculate minimum cost
            visited[i] = false // Backtracking
        }
    }
    
    return minCost
}

4. Code Explanation

The above code uses a simple recursive approach to solve the Traveling Salesman Problem. The structure of each function is as follows:

• main function: Initializes the number of cities and the cost array. Calls the tsp function to compute the minimum route.
• tsp function: Takes current city, number of visited cities, cost array, visitation record, total cost so far, and number of cities as parameters. If all cities have been visited, it returns the cost to return to the starting city along with the minimum cost.

5. Process Overview

A brief look at how the code works:

1. Organizes the given cities in an array (cost) format.
2. Starts from the first city and recursively explores all possible routes.
3. Calculates the total cost for each route and updates the minimum cost.
4. Returns the cost of the current route every time all cities are visited.

6. Conclusion

In this session, we learned how to solve the Traveling Salesman Problem using Kotlin. This problem is a very important case in computer science and algorithm education, and understanding it will greatly help in learning various optimization problems. Furthermore, for large-scale problems, it is essential to learn significant techniques such as dynamic programming.

In the next lecture, we will cover more advanced algorithms and various problem-solving techniques. Thank you!

1. Introduction

There are various algorithm problems to prepare for coding tests. Among them, many problems require mathematical thinking. Today, we will learn about Euler’s Totient Function. The Euler’s Totient Function returns the count of integers that are coprime to n among the integers from 1 to n. This function plays a very important role in number theory and is frequently used in cryptographic algorithms.

2. Understanding Euler’s Totient Function

The Euler’s Totient Function φ(n) has the following properties:

• φ(1) = 1
• When p is a prime number, φ(p) = p – 1
• When p is a prime and k is a natural number, φ(p^k) = p^k – p^(k-1)
• If two numbers are coprime, φ(m * n) = φ(m) * φ(n)

The most common method to calculate Euler’s Totient Function is through prime factorization. You can obtain the value through the prime factorization of the given integer n. For example, if n = 12, the prime factorization can be expressed as 2^2 * 3^1, and to find the value of φ(12), the following formula can be used.

φ(n) = n * (1 – 1/p₁) * (1 – 1/p₂) * … * (1 – 1/pₖ)

Here, p₁, p₂, …, pₖ are the prime factors of n. Therefore, for 12, φ(12) is calculated as follows:

φ(12) = 12 * (1 – 1/2) * (1 – 1/3) = 12 * 1/2 * 2/3 = 4

3. Problem Definition

This problem involves implementing a Kotlin function that returns the value of φ(n) for a given integer n. This problem requires not only calculating the value of φ(n) but also considering the efficiency of the algorithm.

**Problem**: Given a natural number n, implement a function in Kotlin that returns the value of Euler’s Totient Function φ(n).

4. Problem Solving Process

4.1 Algorithm Design

An efficient way to calculate Euler’s Totient Function is through prime factorization. The algorithm consists of the following steps:

1. Set the initial value of result to n for the given natural number n.
2. For each integer p from 2 to the square root of n:
3. If p is a prime factor of n, set result = result * (1 – 1/p) and divide n by p.
4. If n is greater than 1 at the end, treat it as a prime and calculate result = result * (1 – 1/n).
5. Return result.

4.2 Coding

    
    fun eulerTotient(n: Int): Int {
        var result = n
        var p: Int = 2
        var tempN = n

        while (p * p <= tempN) {
            if (tempN % p == 0) {
                // If p is a prime factor
                while (tempN % p == 0) {
                    tempN /= p
                }
                result *= (p - 1)
                result /= p
            }
            p++
        }

        // Remaining prime
        if (tempN > 1) {
            result *= (tempN - 1)
            result /= tempN
        }

        return result
    }
    
    

4.3 Code Explanation

The above code implements Euler’s Totient Function through the following process:

1. Initialize the variable result to n to store the value of φ(n).
2. p starts from 2 and iterates over all integers up to the square root of n.
3. If n is divisible by p, then p is a prime factor of n.
4. Perform complete division of n by p and update the result.
5. After processing all prime factors, if n is greater than 1, reflect n as the only prime in the result.

5. Performance Analysis

The above algorithm has a time complexity of O(√n) and is therefore very efficient. It can quickly compute φ(n) even with large amounts of data. Performance is not an issue even for large numbers like 1,000,000.

6. Examples

Here are some examples of using the function:

    
    fun main() {
        println("φ(1) = " + eulerTotient(1)) // 1
        println("φ(12) = " + eulerTotient(12)) // 4
        println("φ(13) = " + eulerTotient(13)) // 12
        println("φ(30) = " + eulerTotient(30)) // 8
        println("φ(100) = " + eulerTotient(100)) // 40
    }
    
    

7. Conclusion

Today, we learned about Euler’s Totient Function and how to implement it in Kotlin. This problem is often encountered in coding tests and requires both mathematical thinking and algorithmic approaches, so practice is necessary. Validate the implemented function through various test cases and try tackling extended problems as well.

Through problem-solving tutorials like this, I hope to share knowledge with more people and grow together.

8. References

• Concrete Mathematics: A Foundation for Computer Science by Ronald L. Graham, Donald E. Knuth, and Oren Patashnik
• Introduction to Algorithms by Thomas H. Cormen et al.
• Number Theory: A Modern Introduction by Andrew P. Erdos

One of the problems that frequently appears in programming and algorithm tests is the ‘Next Greater Element’ problem. This problem requires an understanding of efficient algorithms and data structures, and it can be very useful in various real programming situations.

Problem Description

Problem: For each number in a given integer array, find the next greater number that appears to the right, and output that number. If it does not exist, output -1.

Input Format

• The first line contains a natural number N (1 ≤ N ≤ 1,000,000).
• The second line contains an array of N integers. The values are from 1 to 1,000,000.

Output Format

Output an array consisting of N integers representing the next greater elements for each number.

Example

Input

    4
    3 5 2 7
    

Output

    5 7 -1 -1
    

How to Solve the Problem

To solve this problem, we will utilize the stack data structure. A stack is a LIFO (Last In, First Out) structure, which means that the last element added is the first one to be removed. By using this structure, we can efficiently find the next greater element for each element.

Algorithm Explanation

1. Create a stack. This stack will store indices.
2. Traverse the given array.
3. If the current number is greater than the number at the top of the stack, pop indices from the stack and store the current number as the next greater element at those indices.
4. Add the current index to the stack.
5. After repeating this process for all numbers, any remaining indices in the stack indicate there is no next greater element, so store -1 for those indices.

Kotlin Code Implementation

fun findNextGreater(nums: IntArray): IntArray {
    val result = IntArray(nums.size) { -1 }  // Initialize result array
    val stack = mutableListOf()  // Create stack

    for (i in nums.indices) {
        // While stack is not empty and current number is greater than the top of the stack
        while (stack.isNotEmpty() && nums[stack.last()] < nums[i]) {
            result[stack.removeAt(stack.size - 1)] = nums[i]  // Store next greater element
        }
        stack.add(i)  // Add current index
    }
    
    return result
}

fun main() {
    val inputArray = intArrayOf(3, 5, 2, 7)
    val result = findNextGreater(inputArray)

    print(result.joinToString(" "))  // Print result
}
    

Code Explanation

The code above is an implementation of the algorithm to find the next greater element in Kotlin. Let's examine the main parts.

1. Initializing the Result Array

The result array is intended to store the next greater elements. It is initialized to -1 by default. This is to handle cases where there is no next greater element.

2. Searching Using a Stack

When the top index of the stack points to a value that is less than the current index i, we pop that index and assign the current number to the result array at that index. This process helps us find the next greater element.

3. Final Result Output

After searching through all numbers, we output the final result array. The result is printed with the next greater elements for each number in the given array.

Performance Analysis

The time complexity of this method is O(N). It is efficient since each element is pushed and popped from the stack only once. The space complexity is O(N) because the stack and the result array are used, meaning the memory used is proportional to the input size.

Conclusion

Today we learned how to solve the Next Greater Element problem using Kotlin. I hope you have felt the importance of data structures and algorithms, and I encourage you to continue practicing to enhance your algorithm problem-solving skills.