< 프로그래머스 / 배달 > 다익스트라 알고리즘

하하하, 이제 학교 생활이 너무..바쁘다.. 과제하랴 팀플하랴...

그래도 부캠 1차 코딩테스트는 통과할 수준이 이제 되었지 않나 싶어서 안심하면서 지냈습니다. 

그런데 !!!!

프로그래머스 파이썬 코칭 스터디를 듣기로 하였고, 사전테스트가 있다 길래 엊그제 4문제를 실제 코테 조건에서 풀어야 했다.

그래서 풀어봤는데, 4 문제 중 3문제가 풀어봤던 문제여서 10분 컷하고 4번째 문제를 푸는데 도저히 안풀리는 것이었다. 

시험 시간은 3시간 40분을 주었지만 나는 딱 2시간 만 쓰기로 생각하고 있었고, 결국 2시간이 다되도록 못 풀고 나왔다. 

 

그 문제를 너무 꼭 풀이를 알고 싶어서 검색을 해봤는데, 바로 이 문제였다. 

 

https://programmers.co.kr/learn/courses/30/lessons/12978

코딩테스트 연습 - 배달

 

배달 문제

레벨 2 짜리 문제였기 때문에 더욱더 자존심이 상

했다.( 이제 2렙 정도는 처바를수 있을 줄 알았는데.. ㅠ )

하지만, 검색을 해보니 '다익스트라 알고리즘' 을 구현하지 못하면 못 푸는 문제였다. 

 

내가 준비하지 못한 알고리즘 개념이 있다는 것에 너무 충격을 받았고.. 당장 담주에 1차코딩테스트..

그래도 사전테스트 덕분에 그것을 알게 되어서 다행이라는 생각도 들었다. 정말 다행이었다.

 

그래서! 다익스트라 알고리즘에 대해 공부하고

또 개선된 다익스트라 알고리즘에 대해서도 공부한 뒤

문제를 세번 정도 풀었다. 

다익스트라 알고리즘은 자다 일어나서도 술술 코드를 짤 수 있도록 익숙해져야 한다기에.. 나동빈님께서

 

import heapq

def solution(N, road, K): # 
    graph = [[] for i in range(N + 1)]
    distance = [int(1e9)] * (N + 1)
    
    for r in road:
        a, b, d = r
        graph[a].append((d, b))
        graph[b].append((d, a)) # (간선거리, 노드번호)
    
    def daijkstra(start):
        distance[start] = 0
        q = []
        heapq.heappush(q, (0, start))
        
        while q:
            dt, node = heapq.heappop(q) 
            
            # 방문필요없는 노드면 패스 (저장된 거리값보다클때 , 같을때는 처음 start 때문에라도 넣어야댐, heapq에처음 넣어지는 애들
            if dt > distance[node]:
                continue
            
            for i in graph[node]: # 안에 있는 노드들 거리 갱신
                i_dt, i_node = i
                comp_dt = i_dt + dt
                if comp_dt < distance[i_node]: # 갱신할 거리가 저장된 거리보다 작으면
                    distance[i_node] = comp_dt
                    heapq.heappush(q, (comp_dt, i_node))
            
    daijkstra(1)   
    k = list(filter(lambda x: x <= K, distance))
               
    return len(k)

일반 다익스트라 알고리즘과, 개선된 다익스트라의 알고리즘의 가장 큰 차이점은

간선거리가 가장 짧은 노드를 탐색하는 방법 에 있다. 

일반 다익스트라 알고리즘은, 남아있는 모든 노드의 간선 거리를 선형 탐색하지만 O(N)

개선된 다익스트라 알고리즘은, 힙 큐를 사용하여 (또는 우선순위 큐) 최소 거리인 노드를 탐색한다 O(logN)

 

또한 방문 처리를 하는 방식이 다르다는 게 차이였다. 

 

정말...코칭스터디 덕분에 내가 부족하다는 것을 알아서 지속적으로 코테까지 빡세게 문제 풀 의욕이 생긴 것 같다. 

프로그래머스 사랑해요

2레벨 전부 세어봤더니 안 풀었던 것이 총 21문제여서 

21 문제를 코테 전 까지 전부 푸는 것을 목표로 두었다. 

 

파이팅!!!