Author: root

To solve algorithm problems, it is crucial to understand the essence of the problem and to choose the appropriate data structures and algorithms. In this course, we will discuss the ‘Longest Increasing Subsequence (LIS)’ problem. This problem involves finding the longest possible subsequence that maintains an increasing order while processing specific data.

1. Problem Definition

The problem is to find the longest increasing subsequence in a given integer array. A subsequence means selecting some numbers from the array while maintaining their order. It is important to note that the selected numbers do not need to be contiguous. For example, given the array [10, 20, 10, 30, 20, 50], the longest increasing subsequence is [10, 20, 30, 50].

1.1 Problem Examples

    Input: [10, 20, 10, 30, 20, 50]
    Output: 4 (Subsequence: [10, 20, 30, 50])

    Input: [5, 6, 3, 7, 8, 4, 1]
    Output: 5 (Subsequence: [5, 6, 7, 8])
    

2. Problem Approach

The longest increasing subsequence problem can be approached with the following two basic methods:

1. Dynamic Programming
2. Binary Search

2.1 Dynamic Programming

Dynamic programming is a method of solving problems by breaking them down into smaller subproblems. To solve the LIS problem using dynamic programming, two arrays can be used. One array stores the length of the longest increasing subsequence for each element of the original array, and the other array stores the elements that make up that subsequence.

2.2 Binary Search

This method allows for a more efficient solution to the LIS problem. The method using binary search has a time complexity of O(n log n), and determines the position of each element by utilizing the length of the already discovered increasing subsequences during the array search process.

3. Algorithm Implementation

Below is the process of solving the LIS problem using dynamic programming and binary search implemented in Swift.

3.1 Dynamic Programming Implementation

    func lengthOfLIS(_ nums: [Int]) -> Int {
        guard !nums.isEmpty else { return 0 }
        
        var dp = Array(repeating: 1, count: nums.count)
        var maxLength = 1
        
        for i in 1.. nums[j] {
                    dp[i] = max(dp[i], dp[j] + 1)
                }
            }
            maxLength = max(maxLength, dp[i])
        }
        
        return maxLength
    }

    // Example usage
    let nums = [10, 20, 10, 30, 20, 50]
    print(lengthOfLIS(nums))  // Output: 4
    

3.2 Binary Search Implementation

    func lengthOfLIS(_ nums: [Int]) -> Int {
        var dp = [Int]()
        
        for num in nums {
            if let idx = dp.firstIndex(where: { $0 >= num }) {
                dp[idx] = num
            } else {
                dp.append(num)
            }
        }
        
        return dp.count
    }

    // Example usage
    let nums = [10, 20, 10, 30, 20, 50]
    print(lengthOfLIS(nums))  // Output: 4
    

4. Time Complexity Analysis

For dynamic programming, the time complexity is O(n^2) because a double loop is used to compare every pair of array elements. In contrast, the approach implemented with binary search has a time complexity of O(n log n), making it more efficient for handling larger inputs.

5. Conclusion

Today we discussed the problem of finding the longest increasing subsequence. We explored two approach methods: dynamic programming and binary search, analyzing each implementation and its time complexity. The process of solving such problems can be excellent practice for algorithm interviews. It is recommended to tackle various problems to prepare for coding tests.

In the next lecture, we will cover another algorithm problem. We appreciate your interest!

In the Subrimari coding test, problems frequently involve finding a “good number.” In this session, we will solve a problem that involves finding specific numbers that satisfy the conditions referred to as “good numbers.” This process will illustrate how to approach and solve problems when using the Swift language.

Problem Description

The problem is as follows:

For a given natural number N, a friend has defined a good number. Specifically, among the numbers from 1 to N, if the sum of any two numbers x and y equals N, then x and y are considered good numbers. You need to find and output the pairs of good numbers for the given N. Note that x must be less than or equal to y, and x + y must equal N.

Input Format

• The first line contains the natural number N (1 ≤ N ≤ 1000).

Output Format

• Output all pairs of good numbers (x, y) one pair per line.

Approach to the Problem

To find good numbers, we can use the following approach:

1. Use two loops to generate all possible pairs from 1 to N.
2. Check if the sum of each pair is N.
3. Output the pairs whose sum equals N.

Algorithm Implementation

In Swift, we can solve the problem using the following structure:

import Foundation

func findGoodNumbers(N: Int) {
    var goodPairs: [(Int, Int)] = []
    
    for x in 1...N {
        for y in x...N {
            if x + y == N {
                goodPairs.append((x, y))
            }
        }
    }
    
    // Output result
    for pair in goodPairs {
        print("Good number pair: \(pair.0), \(pair.1)")
    }
}

let N = 10 // Example input
findGoodNumbers(N: N)

Code Explanation

In the Swift code above, we can see the following important details:

