탐색

11/23 (자료 구조와 탐색, 수) TIL

(어제에 이은) 자료 구조:트리 : 완전 이진 트리의 경우 잎 노드에서 뿌리 노드까지 도달하는 데 O(logN)O(logN)O(logN) 단계가 필요함.힙 : 최대힙과 최소힙이 있음. 완전 이진 트리의 일종이므로 원소 추가와 삭제시 시간 복잡도는 최대 O(logN)O(logN)O(logN)이 된다.그래프 : 노드와 노드 사이의 연결 관계를 강조하여 나타낸 자료 구조. 인접 행렬과 인접 리스트로 표현할 수 있음. 트리와 그래프를 탐색하기:DFS(깊이 우선 탐색)과 BFS(너비 우선 탐색) 모두 인접 리스트를 데이터 삼아 구현을 연습했다. 인접 행렬로 표현한 버전이 연결 관계를 찾을 때 O(1)의 시간만으로 빠르게 찾는다던데, 정작 탐색을 할 때는 어떻게 활용해야 할지 모르겠다. 다이나믹 프로그래밍과 메..