TIL#4

Day4: 파이썬을 무기로, 코딩테스트 광탈을 면하자!(2)

Heap, 동적계획법, DFS/BFS

을 배웠다.

Heap(힙)

import heap 으로 불러옴
-max heap
-min heap
-성질: 최대/최소 원소를 빠르게 찾을 수 있음
-연산: 힙 구성(heapify), 삽입(insert)-heappush, 삭제(remove)-heappop

동적계획법(Dynamic Program)

알고리즘의 진행에 따라 탐색해야 할 범위를 동적으로 결정함으로써 탐색 범위를 한정할 수 있음

DFS/BFS

깊이 우선 탐색(DFS) 는 한 정점에서 인접한 모든(아직 방문하지 않은) 정점을 방문한되, 각 인접 정점을 기준으로 깊이 우선 탐색을 끝낸 후 다음 정점으로 진행 => 스택을 이용함

너비 우선 탐색(BFS) 는 한 정점에서 인접한 모든(아직 방문하지 않은) 정점을 방문하고, 방문한 각 인접 정점을 기준으로 (방문한 순서에 따라 ) 또다시 너비 우선 탐색을 행함 => 큐를 이용함