Author: root

Hello! Today, we will discuss an algorithm problem that finds the “Greatest Common Divisor” in order to help you prepare for coding tests. Accurately calculating the greatest common divisor is essential in many problems, especially those that require both mathematical and algorithmic thinking. In this session, we will use functional programming techniques and practice with the Python language.

Problem Description

Given two integers a and b, please write a program to find the greatest common divisor of these two numbers. The greatest common divisor (GCD) refers to the largest number among the common divisors of the two integers.

Input

• On the first line, there are two integers a and b (1 ≤ a, b ≤ 10⁹).

Output

• Print the integer GCD(a, b).

Examples

Here are some examples:

Example 1:
Input: 60 48
Output: 12

Example 2:
Input: 101 10
Output: 1

Example 3:
Input: 17 17
Output: 17

Solution Method

The most famous method for finding the greatest common divisor is the Euclidean algorithm. This method is based on the following principles:

• The greatest common divisor of two numbers a and b is the same as the greatest common divisor of b and the remainder of a divided by b, r. That is, GCD(a, b) = GCD(b, r).
• Continue this process until r becomes 0, and the last remaining b will be the greatest common divisor.

Implementing the Euclidean Algorithm

Now we will implement the Euclidean algorithm in Python code. Below is an example of a function that calculates the greatest common divisor:

def gcd(a, b):
    while b != 0:
        a, b = b, a % b
    return a

This function uses a loop to continuously swap the values of the two numbers and calculate the remainder until b becomes 0. The final remaining a will be the greatest common divisor.

Code Execution Example

Let’s write the main code to take input and execute:

if __name__ == "__main__":
    a, b = map(int, input("Please enter two numbers: ").split())
    result = gcd(a, b)
    print(f"Greatest Common Divisor: {result}")

Conclusion

In this article, we learned the principle of the Euclidean algorithm through the problem of finding the greatest common divisor and actually implemented it in Python. This problem has various applications and the same principles can be applied when solving other algorithm problems. I hope you experience the harmony of mathematics and programming while solving algorithmic challenges.

One thing I want to emphasize as we conclude!

The foundation of preparing for coding tests is to solve a wide variety of problems. By solving many problems and reviewing the process, you can significantly improve your coding skills. Thank you!

Hello! In this article, I would like to talk about the preparation process for algorithm exams for employment. In particular, we will delve deeply into the problem of finding the shortest path. This problem can be encountered in various situations, and the shortest path algorithm, a fundamental concept in graph theory, is frequently asked in job interviews.

Definition of the Shortest Path Problem

The shortest path problem is the problem of finding the shortest path between two nodes in a given graph. Here, the graph is a mathematical representation of networks such as roads and communication networks, composed of vertices and edges. We can use various algorithms to solve this problem, and we will focus on Dijkstra’s algorithm here.

Understanding Dijkstra’s Algorithm

Dijkstra’s algorithm is an efficient algorithm for finding the shortest path from a single vertex to all other vertices in a weighted graph. The algorithm works as follows:

1. Choose a starting vertex and set the distance for that vertex to 0.
2. Update the distances of the vertices connected to the starting vertex.
3. Select the vertex with the shortest updated distance and mark it as ‘visited’.
4. Repeat the process of selecting vertices connected to the visited vertex and updating the distances.
5. Repeat this process until all vertices are visited.

Problem Statement

In this lecture, we will address the problem of finding the shortest path between two vertices when given a graph. The problem can be summarized in the following form:

5 7
0 1 2
0 2 3
1 2 1
1 3 5
2 4 2
3 4 1
4 3 3
0 4

Problem-Solving Process

1. Setting Up the Graph Structure

First, to solve the above problem, we need to set up the graph in an appropriate data structure. Generally, using an adjacency list is efficient in terms of memory and processing speed. In Python, this can be implemented using a dictionary.

2. Implementing Dijkstra’s Algorithm

Next, the libraries needed to implement Dijkstra’s algorithm are as follows:

import heapq
import sys
from collections import defaultdict

