[알고리즘] 패스트캠퍼스 챌린지 29일차

어제 이론 공부한 것을 오늘은 코드로 짜보기!

강의는 여전히 Python이지만 난 Swift로 직접 바꿔보면서 공부중이다.

 

학습 예제는 어제와 동일하게!

 

우선 그래프 정보를 아래와 같이 표현해줄 수 있다.

let graph: [String: [String:Int]] = [
    "A" : ["B" : 8, "C" : 1, "D" : 2],
    "B" : [:],
    "C" : ["B" : 5],
    "D" : ["E" : 3, "F" : 5],
    "E" : ["F" : 1],
    "F" : [:]
]

 

func dijkstra(graph: [String: [String:Int]], startNode: String) -> [String: Int] {
    // distance
    var distance: [String: Int] = [:]
    for item in graph {
        distance.updateValue(Int.max, forKey: item.key)
    }
    distance[startNode] = 0
    
    // queue
    var priorityQueue: [(node: String, value: Int)] = []
    // insert first node to queue
    priorityQueue.append((startNode, 0))
    
    // pop node from priorty queue until it's empty
    while !priorityQueue.isEmpty {
        // find the smallest value
        priorityQueue.sort {$0 < $1}
        let first = priorityQueue.removeFirst()
        let currentDistance = first.value
        let currentNode = first.node
        
        // don't have to calculate shorter distance
        if distance[currentNode]! < currentDistance {
            continue
        }
        
        if let items = graph[currentNode]?.values as? [String:Int] {
            for (adjacent, weight) in items {
                // (node near the current node, weight)
                let newDistance = currentDistance + weight
                if newDistance < distance[adjacent]! {
                    // update to shorter distance
                    distance[adjacent] = newDistance
                    priorityQueue.append((adjacent, newDistance))
                }
            }
        }
        
    }
    
    return distance
}

 

총 시간 복잡도

• 과정1 + 과정2 = O(E) + 𝑂(𝐸𝑙𝑜𝑔𝐸)O(ElogE) = 𝑂(𝐸+𝐸𝑙𝑜𝑔𝐸)=𝑂(𝐸𝑙𝑜𝑔𝐸)

 

어제 공부했던 이론 그대로 코드로 만든 것

조금 복잡했다ㅠㅠㅠ

어렵다..ㅠㅠㅠ

 

 

인증샷

 

내일까지면 30일 인강챌린지 끝!!

대박 :)

 

https://bit.ly/37BpXiC

패스트캠퍼스 [직장인 실무교육]

본 포스팅은 패스트캠퍼스 환급 챌린지 참여를 위해 작성되었습니다.