Author: root

Hello! Today we will learn about one of the mathematical algorithms, the Extended Euclidean Algorithm. This course is designed to help you prepare for algorithm exams by explaining problem-solving methods in detail based on algorithmic thinking, and it can be implemented in Swift.

1. What is the Euclidean Algorithm?

The Euclidean algorithm is a classical algorithm for finding the greatest common divisor (GCD) of two numbers \(a\) and \(b\). The process is as follows:

GCD(a, b) = GCD(b, a % b)

This expression continues to repeat until \(b\) becomes 0, and \(GCD(a, 0) = a\) holds. In other words, the value remaining in the first argument is the GCD of the two numbers.

2. What is the Extended Euclidean Algorithm?

The Extended Euclidean Algorithm builds upon the Euclidean Algorithm to find the following expression for two integers \(a\) and \(b\):

ax + by = gcd(a, b)

Here, \(x\) and \(y\) are integers, commonly known as Bézout’s identity. Using this algorithm, you can find not only the GCD of the given two numbers but also the coefficients for the GCD.

3. Problem Description

Now, let’s look at a problem that can be solved using the Extended Euclidean Algorithm:

Problem: Given two integers a and b, find x and y that satisfy ax + by = gcd(a, b).

Input Format

• Two integers \(a\) and \(b\) are given. (1 ≤ a, b ≤ 1,000,000)

Output Format

• Output GCD(a, b), x, and y separated by spaces.

Example Input

30 12

Example Output

6 1 -2

4. Algorithm Solution Process

4.1. Problem Analysis

To solve this problem, we need to find the GCD of the given two numbers and the coefficients x and y to find that GCD. For this, we need to implement the Extended Euclidean Algorithm.

4.2. Algorithm Flowchart

1. Receive two numbers \(a\) and \(b\) as input.
2. Find the GCD using the Euclidean Algorithm.
3. Use the Extended Euclidean Algorithm to find the coefficients x and y for the linear combination.
4. Output the result.

4.3. Swift Implementation

Now let’s implement the above process in Swift code:

func extendedGCD(a: Int, b: Int) -> (gcd: Int, x: Int, y: Int) {
    if b == 0 {
        return (a, 1, 0)
    } else {
        let (gcd, x1, y1) = extendedGCD(a: b, b: a % b)
        let x = y1
        let y = x1 - (a / b) * y1
        return (gcd, x, y)
    }
}

func main() {
    let input = readLine()!.split(separator: " ").map { Int($0)! }
    let a = input[0]
    let b = input[1]
    let (gcd, x, y) = extendedGCD(a: a, b: b)
    print("\(gcd) \(x) \(y)")
}

// Program entry point
main()

5. Example Problem Solution

Let’s use the above Swift code to solve the given problem.

Input

30 12

Output

6 1 -2

For the above input, the GCD is 6, which can be confirmed with \(30x + 12y = 6\) where \(x = 1\) and \(y = -2\).

6. Conclusion

Today, we learned about the Extended Euclidean Algorithm and how to solve a given problem using it. This algorithm plays an important role in computer science and cryptography. Remember that it can be effectively used in various applications!

I hope you continue to enhance your coding skills through various algorithm-related courses. If you have any questions or want to learn more, please leave a comment!

In this lecture, we will solve an algorithm problem that finds the minimum number of multiplication operations required for matrix multiplication using Swift. This problem is a good example of utilizing dynamic programming techniques and is a type of problem that can frequently appear in practical coding tests.

Problem Description

The problem is to calculate the minimum number of multiplication operations required to multiply the given matrices in order. Since the size of the matrices affects the multiplication operations, we need to find the optimal multiplication order.

Problem Specification

   Input: Integer array arr (size n+1)
   Each arr[i] represents the number of rows and columns of the ith matrix. 
   (In other words, matrix A has the size arr[i-1] * arr[i]. Here, arr[0] is the number of rows of the first matrix, and arr[n] is the number of columns of the last matrix)

   Output: Minimum number of multiplication operations required for matrix multiplication

Example

Input: arr = [10, 20, 30, 40]
Output: 3000
Description: To achieve the minimum number of operations, we need to perform multiplication in the optimal order: (A1(10×20) * A2(20×30)) * A3(30×40) = 10 * 20 * 40 + (A1 * A2) * A3.

Problem Solving Approach