Here, heapq is used for the priority queue, and defaultdict is used to easily implement the adjacency list.

3. Example Python Code

Now, let’s write the complete code to find the shortest path:

def dijkstra(graph, start, end):
    # Initialize distances
    distance = {node: float('inf') for node in graph}
    distance[start] = 0
    priority_queue = [(0, start)]  # (distance, vertex)

    while priority_queue:
        current_distance, current_node = heapq.heappop(priority_queue)

        # Ignore if a greater value than the current node's distance comes in
        if current_distance > distance[current_node]:
            continue

        # Visit neighboring nodes
        for neighbor, weight in graph[current_node]:
            distance_via_neighbor = current_distance + weight
            if distance_via_neighbor < distance[neighbor]:
                distance[neighbor] = distance_via_neighbor
                heapq.heappush(priority_queue, (distance_via_neighbor, neighbor))

    return distance[end]

# Define the graph
graph = defaultdict(list)
edges = [
    (0, 1, 2),
    (0, 2, 3),
    (1, 2, 1),
    (1, 3, 5),
    (2, 4, 2),
    (3, 4, 1),
    (4, 3, 3)
]

for u, v, w in edges:
    graph[u].append((v, w))

# Calculate the shortest path
start, end = 0, 4
result = dijkstra(graph, start, end)
print(result)  # Output result: 5

4. Code Explanation

The code above uses Dijkstra's algorithm to find the shortest path in the given graph. Each comment allows you to understand the code step by step, but to summarize briefly:

1. Set the graph in dictionary form.
2. Initialize the distance of the starting vertex and add it to the priority queue.
3. Pop a vertex from the queue, investigate its neighbors, update distances, and add them to the queue.
4. After calculating the distances for all vertices, return the distance to the final destination vertex.

Conclusion

The shortest path finding algorithm is one of the important topics in computer science, which may seem simple but can actually be modified in various ways. In addition to Dijkstra's algorithm, there are several methods available, including Bellman-Ford and A* algorithms. In this article, we explored the most basic and widely used Dijkstra's algorithm.

In the future, we will continue to tackle various algorithm problems and delve into more advanced topics. Thank you!

Hello! In this session, we will solve an algorithm problem using sets. A set is an important fundamental concept in mathematics and is also a commonly used data structure in programming. In Python, sets are provided as a built-in data structure that is very easy to use.

Problem Description

Problem: Given two integer arrays, find the intersection of the two arrays. The result should be returned as a set, excluding duplicate elements.

Input Format

arr1: List[int]  # The first integer array
arr2: List[int]  # The second integer array

Output Format

Set[int]  # The intersection of the two arrays

Input: arr1 = [1, 2, 2, 3], arr2 = [2, 3, 4]
Output: {2, 3}

Problem Solving Strategy

There are several ways to solve this problem, but utilizing the properties of sets is the most efficient. Since sets do not allow duplicate elements, converting the given arrays to sets automatically removes duplicates. Then, we can compute the intersection of the two sets and return the result.

Step-by-Step Approach

1. Convert the given arrays to sets.
2. Find the intersection between the two sets.
3. Return the result of the intersection.

Code Implementation

Now, let’s implement the Python code based on the above steps.

def intersection(arr1, arr2):
    set1 = set(arr1)
    set2 = set(arr2)
    return set1 & set2  # & operator denotes intersection.

Code Explanation

The code is quite simple. First, we convert the two given arrays to sets and then use the & operator to find the intersection. This operator returns only the common elements from both sets.

Test Cases

Now, let’s create some test cases to check if the code works correctly.

# Test cases
print(intersection([1, 2, 2, 3], [2, 3, 4]))  # Output: {2, 3}
print(intersection([5, 6, 7], [6, 8, 9]))     # Output: {6}
print(intersection([1, 1, 1], [2, 2, 2]))     # Output: set()
print(intersection([], [1, 2, 3]))              # Output: set()

Test Results Explanation

Looking at the results of each test case:

