미새문지

깊이 우선 탐색(DFS, depth-first search) 깊이 우선 탐색(DFS)은 그래프의 모든 노드를 탐색하는데 사용되는 알고리즘 중 하나이다. 루트 노드에서 시작해 한 방향으로(주로 왼쪽부터) 들어갈 수 있는한 끝까지 탐색하여 더 이상 들어갈 수 없는 경우, 가장 최근의 분기점으로 돌아가 다른 방향의 노드를 탐색하는 방식으로 진행된다. DFS의 구현 // 그래프를 인접 리스트 형태로 표현 const graph = { A: ['B', 'C'], B: ['A', 'D', 'E'], C: ['A', 'F'], D: ['B'], E: ['B', 'F'], F: ['C', 'E'] }; // DFS 함수 정의 function dfs(graph, startNode) { let visited = []; //..

힙(heap) 최댓값과 최솟값을 찾는 연산을 빠르게 하기 위해 고안된 완전이진트리를 기본으로 하는 자료구조 특징 a가 b의 부모노드면 a의 키값과 b의 키값 사이에는 대소 관계가 성립한다. 최소 힙 : 부모 노드의 키값이 자식 노드의 키값보다 항상 작은 힙 최대 힙 : 부모 노드의 키값이 자식 노드의 키값보다 항상 큰 힙 ​ 힙 자료구조 파이썬 힙 모듈은 heapq라는 알고리즘 라이브러리를 제공 내장 모듈이기 때문에 설치할 필요없이 사용가능 모든 부모 노드는 자식 노드보다 값이 작거나 큰 이진 트리 구조인데, 내부적으로는 인덱스 0에서 시작해 n번 째 원소가 항상 자식 원소들보다(2n+1, 2n+2)보다 작거나 최소 힙의 형태로 정렬 기능 heapq.heappush(heap, item) : item을 h..

그래프(Vertex, edge, node, arc) 구조 정점(Vertex) 그래프의 기본 단위로, 위치나 상태 등을 표현, 노드(Node)라고 부른다 간선(Edge) 두 개의 정점을 연결하는 선을 말하며 두 정점 사이의 관계나 거리 등을 표현 노드(Node) 간선과 같은 의미이며 특정 상태나 위치를 나타내는 점(dot) 그래프에서 점으로 표현 호(Arc) 방향성이 있는 간선을 의미. 두 정점을 연결하는 선이지만, 한 정점에서 다른 정점으로 방향이 정해져 있다. ​ 그래프는 정점과 정점들을 연결하는 간선으로 구성 그래프는 정점과 간선의 집합으로 이루어진 자료구조이다. 특징 방향성 방향성이 있는 그래프를 유향 그래프(Directed Graph) 방향성이 없는 그래프를 무향 그래프(Undirected Gra..