uzzam
uzzam.dev
uzzam
전체 방문자
819
오늘
4
어제
14
  • 분류 전체보기 (29)
    • 프로젝트 (4)
      • 담타 (4)
    • CS (0)
      • 운영체제 (0)
    • ps, cp (4)
      • 코딩테스트 cheatsheet (3)
      • baekjoon (1)
      • codeforces (0)
    • languages (0)
      • dart (0)
    • frameworks (2)
      • flutter (2)
    • ios (1)
    • 블로그 (10)
    • git (2)
    • blockchain (0)
    • etc. (6)

블로그 메뉴

  • 홈
  • 태그
  • 방명록

공지사항

인기 글

  • Apple Silicon(M1) 맥북 공장 초기화하기
    2022.12.07
  • 군대 사지방에서 개발하는 방법들
    2022.12.07
  • netlify 로 gatsby 블로그 자동배포하기
    2022.12.07
  • porkbun에서 깃허브 블로그 도메인 구매하기 및 도메인⋯
    2022.12.07
    porkbun에서 깃허브 블로그 도메인 구매하기 및 도메인⋯
  • 빠르게 Gatsby + Github pages 로 블로그 ⋯
    2022.12.07

태그

  • 블로그

최근 댓글

  • 블로그 글 잘 쓰시네요 ㅎㅎ 잘 보구 갑니당
    alpha-traveler
  • 마침 찾아보던 글인데 글 올려주셔서 감사합니다 ㅎㅎ
    alpha-traveler

최근 글

  • 내 인생 최고의 책
    2023.01.10
    내 인생 최고의 책
  • 새해는 특별하니까
    2023.01.08
    새해는 특별하니까
  • 안드로이드 splash screen 중복 문제 해결하기
    2023.01.07
  • git clean -fdx 하고 잠못자기
    2023.01.06
  • Xcode developer mode disabled 해결⋯
    2023.01.05

티스토리

hELLO · Designed By 정상우.
uzzam

uzzam.dev

ps, cp/코딩테스트 cheatsheet

[코딩테스트 cheatsheet] 다익스트라

2022. 12. 14. 19:24

개념

한 지점에서 다른 모든 지점까지의 최단거리를 구하는 알고리즘

현재 노드에서 가장 가까운 노드를 계속 탐색하며 최단거리를 그리디하게 업데이트해나감

힙을 사용하지 않으면 다음 노드를 선택하는 과정에서 연결된 노드를 모두 살펴야 함으로 비효율적

주의 : 가중치가 음일 경우 불가능함 => 벨만 포드 알고리즘을 사용해야함

 

시간복잡도 : O(ElogV) E : 간선의 개수, V : 노드의 개수 (힙 사용시)

 

코드

import heapq

# 입력값은 인접리스트 형식으로
graph = [[] for _ in range(n + 1)]

# 거리테이블을 무한으로 초기화
INF = int(1e9)
distance = [INF] * (n + 1)

# (거리, 노드)로 힙에 추가 -> 가장 가까운 거리를 바로 알 수 있음
start = 0
heap = []
heapq.heappush(heap, (0, start))

while heap:
    dist, now = heapq.heappop(heap)
    
    if distance[now] < dist:
    	continue
       
    for i in graph[now]:
        cost = dist + i[1]
        if distance[i[0]] > cost:
            distance[i[0]] = cost
            heapq.heappush(heap, (cost, i[0])
        
print(distance)

 

백준 티어별로 살펴보는 문제 유형

 

골드 5

5972 - 택배 배송 (https://www.acmicpc.net/problem/5972)

다익스트라를 알고 있다면 쉽게 풀리는 문제

 

골드 4

1504 - 특정한 최단 경로

 

골드 3

11779 - 최소비용 구하기 2 (https://www.acmicpc.net/problem/11779)

 

골드 2

2211 - 네트워크 복구 (https://www.acmicpc.net/problem/2211)

9370 - 미확인 도착지 (https://www.acmicpc.net/problem/9370)

 

골드 1 

1162 - 도로포장 (https://www.acmicpc.net/problem/1162)

1800 - 인터넷 설치 (https://www.acmicpc.net/problem/1800)

 

플래티넘 5

5719 - 거의 최단 경로 (https://www.acmicpc.net/problem/5719)

 

 

문제 접근법

'ps, cp > 코딩테스트 cheatsheet' 카테고리의 다른 글

[코딩테스트 cheatsheet] 플로이드 워셜  (0) 2022.12.10
[코딩테스트 cheatsheet] 시작하기  (0) 2022.12.09
    'ps, cp/코딩테스트 cheatsheet' 카테고리의 다른 글
    • [코딩테스트 cheatsheet] 플로이드 워셜
    • [코딩테스트 cheatsheet] 시작하기
    uzzam
    uzzam
    댓글쓰기
    이전 글
    [코딩테스트 cheatsheet] 플로이드 워셜

    티스토리툴바