1. The function findGoodNumbers takes a natural number N as a parameter and finds the pairs of good numbers for it.
2. A nested for loop is used to generate all pairs of x and y.
3. If the sum equals N, that pair is added to the goodPairs array.
4. Finally, the pairs of good numbers stored in the array are printed.

Execution Result

If the input N is 10, the program produces the following output:

Good number pair: 1, 9
Good number pair: 2, 8
Good number pair: 3, 7
Good number pair: 4, 6
Good number pair: 5, 5

Complexity Analysis

The time complexity of this algorithm is O(N^2). Since we use a nested loop for N, the execution time may increase for larger values of N. However, since the maximum value of N is limited to 1000, this level of time complexity is practically feasible.

Conclusion

In this article, we explored the approach to solve the “good number” problem and implemented the solution in Swift code. We learned how to resolve the problem through a simple yet effective nested loop. I hope this helps improve algorithmic thinking through similar problems in the future.

Additional Considerations

Various methods can be explored to solve this problem. For example:

• Using a hashmap to find good numbers with O(N) time complexity
• When N is even, restricting the range of x to up to N/2
• Solutions through recursive methods

Through these various approaches, a deeper understanding of algorithms can be achieved. In the next session, we will address additional problems related to this topic. Thank you!

Problem Description

This is a problem of finding the K-th shortest path between two nodes A and B in a given graph.
The graph is a weighted directed graph. The K-th shortest path refers to the path from A to B
whose sum of weights is the K-th smallest among all paths.
K is a positive integer and K is always greater than or equal to 1.

Input Description

The first line of the input contains two integers N (1 ≤ N ≤ 100) and M (1 ≤ M ≤ 1000).
Here, N represents the number of nodes, and M represents the number of edges.
Following this, M lines contain three integers U, V, W, which represent an edge with weight W from node U to node V.
The last line contains two integers K, A, B. K indicates which K-th shortest path to find,
A is the starting node, and B is the destination node.

Output Description

Output the sum of weights of the K-th shortest path. If the K-th shortest path does not exist, output -1.

Problem Solving Process

There are various methods to solve this problem, but a variant of the ‘Dijkstra’s Algorithm’ can be used.
Dijkstra’s algorithm is typically used to find the shortest path but can utilize a priority queue
and path list to find a certain number of shortest paths.
The following describes that process.

1. Graph Representation

Represent the graph in the form of an adjacency list. Store the connected nodes and their weights for each node.

2. Use of Priority Queue

Use a priority queue to manage the weights of paths from the current node to find the shortest path.
To find the K-th path, maintain a path list for each node.

3. Path Calculation

Start from the starting node and explore paths for each node.
The lower the sum of weights of each path, the higher the priority is set,
and this process continues until the K-th shortest path is found.

4. Result Output

Once the sum of weights for the K-th shortest path is successfully calculated, that value is printed.
If no path exists, -1 is printed.

Swift Code Implementation

Below is the Swift code that uses the method described above.

import Foundation

struct Edge {
    let to: Int
    let weight: Int
}

func kthShortestPath(n: Int, edges: [[Edge]], k: Int, start: Int, end: Int) -> Int {
    var paths = [[Int]](repeating: [], count: n + 1)
    var minHeap = [(weight: Int, node: Int)]()
    
    // Insert (0, start node)
    minHeap.append((0, start))
    
    while !minHeap.isEmpty {
        // Remove the node with the smallest weight
        minHeap.sort { $0.weight < $1.weight }
        let current = minHeap.removeFirst()
        
        // Save the path
        paths[current.node].append(current.weight)
        
        // If the k-th path is found, terminate
        if paths[end].count == k {
            return current.weight
        }
        
        // Explore adjacent nodes
        for edge in edges[current.node] {
            minHeap.append((current.weight + edge.weight, edge.to))
        }
    }
    
    // K-th path does not exist
    return -1
}

// Input
let n = 5 // Number of nodes
let m = 7 // Number of edges
let edges = [
    1: [Edge(to: 2, weight: 10), Edge(to: 3, weight: 5)],
    2: [Edge(to: 3, weight: 2), Edge(to: 4, weight: 1)],
    3: [Edge(to: 2, weight: 3), Edge(to: 4, weight: 9)],
    4: [Edge(to: 5, weight: 2)],
    5: []
]
let k = 3 // K-th path
let start = 1 // Starting node
let end = 5 // Destination node

// Function call
let result = kthShortestPath(n: n, edges: edges, k: k, start: start, end: end)
print(result) // Output result
    

Conclusion

The K-th shortest path problem is one of the important techniques in algorithm problem solving.
Utilizing Dijkstra's algorithm and priority queues can effectively solve the problem.
Additionally, problems like this are often encountered in actual interviews, so sufficient practice is necessary.
Through this course, I hope it serves as a foundation for understanding the K-th shortest path problem.