This problem can be solved using dynamic programming.
The basis of the algorithm is as follows.

• Understand the optimal structure of matrix multiplication.
• Define the recurrence relation: Define dp[i][j] as the minimum multiplication cost of multiplying matrices from index i to j.
• Derive the recurrence relation for minimum operations and fill the dp array.
• Return the result.

Recurrence Relation

Considering the multiplication from matrix A to B, and setting K as the point that divides A and B, we can establish the following equation:

   dp[i][j] = min(dp[i][k] + dp[k+1][j] + arr[i]*arr[k+1]*arr[j+1])

This equation represents the process of partitioning into several parts to find the optimal number of multiplication operations, where k is any possible splitting point between i and j.

Implementation

Now let’s write Swift code to solve the problem.

func matrixChainOrder(arr: [Int]) -> Int {
    let n = arr.count - 1
    var dp = Array(repeating: Array(repeating: 0, count: n), count: n)

    for length in 2...n { // Loop through the length of the matrices
        for i in 0..< (n - length + 1) {
            let j = i + length - 1
            dp[i][j] = Int.max
            for k in i..< (j) {
                dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j] + arr[i] * arr[k + 1] * arr[j + 1])
            }
        }
    }
    
    return dp[0][n - 1]
}

// Example usage
let arr = [10, 20, 30, 40]
let result = matrixChainOrder(arr: arr)
print("Minimum number of multiplication operations: \(result)")

Code Explanation

The above code is a function that calculates the minimum number of operations for matrix multiplication.

• First, it initializes the dp array based on the number of matrices received as input.
• Next, it uses a double loop to calculate the number of operations for all possible combinations of matrices.
• To find the smallest value, it explores possible split points in the third loop.
• Finally, it returns dp[0][n - 1] to output the minimum value for all matrix multiplications.

Complexity Analysis

The time complexity of this algorithm is O(n^3). This indicates that the number of operations increases proportional to the number of matrices. The space complexity is O(n^2), which increases due to the dp array used following the recurrence relation.

Conclusion

In this lecture, we explained the problem of finding the minimum number of multiplication operations for matrices. We learned how to derive the optimal solution using dynamic programming techniques and how to implement it in Swift. This algorithm is very useful for effectively solving complex problems and is a frequently presented topic in future coding tests.

We hope this problem encourages you to research various algorithms and deterministic problem-solving methods, and to enhance your coding skills further.

Let’s learn about the Floyd-Warshall algorithm, which often appears in coding tests, and solve related algorithm problems. This article will detail the overview, working principle, and example problem-solving process of the Floyd-Warshall algorithm.

1. Overview of the Floyd-Warshall Algorithm

The Floyd-Warshall algorithm is an algorithm used to find the shortest paths between all pairs of vertices in a graph. This algorithm is based on dynamic programming and updates the shortest paths by considering paths that pass through vertex k at each step. The time complexity of the Floyd-Warshall algorithm is O(V³), where V represents the number of vertices.

1.1. Significance of the Algorithm

The Floyd-Warshall algorithm exhibits excellent efficiency in that it can identify the shortest paths between all pairs of vertices through a single process, not just finding the shortest path from a single starting point.

1.2. Applications

This algorithm is applied in various fields including calculating the shortest paths between all nodes in a network, optimizing road networks, and computing movement paths in games.

2. Working Principle of the Algorithm

The Floyd-Warshall algorithm operates in the following manner:

1. Initialize the shortest paths for all edges of the graph. The distance between two directly connected vertices is set to the weight of the edge, while the remaining pairs are set to infinity.
2. For each vertex k, update the shortest paths for all combinations of vertices i and j as follows: dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
3. Repeat this process for all pairs of vertices.

This algorithm allows us to find the shortest paths when there are paths that pass through vertex k.

3. Example Problem

Problem Description

Here is a problem that can be solved using the Floyd-Warshall algorithm:

Given a directed graph consisting of N vertices and M edges, write a program to find the shortest distance between each pair of vertices. The weights of the edges are given as positive integers, and if there is no edge between two vertices, it should be set to infinity.

Problem Input

The first line contains the number of vertices N (1 ≤ N ≤ 100) and the number of edges M (1 ≤ M ≤ 100,000). The next M lines provide the starting vertex, ending vertex, and weight of each edge. If there are multiple edges between two vertices, only the edge with the smallest weight should be considered.