• The first case contains both 2 and 3 in both arrays, returning {2, 3}.
• The second case returns the set {6}.
• The third case returns an empty set since there are no common elements between the two arrays.
• The fourth case returns an empty set because the first array is empty.

Complexity Analysis

Now, let’s analyze the time complexity. Let n be the size of one array and m of the other:

• It takes O(n) and O(m) time to convert each array to a set.
• Finding the intersection between the two sets consumes O(min(n, m)) time.

In summary, the total time complexity is O(n + m). The space complexity is also O(n + m) as space is required to store the sets.

Conclusion

In this lecture, we learned about the utility of sets through the problem of finding the intersection of arrays. Sets are a very useful data structure and can be used in a variety of algorithmic problems, not just this one. We look forward to covering more valuable algorithmic techniques in the next lecture!

5
5 3 1 4 2
    

4
    

def min_swaps(arr):
    n = len(arr)
    # Create a sorted array and combine it with index information.
    sorted_arr = sorted(enumerate(arr), key=lambda x: x[1])
    
    # Initialize visited array and swap count.
    visited = [False] * n
    swap_count = 0
    
    for i in range(n):
        # Skip already visited indices.
        if visited[i] or sorted_arr[i][0] == i:
            continue
        
        # Explore the cycle.
        cycle_size = 0
        j = i
        
        while not visited[j]:
            visited[j] = True
            j = sorted_arr[j][0]
            cycle_size += 1
            
        if cycle_size > 0:
            swap_count += (cycle_size - 1)
    
    return swap_count

# Take input.
N = int(input())
arr = list(map(int, input().split()))

# Print the result.
print(min_swaps(arr))
    

• Baekjoon Algorithm Problem: ACM ICPC
• Data Structures and Algorithms
• Books related to Competitive Programming

1. Problem Overview

This coding test problem is to implement the given conditions based on the orders that Jumong gave to his soldiers. The problem is as follows.

Problem Description

Jumong gives each soldier N commands. Each command instructs them to move in a specific direction.
The soldiers receive and execute these commands. However, Jumong made a mistake during the command process and decided to ignore some commands.
Now, you need to write a program that calculates the final position based on the executed commands by the soldiers.

Format of Commands

• The commands are given as a list of strings: ["U", "D", "L", "R"].
• “U” means to move up by one step, “D” means to move down by one step, “L” means to move left by one step, and “R” means to move right by one step.
• The number of commands is 1 ≤ N ≤ 1000.

Input

The first line contains the number of commands N,
and the next N lines contain each command.

Output

Output the coordinates of the final position (x, y) as integers.
The initial position is (0, 0).

2. Problem Solving Process

2.1. Understanding the Problem

To solve the problem, we need to implement the movement according to each command following specific rules.
The list of commands will be analyzed, and the coordinates will be updated according to each command.

2.2. Data Structure Design

We use the (x, y) coordinates to store the final position.
It is initialized with x = 0, y = 0.

2.3. Algorithm Design

We will read each command line by line and move in the corresponding direction.
In other words, the coordinates will be updated as follows based on each command:

• "U": y += 1
• "D": y -= 1
• "L": x -= 1
• "R": x += 1

2.4. Final Code Implementation

def final_position(commands):
    x, y = 0, 0  # Initial position

    for command in commands:
        if command == "U":
            y += 1
        elif command == "D":
            y -= 1
        elif command == "L":
            x -= 1
        elif command == "R":
            x += 1

    return (x, y)

# Example input
N = int(input("Enter the number of commands: "))
commands = [input().strip() for _ in range(N)]
# Output final position
print(final_position(commands))

3. Examples and Tests

3.1. Test Cases

For example, if the following input is given:

5
    R
    R
    U
    D
    L

When processing the above commands, the final position will be (1, 0).

4. Conclusion

In this process, we implemented an algorithm to calculate the final position of the soldiers based on Jumong’s commands.
We solved the problem through coordinate updates according to each command.
This simple problem helps us understand the basics of data structures and algorithm application.