포시코딩

최단 경로 문제란? 두 노드를 잇는 가장 짧은 경로를 찾는 문제 가중치 그래프(Weighted Graph)에서 간선(Edge)의 가중치 합이 최소가 되도록 하는 경로를 찾는 것이 목적 문제 종류 단일 출발 및 단일 도착 그래프 내의 특정 노드 u에서 출발, 또 다른 특정 노드 v에 도착하는 가장 짧은 경로를 찾는 문제 단일 출발 그래프 내의 특정 노드 u와 그래프 내 다른 모든 노드 각각의 가장 짧은 경로를 찾는 문제 출발점이 A라고 한다면 A가 아닌 각각 다른 노드들 간의 최단 경로를 찾는걸 의미 다익스트라 알고리즘이 여기에 해당됨 전체 쌍(all-pair) 그래프 내의 모든 노드 쌍(u, v)에 대한 최단 경로를 찾는 문제 다익스트라 알고리즘 첫 정점을 기준으로 연결되어 있는 정점들을 추가해가며 최단..

개요 대표적인 그래프 탐색 알고리즘 너비 우선 탐색(Breadth First Search:BFS) 정점들과 같은 레벨에 있는 노드들(형제 노드들)을 먼저 탐색하는 방식 깊이 우선 탐색(Depth First Search:DFS) 정점의 자식들을 먼저 탐색하는 방식 예제 BFS 방식: A - B - C - D - G - H - I - E - F - J * 한 단계씩 내려가면서, 해당 노드와 같은 레벨에 있는 노드들(형제 노드들)을 먼저 순회한다. DFS 방식: A - B - D - E - F - C - G - H - I - J * 한 노드의 자식을 타고 끝까지 순회한 후, 다시 돌아와서 다른 형제들의 자식을 타고 내려가며 순회한다. 구현 파이썬에서는 딕셔너리와 리스트 자료 구조를 활용해 그래프를 표현할 수 ..

그래프(Graph)란? 노드(Node)와 간선(Edge)로 이루어진 자료구조. 노드(Node): 위치를 뜻한다. 버텍스(Vertex), 정점이라고도 불림 간선(Edge): 위치 간의 관계를 표시한 선. 노드를 연결한 선으로 링크(link) 또는 브랜치(branch)라고도 한다. 인접 정점(Adjacent Vertex): 간선으로 직접 연결된 노드 참고용어 정점의 차수(Degree): 무방향 그래프에서 하나의 정점에 인접한 정점의 수 진입 차수(In-Degree): 방향 그래프에서 외부에서 오는 간선의 수 진출 차수(Out-Degree): 방향 그래프에서 외부로 향하는 간선의 수 경로 길이(Path Length): 경로를 구성하기 위해 사용된 간선의 수 단순 경로(Simple Path): 처음 정점과 끝 ..

그래프란? 연결되어있는 원소간의 관계를 표현한 자료구조 비선형 구조는 표현에 초점이 맞춰져있고 선형 구조는 자료를 저장하고 꺼내는 것에 초점이 맞춰져 있는 반면, 그래프 자료구조는 연결 관계에 초점이 맞춰져 있다. 그래프 용어 노드(Node): 연결 관계를 가진 각 데이터를 의미. 정점(Vertax)이라고도 한다. 간선(Edge): 노드 간의 관계를 표시한 선. 인접 노드(Adjacent Node): 간선으로 직접 연결된 노드(또는 정점) 그래프의 종류 유방향 그래프(Directed Graph): 방향이 있는 간선을 갖는다. 간선은 단방향 관계를 나타내며, 각 간선은 한 방향으로만 진행할 수 있다. 무방향 그래프(Undirected Graph): 방향이 없는 간선을 갖는다. 무방향 그래프의 표현방법 1...