Problem Output

Output the shortest distance between each pair of vertices. If the shortest distance does not exist, output INF.

Example

Input:

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

Output:

        0 1 2 3
        INF 0 1 2
        INF INF 0 1
        2 1 2 0
        

4. Problem Solving Process

To solve the problem, we will implement the Floyd-Warshall algorithm. Below is the step-by-step process of problem-solving.

4.1. Initial Setup

First, set up the initial distance array using N vertices and M edges. The weights between directly connected vertices are set to the given values, and the distances for unconnected vertices are set to infinity.

4.2. Initialize Distance Array

        var N = 4
        var M = 7
        var dist = [[Int]](repeating: [Int](repeating: Int.max, count: N + 1), count: N + 1)
        
        for i in 1...N {
            dist[i][i] = 0
        }
        

This code initializes the distance array dist to infinity and sets the distance to itself as 0.

4.3. Input Edge Information

        dist[1][2] = 1
        dist[1][3] = 3
        dist[2][3] = 1
        dist[2][4] = 2
        dist[3][4] = 1
        dist[4][1] = 2
        dist[4][2] = 3
        

Now, set the weights between directly connected vertices using the edge information. If there are multiple edges, update it to the minimum weight.

4.4. Apply the Floyd-Warshall Algorithm

        for k in 1...N {
            for i in 1...N {
                for j in 1...N {
                    if dist[i][j] > dist[i][k] + dist[k][j] {
                        dist[i][j] = dist[i][k] + dist[k][j]
                    }
                }
            }
        }
        

Here, k acts as an intermediate vertex, updating the shortest path from i to j.

4.5. Output Results

        for i in 1...N {
            for j in 1...N {
                if dist[i][j] == Int.max {
                    print("INF", terminator: " ")
                } else {
                    print(dist[i][j], terminator: " ")
                }
            }
            print("")
        }
        

Finally, output the distance array to check the shortest distances between each pair of vertices.

5. Conclusion

In this lecture, we learned the concepts and operating principles of the Floyd-Warshall algorithm and examined the process of solving actual problems. This algorithm is a powerful tool for efficiently finding the shortest paths between all pairs of vertices. It is important to solve various examples to enhance your understanding of the algorithm. You should also practice solving algorithm problems in Swift to improve your skills!

In this course, we will solve an algorithm problem to calculate the average using the Swift programming language. This problem, frequently seen in coding tests for recruitment, is a good foundation for data processing. Additionally, it will be an opportunity to learn the basic syntax of Swift and how to manipulate arrays.

Problem Description

An array is given as follows. Write a function to calculate the average of all elements in this array. The elements of the array are integers.

Input

• An integer array numbers is provided. (1 ≤ numbers.count ≤ 100, 0 ≤ numbers[i] ≤ 1000)

Output

• Output the average value of the given array rounded to the nearest integer at the first decimal place.

Example

Solution Process

Step 1: Understanding the Problem

To understand the problem, one must acknowledge that to find the average, all elements of the given array should be summed and then divided by the number of elements. Additionally, it should be remembered that the average needs to be returned as an integer rounded to the nearest whole number.

Step 2: Input Handling

Swift provides various methods to handle arrays easily, so the input array can be used directly. For example, the reduce function can be used to calculate the sum of the array.

Step 3: Algorithm Implementation

Now, let’s implement the algorithm that we will actually use.

func average(numbers: [Int]) -> Int {
    // 1. Compute the total sum of the elements in the array.
    let total = numbers.reduce(0, +)
    
    // 2. Determine the number of elements in the array.
    let count = numbers.count
    
    // 3. Calculate the average and round it.
    let average = Double(total) / Double(count)
    return Int(round(average))
}

Step 4: Writing Test Cases

Based on the function we’ve written, let’s create a few test cases.

let test1 = average(numbers: [60, 82, 75, 90, 45]) // 70
let test2 = average(numbers: [100, 90, 80]) // 90
let test3 = average(numbers: [0, 0, 0, 0]) // 0
let test4 = average(numbers: [1, 2, 3, 4, 5, 6]) // 4
let test5 = average(numbers: [1, 2, 3]) // 2

Step 5: Checking Results and Output

Let’s output the results through testing. We will use the print function for this purpose.

