Upstage AI Lab 2기 [Day042] 자료구조 및 알고리즘 (3)

Upstage AI Lab 2기

2024년 2월 8일 (목) Day_042

 

Day_042 실시간 강의 : 자료구조 및 알고리즘 (3)

(노정호 강사님

https://www.nossi.dev/

https://www.youtube.com/@nossi-dev)

 

---

3일차 수업 요약 키워드

Priority Queue

Heap

Dijkstra

---

2일차 수업 복습 BFS/DFS

BFS

tip : 예약부터 한다!

q = deque()
q.append(start_v)
visited = {start_v : True}

while q:

 

DFS

def dfs(cur_v):
    visited[cur_v] = True
    for next_v in graph[cur_v]:
        if visited[next_v] == False:
            dfs(next_v)

 

1091. Shortest Path in Binary Matrix

https://leetcode.com/problems/shortest-path-in-binary-matrix/description/

 

---

우선순위 큐 Priority Queue

-> 완전 이진트리로 구현

우선순위의 정의 필요

 

Heap 자료구조

Priority Queue는 heap으로 구현하는게 가장 효율

min heap / max heap

(형제 노드간 대소관계 없음)

이진트리 - child node 0~2개

완전이진트리 - 위에서 아래로, 왼쪽에서 오른쪽으로 순서대로 child node가 채워져 있는 형태

 

완전 이진트리의 특성상 heap을 배열로 구현 가능

(index i인 노드의 child의 index는 2*i+1, 2*i+2)

 

heapify

import heapq

import heapq

pq = []
heapq.heappush(pq, 3)
print(heapq.heappop(pq))

heapq.heappush() ≒ enqueque
heapq.heappop() ≒ dequeque (root node를 pop) -> 재정렬

heappop() 이후 재정렬 방법

 

 

743. Network Delay Time

https://leetcode.com/problems/network-delay-time/description/

 

 

 

Dijkstra 알고리즘