6. 위상 정렬 (Topological Sorting)6.1 위상 정렬이란?📌 활용 사례 - 프로젝트 빌드 순서 (실제 사례 코드 추가)소프트웨어 프로젝트에서는 컴파일해야 할 파일들이 서로 의존성을 가짐예를 들어, main.o 파일을 빌드하기 위해 util.o, network.o를 먼저 빌드해야 함소스 코드 파일 간의 의존성을 DAG로 표현하여 위상 정렬을 수행하면 올바른 빌드 순서를 결정할 수 있음📌 프로젝트 의존성 그래프 (compile util.c) → (util.o) ↓ (compile main.c) → (main.o) ↓ (link)📌 프로젝트 빌드 순서 - 위상 정렬 코드 (Kahn’s Algorithm 활용)from collections import..

5. 최소 신장 트리 (MST, Minimum Spanning Tree)5.1 크루스칼 알고리즘 (Kruskal’s Algorithm)📌 단계별 실행 과정 (시각화)📌 입력 그래프 (0) / \ 1/ \4 / \ (1) ----- (2) \ / 3\ /2 \ / (3)📌 간선 정렬 후 선택 과정가중치 1 (0-1) 추가 → MST: {(0-1)}가중치 2 (2-3) 추가 → MST: {(0-1), (2-3)}가중치 3 (1-3) 추가 → MST: {(0-1), (2-3), (1-3)}가중치 4 (0-2) 추가하면 사이클 발생 → 제외📌 최종 MST (0) / 1/ / ..

4. 최소 비용 경로 알고리즘4.1 다익스트라 알고리즘 (Dijkstra’s Algorithm)📌 다익스트라의 제한 사항 및 주의할 점⚠ 음수 가중치가 있는 그래프에서는 사용할 수 없음⚠ 단일 출발점 기준 최단 경로만 계산 가능 (모든 정점 간 최단 경로를 원하면 플로이드-워셜 사용)📌 추가된 예제 그래프 (A) / \ 4/ \2 / \ (B) (C) \ / \ 7\ /3 1 \ / \ (D) (E) \ / 5/ (F)A → B = 4, A → C = 2, B → D = 7, C → D = 3, C → E = 1, D → F = 5, E → F ..

3. 그래프 탐색 (Graph Traversal)3.1 깊이 우선 탐색(DFS, Depth-First Search)📌 DFS 시간 및 공간 복잡도시간 복잡도인접 행렬 사용 시: 𝑂(𝑁²) (모든 정점을 확인해야 함)인접 리스트 사용 시: 𝑂(𝑁+E) (정점과 간선 개수에 비례)공간 복잡도𝑂(𝑁) (재귀 호출 또는 스택 사용)3.2 너비 우선 탐색(BFS, Breadth-First Search)📌 BFS 시간 및 공간 복잡도시간 복잡도인접 행렬 사용 시: 𝑂(𝑁²)인접 리스트 사용 시: 𝑂(𝑁+E)공간 복잡도𝑂(𝑁) (큐에 저장할 노드 개수)📌 DFS vs BFS 미로 찾기 (경로 출력 기능 추가, 입/출력 예시 포함)📌 미로 구조 예제0 0 1 01 0 1 00 0 0 00:..

2. 그래프 표현 방법2.1 인접 행렬(Adjacency Matrix)📌 정의 및 구현인접 행렬은 정점 간의 연결을 2차원 배열(행렬)로 표현하는 방법입니다.📌 무방향 그래프 (비가중치) A --- B \ / C이 그래프를 인접 행렬로 나타내면 다음과 같습니다. ABCA011B101C110📌 가중치 그래프 (Weighted Graph) A --(2)--> B \-(5)-→ C이 경우, 가중치를 행렬에 저장합니다. ABCA025B000C000📌 인접 행렬 구현 (Python)# 그래프 정의 (가중 방향 그래프)N = 3 # 정점 개수adj_matrix = [[0] * N for _ in range(N)] # N x N 2차원 배열 초기화# 간선 추가 (A=0, B=1, C=2..

1. 그래프 이론 기초1.1 그래프(Graph)란?📌 그래프의 정의그래프(Graph)는 정점(Vertex, Node)과 간선(Edge)으로 이루어진 자료 구조입니다.정점(Vertex, Node): 데이터를 저장하는 지점간선(Edge): 정점 간의 연결을 나타내는 선그래프는 다양한 현실 세계의 관계를 모델링하는 데 사용됩니다.📌 그래프의 활용 분야그래프는 연결된 데이터 구조를 표현할 때 매우 유용하며, 다음과 같은 분야에서 활용됩니다.1) SNS (소셜 네트워크 서비스)사용자와 친구 관계를 그래프로 표현할 수 있습니다.🔹 무방향 그래프: 친구 관계는 양방향입니다. A --- B --- C | | D --------- E📌 설명:A, B, C, D, E는 사용자A는 B, D와 ..