문제- 가중치가 음이 아닌(0 이상) 방향 그래프에서, 한 출발점 'start' 에서 다른 모든 정점까지의 최단 거리를 구하는 표준 알고리즘입니다.- 1959년 Edsger W. Dijkstra 가 발표하였으며, 우선순위 큐(min-heap) 와 결합한 구현은 공지된 표준 기법입니다. 본 지문과 테스트 케이스는 본 학습 자료를 위해 자체적으로 작성되었습니다. 문제풀이import heapqINF = float('inf')def dijkstra(n: int, edges: list, start: int) -> list: """ n: 정점 수 (정점 번호 0 ~ n-1) edges: (u, v, w) 형식 방향 간선 리스트 start: 출발 정점 반환: 길이 n 의 거리 리스..
힙이 필요한 이유원소 100만 개가 있고, 가장 작은 값 꺼내기를 100만번 반복해야 한다고 할 때, 아래와 같은 효율을 낸다.리스트 순회 : O(n)sort() : O(n log n)힙 : O(log n) 모든 원소를 다 정렬해 봐야하는 문제라면 힙은 의미가 없다. 힙이 필요할 때는 매번 극값(가장 크거나 작은 값) 하나만 필요할 때이다. Heap 힙 이란?힙은 최댓값과 최솟값을 찾는 연산을 빠르게 하기 위해 고안된 완전 이진트리를 기본으로 한다.완전 이진 트리 : 위에서 아래로, 왼쪽에서 오른쪽으로 빈틈없이 채워진다.힙 속성 : 모든 부모 ≤ 자식 (min heap 기준)형제끼리는 아무 순서 관계가 없다. 힙이 보장하는 건 오직 루트 heap[0] 가 전체 최솟값이라는 것이다. 파이썬의 힙큐 ..
리스트란? 여러 값을 순서대로 담는, 변경 가능한 자료형이다. 순서 : 넣은 순서가 유지되고, 각 자리에 인덱스가 붙는다.가변 : 만든 뒤에도 값을 바꾸거나 넣고 뺄 수 있다.이질 : 서로 다른 타입을 섞어 담을 수 있다. 이 세가지 성질이 튜플, 문자열, 집합과 리스트를 가르는 기준이다. 튜플은 순서는 있지만 불변이고, 집합은 가변이지만 순서가 없다.a = [1, 2, 3] # 대괄호 리터럴b = [] # 빈 리스트c = list("abc") # 다른 순회 가능 객체로부터 → ['a','b','c']d = [0] * 5 # 반복 → [0,0,0,0,0]e = [x**2 for x in range(5..
튜플이란?튜플은 한번 만들면 값을 바꿀 수 없는 (불변, immutable) 순서 있는 값들의 묶음이다. t = (1, 2, 3)t = 1, 2, 3 # 괄호는 사실 선택사항t = () # 빈 튜플t = (1,) # 요소 1개는 쉼표 필수! (1)은 그냥 정수 리스트와 비교하면 리스트는 안의 값을 수정, 추가, 삭제할 수 있지만 튜플은 한 번 만들면 그 값 그대로 고정된다.lst = [2,5] # 리스트 - 대괄호lst[0] = 100 # 가능. lst는 [100, 5]가 됨tup = (2,5) # 튜플 - 소괄호tup[0] = 100 # 에러! TypeError: 'tuple' object does not support item assignm..