print(test1) // 70
print(test2) // 90
print(test3) // 0
print(test4) // 4
print(test5) // 2

Complete Code

Now, let’s introduce the final code that integrates all the steps.

func average(numbers: [Int]) -> Int {
    let total = numbers.reduce(0, +)
    let count = numbers.count
    let average = Double(total) / Double(count)
    return Int(round(average))
}

// Test Cases
let test1 = average(numbers: [60, 82, 75, 90, 45]) // 70
let test2 = average(numbers: [100, 90, 80]) // 90
let test3 = average(numbers: [0, 0, 0, 0]) // 0
let test4 = average(numbers: [1, 2, 3, 4, 5, 6]) // 4
let test5 = average(numbers: [1, 2, 3]) // 2

print(test1)
print(test2)
print(test3)
print(test4)
print(test5)

Conclusion

Through this course, we learned how to solve the algorithm problem of calculating the average using Swift. The series of processes involved in summing array elements, calculating the average, and outputting the rounded result forms a foundation for data processing. The ability to solve such problems is very important for recruitment coding tests, so it is advisable to strengthen your skills through practice.

References

• Apple Swift official documentation
• HackerRank
• LeetCode

Problem Description

There are N cities, and there are M one-way roads between them.
Each city is represented by an integer from 1 to N. If there is a road from city A to city B,
you can travel from A to B.
Write a program to find all cities that are exactly K distance away.
Ensure that the same city is not printed more than once.

Input Format

    N M K
    A1 B1
    A2 B2
    ...
    Am Bm
    

• N: Number of cities (1 ≤ N ≤ 30000)
• M: Number of roads (1 ≤ M ≤ 200000)
• K: Distance to find (0 ≤ K ≤ 30000)
• A1, B1: Road from city A to city B

Output Format

    Print the city numbers that are K distance away in ascending order.
    If there are no such cities, print -1.
    

Example

Input

    4 4 2
    1 2
    1 3
    2 4
    3 4
    

Output

    4
    

Approach to Solution

This problem can be solved using graph traversal (especially Breadth-First Search BFS).
The given cities can be modeled as nodes, and the roads as edges.
A BFS is performed to find the cities that reach a distance of K.

Overview of BFS Algorithm

BFS works by exploring all adjacent nodes from the starting node, and once
that is complete, it explores the next level of nodes. This method is
suitable for shortest path problems.

Implementation Details

Below is the code that finds cities at a specific distance using BFS in Swift.

    import Foundation

    struct City {
        var number: Int
        var distance: Int
    }

    func findCitiesAtDistanceN(n: Int, roads: [(Int, Int)], k: Int) -> [Int] {
        // Create adjacency list
        var graph = [[Int]](repeating: [Int](), count: n + 1)
        for road in roads {
            let a = road.0
            let b = road.1
            graph[a].append(b)
        }

        // Initialize BFS
        var queue = [City]()
        var distances = Array(repeating: -1, count: n + 1)
        distances[1] = 0 // Assume the starting city is 1
        queue.append(City(number: 1, distance: 0))

        while !queue.isEmpty {
            let current = queue.removeFirst()
            let currentDistance = current.distance
            for neighbor in graph[current.number] {
                if distances[neighbor] == -1 { // If not visited yet
                    distances[neighbor] = currentDistance + 1
                    queue.append(City(number: neighbor, distance: distances[neighbor]!))
                }
            }
        }

        // Find cities at distance K
        let result = distances.enumerated().compactMap { index, distance in
            distance == k ? index : nil
        }.sorted()

        return result.isEmpty ? [-1] : result
    }

    // Example input
    let roads = [(1, 2), (1, 3), (2, 4), (3, 4)]
    let result = findCitiesAtDistanceN(n: 4, roads: roads, k: 2)
    
    print(result) // Output: [4]
    

Code Explanation

In the above code, we first create an adjacency list.
Each city stores its connected neighboring cities as an array.
Then, we perform BFS to calculate the distances for each city.
Finally, we find and print the cities at distance K.

Complexity Analysis

Since we visit every node in the graph,
the time complexity is O(N + M).
The space complexity is also O(N + M).

Conclusion

In this lecture, we addressed the problem of finding cities at a specific distance.
It can be efficiently solved using BFS,
requiring careful implementation. By mastering this algorithm,
you can establish a solid foundation for solving complex graph
and road problems.