Kotlin coding test 보관 - Page 7 of 28

Kotlin coding test course, finding the least common multiple

One common algorithm problem that frequently appears in coding tests is finding the ‘Least Common Multiple (LCM)’. The least common multiple refers to the smallest common multiple found among the multiples of two given numbers. In this article, we will implement an algorithm to calculate the least common multiple in Kotlin.

Problem Description

Given two integers 𝑎 and 𝑏, please write a function to find their least common multiple. The function signature is as follows:

fun lcm(a: Int, b: Int): Int

For example, the least common multiple of 4 and 6 is 12, and the least common multiple of 15 and 20 is 60. The input range is integers between 1 and 10⁶.

Finding the Least Common Multiple

The least common multiple can be calculated by dividing the product of the two numbers by their greatest common divisor (GCD). The least common multiple is defined by the following formula:

LCM(a, b) = (a * b) / GCD(a, b)

To calculate the least common multiple using the above formula, we must first determine the greatest common divisor of the two numbers. We can use the Euclidean algorithm for this purpose.

Explanation of the Euclidean Algorithm

The Euclidean algorithm is an efficient method to find the greatest common divisor of two numbers. For two numbers 𝑎 and 𝑏, the process proceeds as follows when 𝑏 is not 0:

Find the remainder of 𝑎 divided by 𝑏.
Assign 𝑏 to 𝑎.
Assign the remainder to 𝑏.
Repeat until 𝑏 becomes 0.

Finally, return the value of 𝑎 as the greatest common divisor.

Kotlin Implementation

Now, let’s implement a function in Kotlin to calculate the least common multiple based on the above algorithm.

fun gcd(a: Int, b: Int): Int {
        return if (b == 0) a else gcd(b, a % b)
    }

    fun lcm(a: Int, b: Int): Int {
        return (a * b) / gcd(a, b)
    }
    
    fun main() {
        val a = 4
        val b = 6
        println("Least Common Multiple: ${lcm(a, b)}")  // Output: Least Common Multiple: 12
    }

Function Descriptions

The code above includes two functions:

gcd(a: Int, b: Int): Int – A function that calculates the greatest common divisor. It repeatedly calculates the remainder until it reaches 0.
lcm(a: Int, b: Int): Int – A function that calculates the least common multiple by dividing the product of the two numbers by their greatest common divisor.

Complexity Analysis

The time complexity of the Euclidean algorithm is O(log min(a, b)). This makes it a much faster method for calculating the greatest common divisor based on the size of the two numbers. Therefore, the overall time complexity of the algorithm for finding the least common multiple is also O(log min(a, b)).

Test Cases

Let’s look at some test cases to verify if the function works correctly:

lcm(4, 6): 12
lcm(15, 20): 60
lcm(7, 5): 35
lcm(1, 999999): 999999
lcm(123456, 789012): 493827156

The results of each function can help validate the correctness of the logic.

Conclusion

We have learned how to solve the problem of finding the least common multiple using Kotlin. We examined how to efficiently calculate the greatest common divisor using the Euclidean algorithm and how to use it to find the least common multiple. Such algorithms frequently appear in coding tests, so it’s advisable to study and practice them thoroughly.

kotlin coding test course, finding the greatest common divisor

Hello! In this session, we will delve into an algorithm problem that calculates the Greatest Common Divisor (GCD) using Kotlin. The GCD refers to the largest divisor that two or more integers share. This problem is one of those often encountered in programming interviews. Let’s take a look at the problem.

Problem Description

Given two integers A and B, write a function to calculate the GCD of these two numbers. For example, if A and B are 48 and 18 respectively, the GCD is 6.

Input Format

The first line contains the integer A. (1 ≤ A ≤ 10⁹)
The second line contains the integer B. (1 ≤ B ≤ 10⁹)

Output Format

Print the GCD of the two integers.

Problem Approach

There are several ways to find the GCD, but among them, the Euclidean algorithm is the most famous and efficient method. The Euclidean algorithm is based on the following principle:

