[swift] Swift 알고리즘 문제 풀이

28 Nov 2023

swift

Swift는 강력한 프로그래밍 언어로, 다양한 알고리즘 문제를 효율적으로 해결할 수 있습니다. 이 글에서는 몇 가지 대표적인 알고리즘 문제를 Swift로 풀어보면서 Swift의 강점을 살펴보겠습니다.

1. 이진 탐색(Binary Search)

이진 탐색은 정렬된 배열에서 특정한 값을 찾는 알고리즘입니다. Swift로 이진 탐색을 구현해보겠습니다.

func binarySearch(_ array: [Int], target: Int) -> Int {
    var left = 0
    var right = array.count - 1
    
    while left <= right {
        let mid = (left + right) / 2
        
        if array[mid] == target {
            return mid
        }
        
        if array[mid] < target {
            left = mid + 1
        } else {
            right = mid - 1
        }
    }

    return -1
}

let array = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
let target = 6

let index = binarySearch(array, target: target)
if index == -1 {
    print("Element not found")
} else {
    print("Element found at index \(index)")
}

2. 퀵 정렬(Quick Sort)

퀵 정렬은 분할 정복 알고리즘으로, 평균적으로 매우 빠른 정렬 방법입니다. Swift로 퀵 정렬을 구현해보겠습니다.

func quickSort(_ array: inout [Int], low: Int, high: Int) {
    if low < high {
        let pivotIndex = partition(&array, low: low, high: high)
        quickSort(&array, low: low, high: pivotIndex - 1)
        quickSort(&array, low: pivotIndex + 1, high: high)
    }
}

func partition(_ array: inout [Int], low: Int, high: Int) -> Int {
    let pivot = array[high]
    var i = low
    
    for j in low..<high {
        if array[j] <= pivot {
            array.swapAt(i, j)
            i += 1
        }
    }
    
    array.swapAt(i, high)
    
    return i
}

var array = [5, 2, 9, 1, 3, 6, 8, 7, 4]
quickSort(&array, low: 0, high: array.count - 1)
print("Sorted array: \(array)")

3. 최단 경로(Dijkstra’s Algorithm)

Dijkstra의 알고리즘은 가중치 그래프에서 최단 경로를 찾는 알고리즘입니다. Swift로 Dijkstra 알고리즘을 구현해보겠습니다.

struct Edge {
    let start: String
    let end: String
    let weight: Int
}

func dijkstra(_ graph: [String: [Edge]], start: String, end: String) -> [String: Int] {
    var distances = [String: Int]()
    var queue = [String]()
    
    for vertex in graph.keys {
        distances[vertex] = Int.max
    }
    
    distances[start] = 0
    queue.append(start)
    
    while !queue.isEmpty {
        let vertex = queue.removeFirst()
        
        if vertex == end {
            break
        }
        
        if let edges = graph[vertex] {
            for edge in edges {
                let distance = distances[vertex]! + edge.weight
                if distance < distances[edge.end]! {
                    distances[edge.end] = distance
                    queue.append(edge.end)
                }
            }
        }
    }
    
    return distances
}

let graph = [
    "A": [Edge(start: "A", end: "B", weight: 6), Edge(start: "A", end: "D", weight: 1)],
    "B": [Edge(start: "B", end: "A", weight: 6), Edge(start: "B", end: "D", weight: 2), Edge(start: "B", end: "E", weight: 2)],
    "C": [Edge(start: "C", end: "E", weight: 5), Edge(start: "C", end: "F", weight: 5)],
    "D": [Edge(start: "D", end: "A", weight: 1), Edge(start: "D", end: "B", weight: 2), Edge(start: "D", end: "E", weight: 1)],
    "E": [Edge(start: "E", end: "B", weight: 2), Edge(start: "E", end: "C", weight: 5), Edge(start: "E", end: "D", weight: 1), Edge(start: "E", end: "F", weight: 2)],
    "F": [Edge(start: "F", end: "C", weight: 5), Edge(start: "F", end: "E", weight: 2)]
]

let start = "A"
let end = "F"

let distances = dijkstra(graph, start: start, end: end)
print("Shortest distances: \(distances)")

위의 예시 코드에서는 Swift를 사용하여 이진 탐색, 퀵 정렬 및 최단 경로 알고리즘을 구현하는 방법을 살펴보았습니다. 알고리즘 문제 풀이에 Swift를 사용하면 간결하고 효율적인 코드를 작성할 수 있습니다.

1. 이진 탐색(Binary Search)

2. 퀵 정렬(Quick Sort)

3. 최단 경로(Dijkstra’s Algorithm)

참고 자료