728x90 [코딩테스트] 3주차: 그래프 알고리즘 그래프 알고리즘학습 주제:그래프의 표현 방법 (인접 행렬, 인접 리스트)그래프 탐색 알고리즘 (DFS, BFS)최단 경로 알고리즘 (Dijkstra, Floyd-Warshall)학습 목표:그래프의 표현 방법을 이해하고 구현할 수 있다.깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS) 알고리즘을 이해하고 적용할 수 있다.다양한 최단 경로 알고리즘을 이해하고 문제에 적용할 수 있다.학습 자료:그래프의 표현 방법 설명 및 구현깊이 우선 탐색(DFS) 알고리즘 설명 및 구현너비 우선 탐색(BFS) 알고리즘 설명 및 구현Dijkstra 알고리즘 설명 및 구현Floyd-Warshall 알고리즘 설명 및 구현실습 문제:1. 그래프 표현 방법인접 행렬과 인접 리스트를 사용하여 그래프를 구현하세요.# 인접 행렬def .. 2024. 6. 4. [알고리즘] Week 11: 그래프 알고리즘 II - 최단 경로 알고리즘과 최소 스패닝 트리 Day 1: 최단 경로 알고리즘 개요강의 내용:최단 경로 문제 정의최단 경로 문제란 무엇인가?단일 출발점 최단 경로와 모든 쌍 최단 경로 문제의 차이최단 경로 알고리즘의 응용 사례네비게이션 시스템네트워크 라우팅실습:최단 경로 문제를 해결할 기본적인 그래프 준비# 기본적인 그래프 준비graph = { 'A': {'B': 1, 'C': 4}, 'B': {'A': 1, 'C': 2, 'D': 5}, 'C': {'A': 4, 'B': 2, 'D': 1}, 'D': {'B': 5, 'C': 1}} Day 2: 다익스트라 알고리즘 (Dijkstra's Algorithm)강의 내용:다익스트라 알고리즘의 개념다익스트라 알고리즘의 정의 및 작동 원리우선순위 큐를 이용한 구현다익스트라 알고리즘의 시간.. 2024. 6. 2. [알고리즘] Week 10: 그래프 알고리즘 I - 개념과 탐색 알고리즘 Day 1: 그래프의 개념과 용어강의 내용:그래프의 정의와 중요성그래프란 무엇인가?그래프의 실생활 응용 사례 (소셜 네트워크, 지도, 인터넷 등)그래프의 기본 용어정점(Vertex)와 간선(Edge)방향 그래프(Directed Graph)와 무방향 그래프(Undirected Graph)가중치 그래프(Weighted Graph)와 비가중치 그래프(Unweighted Graph)인접 정점(Adjacent Vertices), 경로(Path), 차수(Degree)그래프의 종류유향 그래프와 무향 그래프연결 그래프와 비연결 그래프사이클(Cycle)과 비사이클(Acyclic)실습:파이썬을 사용한 그래프의 기본 구조 생성# 무방향 그래프의 예제 구현class Graph: def __init__(self): .. 2024. 6. 2. [자료구조] Week 9: 그래프 II - 그래프 탐색과 최단 경로 알고리즘 Day 1: 그래프 탐색 - 깊이 우선 탐색 (DFS)강의 내용:깊이 우선 탐색 (DFS)의 개념과 특징DFS의 정의 및 탐색 방식DFS의 시간 복잡도DFS의 구현재귀적 구현비재귀적 구현 (스택 사용)실습:DFS의 재귀적 구현 및 비재귀적 구현# 그래프 탐색 클래스 정의class Graph: def __init__(self, num_vertices): self.num_vertices = num_vertices self.adj_list = [[] for _ in range(num_vertices)] def add_edge(self, u, v): self.adj_list[u].append(v)# DFS 재귀적 구현def dfs_recursive(graph, v.. 2024. 6. 1. [자료구조] Week 8: 그래프 I - 그래프의 개념과 표현 방법 Day 1: 그래프의 기본 개념과 용어강의 내용:그래프의 정의와 특징그래프의 개념 (정점과 간선으로 이루어진 자료구조)방향 그래프와 무방향 그래프그래프의 기본 용어정점 (Vertex), 간선 (Edge), 인접 (Adjacent), 경로 (Path), 사이클 (Cycle), 연결성 (Connectivity)그래프와 트리의 차이실습:그래프의 기본 용어와 개념을 시각적으로 설명# 그래프의 기본 용어 설명# - 정점(Vertex): 그래프의 노드# - 간선(Edge): 정점 간의 연결# - 인접(Adjacent): 간선으로 연결된 두 정점# - 경로(Path): 정점과 간선의 연속# - 사이클(Cycle): 시작 정점과 끝 정점이 동일한 경로# - 연결성(Connectivity): 모든 정점이 연결된 상태# .. 2024. 6. 1. [알고리즘] 9. 기타 그래프 이론 Index 1. 서로소 집합 자료구조 2. 서로소 집합을 활용한 사이클 판별법 3. 최소 신장 트리(크루스칼 알고리즘) 4. 위상 정렬 5. 추천 문제 6. 참고자료 1. 서로소 집합 자료구조 Disjoint Sets - 공통 원소가 없는 두 집합 서로소 집합 자료구조(= Union Find) - 서로소 부분 집합들로 나누어진 원소들의 데이터를 처리하기 위한 자료구조 - 두 종류의 연산을 지원 - - Union: 두 개의 원소가 포함된 집합을 하나의 집합으로 합치는 연산 - - Find: 특정한 원소가 속한 집합이 어떤 집합인지 - 연결성을 통해 집합의 형태를 확인 (동작 과정) 1) Union 연산을 확인하여, 서로 연결된 두 노드 A, B를 확인 - A와 B의 루크 노드 A', B'를 각각 찾기 - .. 2023. 10. 5. [알고리즘] 7. 그래프 탐색 Index 1. 스택과 큐 2. 재귀 3. 유클리드 호제법 4. DFS 5. BFS 6. 추천 문제 7. 참고자료 - Search란 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정 - 그래프 탐색 알고리즘으로 DFS/BFS가 있음 1. 스택과 큐 Stack - FILO(First In Last Out)의 자료구조 - 입구와 출구가 동일 stack = [] # 삽입 stack.append(val) # 삭제 stack.pop() # 최상단 원소 확인 print(stack[-1]) Queue - FIFO(First In First Out)의 자료구조 - 입구와 출구가 양쪽으로 나있는 터널 형태 queue = [] # 삽입 queue.append(val) # 삭제 queue.pop(0) # 최하단/최상단 원.. 2023. 10. 5. 이전 1 다음 반응형