GCD(A, B) = GCD(B, A % B) (until B becomes 0)
GCD(A, 0) = A

In other words, given two numbers A and B, we find the remainder of A divided by B, and during this process, when B becomes 0, we can identify that A is the GCD. This algorithm can find the GCD very quickly, proportional to the size of the two numbers.

Kotlin Implementation

Now, let’s implement the above algorithm in Kotlin. The code example is as follows:

fun gcd(a: Int, b: Int): Int {
    return if (b == 0) a else gcd(b, a % b)
}

fun main() {
    val a = readLine()!!.toInt()
    val b = readLine()!!.toInt()
    println(gcd(a, b))
}

The code above takes two integers as input and computes the GCD using the function, then prints the result.

Detailed Code Explanation

1. Function Definition

First, we define a function named gcd. This function takes two integers a and b as parameters.

2. Termination Condition

Inside the function, we check whether b is 0. If b is 0, the GCD is a, so we return a.

3. Recursive Call

If not, we recursively call gcd(b, a % b). This process continues until b becomes 0, calculating the GCD.

4. Main Function

In the main function, we use readLine() to take input of two integers from the user. This input is guaranteed to be non-null using !! and is converted to an integer type using toInt(). Finally, we call println(gcd(a, b)) to print the result.

Test Cases

Now, let’s verify whether this algorithm works correctly through test cases. Below are some sample test cases:

Test Case Number	A	B	Expected Output
1	48	18	6
2	56	98	14
3	101	10	1
4	7	13	1

Code Optimization

The implementation above is simple and easy to understand. However, it can also be implemented in a more optimized way. By using Kotlin’s built-in functions and APIs, we can achieve more concise code and better performance. For example, in Kotlin, you can also use the gcd function from the Math class. This can make the code more succinct:

fun main() {
    val a = readLine()!!.toInt()
    val b = readLine()!!.toInt()
    println(Math.gcd(a, b)) // This method is used in Java 8 and above
}

Conclusion

In this lecture, we explored a problem on calculating the GCD using Kotlin. We learned that it can be solved with a simple yet efficient method using the Euclidean algorithm.

It is important to encounter various problems while preparing for coding tests and to develop algorithmic thinking through the process of solving these problems. To succeed in your next coding test, you should implement actual code and test it in different scenarios.

If you have any further questions or requests for topics, please leave a comment! Thank you for reading!

kotlin coding test course, finding the shortest path

Problem Description

Finding the shortest path from a specific starting point to all other vertices is a very important problem in graph theory.
Various algorithms can be used to solve this problem, including Dijkstra’s algorithm, Bellman-Ford algorithm, and Floyd-Warshall algorithm.

In this lecture, we will focus on Dijkstra’s algorithm to address the problem of finding the shortest path.
The specific form of the problem is as follows.

After constructing a directed graph with the given edges, find the shortest path from the starting vertex to all other vertices.
Input consists of the number of vertices N and the number of edges M,
and each edge consists of the starting vertex A, the destination vertex B, and the weight C.

Example Problem

Input example:

Output example:

Here, the first line represents the number of vertices (N) and the number of edges (M),
and from the next line, the information of each edge is presented.
The starting vertex is 1, and 0 means the shortest path to itself.

Problem Solving Process

1. Overview of Dijkstra’s Algorithm

Dijkstra’s algorithm is an algorithm for finding the shortest path from the starting vertex to all other vertices in a graph.
This algorithm is valid for graphs with non-negative weights and is generally implemented using a priority queue.

The basic idea of this algorithm is to update the paths between vertices that have not yet had their shortest paths calculated based on the shortest path found so far at each step.

2. Steps of the Algorithm

Initialize the distances from the starting vertex to all vertices to infinity, except for the starting vertex which is initialized to 0.
Select the currently closest vertex using a priority queue.
Update the distance values of adjacent vertices using the distance of the selected vertex.
Repeat steps 2 and 3 until the distances of all vertices are finalized.

3. Kotlin Code Implementation

