트리: 계층형 트리 구조를 시뮬레이션 하는 추상 자료형(ADT)으로, 루트 값과 부모-자식 관계의 서브트리로 구성되며, 서로 연결된 노드의 집합 재귀로 정의된 자기 참조 자료구조 트리는 항상 하나의 루트(Root)에서 시작되며, 자식(Child) 노드를 가지고, 간선(Edge)으로 연결되어 있다 차수(Degree): 자식 노드의 개수, 크기(Size): 자신을 포함한 모든 자식 노드의 개수 높이(Height): 현재 위치에서부터 리프까지의 거리, 깊이(Depth): 루트에서부터 현재 노드까지의 거리 레벨은 루트에서 0이고, 노드 A의 자식노드는 A의 레벨 + 1 트리는 순환 구조를 갖지 않는 그래프, 단방향, 하나의 부모 노드, 하나의 루트 이진 트리: 가장 널리 사용되는 트리 자료구조 m-ary 트리(..
BFS
최단 경로 문제: 각 간선의 가중치 합이 최소가 되는 두 정점(또는 노드) 사이의 경로를 찾는 문제 정점: 교차로, 간선: 길, 가중치: 거리 & 시간 등의 이동 비용 다익스트라 알고리즘: 항상 노드 주변의 최단 경로만을 택하는 대표적인 그리디 알고리즘 -> BFS 이용 임의의 정점을 출발 집합에 더할 때, 그 정점까지의 최단거리는 계산이 끝났다는 확신을 가지고 더한다 743. network delay time - 다익스트라 알고리즘 -> 시작점에서 각 노드까지 최단시간 계산하고 저장(BFS) 및 계산되지 않는 노드 여부 확인 heapq 모듈에는 우선순위 업데이트 기능 없음 이전 노드의 값이 무엇인지 필요없으므로 생략 787. cheapest flights within k stops - 다익스트라 알고리..
그래프: 객체의 일부 쌍들이 연관되어 있는 객체 집합 구조 오일러 경로: 모든 간선(edge)을 한 번씩 방문하는 유한 그래프 경로(= 한붓그리기) 모든 정점(vertex)이 짝수 개의 차수(degree)를 갖는다면 오일러 경로 해밀턴 경로: 각 정점을 한 번씩 방문하는 무향 또는 유향 그래프 경로 최적 알고리즘이 없는 대표적인 NP-완전 문제 (NP문제 중 NP-난해 문제) 해밀턴 순환: 원래의 출발점으로 돌아오는 경로 외판원 문제: 최단거리인 해밀턴 순환을 찾는 문제 -> 다이나믹 프로그래밍으로 최적화 그래프 순회 (그래프 탐색): 그래프의 각 정점을 방문하는 과정 깊이 우선 탐색(DFS)이 너비 우선 남색(BFS)에 비해 더 널리 쓰임 DFS는 주로 스택이나 재귀로 구현(재귀 선호), BFS는 주로..