Now, let’s implement this process in Kotlin. Below is the code that solves the given problem using Dijkstra’s algorithm.

                
                    import java.util.PriorityQueue
                    import kotlin.math.min

                    data class Edge(val target: Int, val weight: Int)

                    fun dijkstra(n: Int, edges: List>, start: Int): IntArray {
                        val graph = MutableList(n + 1) { mutableListOf() }
                        for ((a, b, c) in edges) {
                            graph[a].add(Edge(b, c))
                        }

                        val distances = IntArray(n + 1) { Int.MAX_VALUE }
                        distances[start] = 0

                        val priorityQueue = PriorityQueue>(compareBy { it.first })
                        priorityQueue.add(0 to start)

                        while (priorityQueue.isNotEmpty()) {
                            val (dist, current) = priorityQueue.poll()

                            if (dist > distances[current]) continue

                            for (edge in graph[current]) {
                                val newDist = dist + edge.weight
                                if (newDist < distances[edge.target]) {
                                    distances[edge.target] = newDist
                                    priorityQueue.add(newDist to edge.target)
                                }
                            }
                        }

                        return distances
                    }

                    fun main() {
                        val input = readLine()!!.split(" ").map { it.toInt() }
                        val n = input[0]
                        val m = input[1]

                        val edges = mutableListOf>()
                        for (i in 0 until m) {
                            val edgeInput = readLine()!!.split(" ").map { it.toInt() }
                            edges.add(Triple(edgeInput[0], edgeInput[1], edgeInput[2]))
                        }

                        val distances = dijkstra(n, edges, 1)

                        for (i in 1..n) {
                            println(if (distances[i] == Int.MAX_VALUE) "INF" else distances[i])
                        }
                    }

In the above code, the dijkstra function takes the number of vertices and edge information as input and calculates the shortest path from the starting vertex.
The distances array stores the shortest path distances to each vertex, initially set to infinity.

After processing the given input, the main function outputs the distances array.
If there are vertices that cannot be reached, they are marked as “INF”.

Testing and Verification

After implementing the algorithm, various test cases should be conducted to verify the accuracy of the code.
For example, consider the following additional test case:

The operation result should be as follows:

Verify the accuracy by providing actual input and comparing the output of the code.
It is also important to consider various scenarios and handle edge cases.

Conclusion

In this lecture, we covered the problem of finding the shortest path using Dijkstra’s algorithm.
We passed through the process of implementing the algorithm in Kotlin, connecting theoretical background with actual implementation.
While preparing for coding tests, learn various algorithms and data structures to enhance your problem-solving capabilities.

Kotlin coding test course, representing sets

Hello! In this session, we will cover the topic of set expressions, which frequently appear in coding tests using Kotlin. Through the problems I present, I will clarify the concept of sets and explain how sets can be utilized in Kotlin.

Problem Description

Here is the description of the problem:

When a set of integers is given, write a function that finds all subsets of that set and returns the number of unique sums of each subset. (The sum of subsets does not allow duplicates)

Input: A set of integers {a1, a2, …, an} (1 ≤ n ≤ 20, 1 ≤ a ≤ 100)

Output: The number of unique sums

Input Example

Input: {1, 2, 3}

Output: 7

Problem Analysis

To understand this problem, one must first know the concepts of sets and subsets. A set is a collection of distinct objects where no duplicate objects are allowed. A subset is a set that includes some or all elements of the given set.

For example, all subsets of the set {1, 2, 3} are as follows:

{}
{1}
{2}
{3}
{1, 2}
{1, 3}
{2, 3}
{1, 2, 3}

To solve this, we need to find the sum of each of these subsets and count the unique values of these sums. However, it is important to note that we should not count duplicate sums.

Solution Process

Step 1: Creating Subsets

We can use a recursive approach to create subsets. Since each element can either be included or not included, binary flags can be used. We construct subsets using combinations of indices.

Step 2: Calculating the Sum of Subsets

Next, we calculate the sum of each created subset. To ensure that sums do not duplicate, we can use a HashSet.

Step 3: Returning the Count of Unique Sums

Finally, we return the count of the stored sums.

Code Implementation

Based on the above process, let’s write the code.

fun uniqueSubsetSums(nums: IntArray): Int {
    val sums = mutableSetOf()

    fun backtrack(index: Int, currentSum: Int) {
        if (index == nums.size) {
            sums.add(currentSum)
            return
        }
        // Include element
        backtrack(index + 1, currentSum + nums[index])
        // Exclude element
        backtrack(index + 1, currentSum)
    }

    backtrack(0, 0)
    return sums.size
}

fun main() {
    val input = intArrayOf(1, 2, 3)
    println(uniqueSubsetSums(input)) // Output: 7
}

Code Explanation

The above code works as follows:

The uniqueSubsetSums function calculates the unique sums of all subsets of the input integer array nums.
A set is created to store sums using mutableSetOf().
The backtrack function is called recursively to handle two cases for each index: including or excluding the element.
After iterating through all subsets, sums.size is returned to output the count of unique sums.

Conclusion

In this lesson, we looked at how to express sets using Kotlin and how to solve the problem to find the count of unique sums through subsets. I hope that encountering this type of problem, which often appears in coding tests, enhances your understanding of algorithms. I will continue to present various problems in the future. Thank you!

Kotlin coding test course, line ordering

Coding tests are one of the important processes in modern software development. In particular, many companies conduct coding tests to evaluate algorithm and problem-solving abilities. In this course, we will cover the topic of ‘Sorting’, and through this, we will deeply understand the algorithm problem-solving process using the Kotlin language.

Problem Description

A series of students must line up according to their height. Each student has their own height, and the line should be arranged based on this height. You are required to write a program that sorts these students in ascending order of their heights when their height information is given.

Input Format

First line: Number of students N (1 ≤ N ≤ 100,000)
Next N lines: Each student’s height H (1 ≤ H ≤ 2,000)

Output Format

Print each student’s height in ascending order, one per line.

Example Input

Example Output

Problem Solving Strategy

This problem is about sorting students’ heights, and can be solved through sorting algorithms. A hint is to use Kotlin’s sort() function or sorted() function to solve the problem. Additionally, you should consider the time complexity of various sorting algorithms to choose the optimal method.

Step 1: Collecting Input Data

We will use standard input to collect the number of students and each student’s height. Kotlin supports concise code writing, allowing us to do this efficiently.

Step 2: Sorting Data

The sort() function is the easiest and most convenient method to apply for sorting. This function internally uses the Timsort algorithm and has an average performance of O(N log N). The code below describes how to sort students’ heights using this function.

Step 3: Outputting Results

We will go through the process of printing each sorted result line by line. This can be easily implemented using Kotlin’s looping constructs.

Kotlin Code Implementation

The following code is based on the steps described above for a Kotlin program.


fun main() {
    val n = readLine()!!.toInt()  // Input number of students from the first line
    val heights = mutableListOf()  // List to store students' heights

    // Receive height inputs
    for (i in 1..n) {
        heights.add(readLine()!!.toInt())
    }

    // Sort heights
    heights.sort()

    // Output sorted results
    heights.forEach { height -> 
        println(height) 
    }
}

Code Explanation

readLine()!!.toInt(): Reads a value from standard input and converts it to an integer.
mutableListOf(): Creates a mutable list to store students’ heights.
heights.sort(): Sorts the list.
heights.forEach(): A loop to print the sorted results.

Results and Performance Analysis

The time complexity of this code is O(N log N), making it efficient for handling large numbers of students. Additionally, the code’s readability is high, making maintenance easier.

Test Cases

Through various inputs, the stability of the program can be verified. For example, consider adding test cases for students with the same height or those sorted in reverse order.

Conclusion

In this course, we explored how to solve the sorting problem using Kotlin. I hope this has provided an opportunity to further develop your algorithm problem-solving skills through the processes of input handling, data sorting, and result output. The next course will cover more challenging problems.