반응형 [알고리즘] DFS/BFS 그래프 표현(인접행렬)- 각 행과 열은 노드를 의미- 무향 그래프일 경우 대각선 대칭- 가중치 그래프의 경우 1이 아닌 다른 값을 넣음으로 가중치 표현(인접 리스트)- 각 인덱스에 해당하는 노드에 연결된 노드들을 리스트 형태로 저장한느 방식- 가중치를 표현하기 위해서 연결정보에 튜플형태나 다른 방식으로 가중치를 추가적으로 입력DFS(Depth First Search)- 깊이 우선 탐색- 갈 수 있는 한 끝까지 탐색해 leaf node를 방문하고 이전 갈림길에서 선택하지 않았던 노드를 방문DFS 구현- stack을 활용더보기1. 시작노드를 방문 표시하고 스택에 넣기2. 스택이 비어있지 않은 동안 다음을 반복합니다.2-1. 스택의 최상단 노드를 꺼냅니다.2-2. 꺼낸 노드에 방문하지 않은 인접 노드가 있다면.. 2025. 9. 28. [코딩테스트] Python- 알고리즘 백트래킹코드더보기더보기ㅇ 예시더보기더보기ㅇ 정렬코드더보기더보기ㅇ 예시더보기더보기ㅇ 시뮬레이션코드더보기더보기ㅇ 예시더보기더보기ㅇ 동적계획법코드더보기더보기ㅇ 예시더보기더보기ㅇ 그리디코드더보기더보기ㅇ 예시더보기더보기ㅇ 2025. 2. 9. [코딩테스트] 3주차: 그래프 알고리즘 그래프 알고리즘학습 주제:그래프의 표현 방법 (인접 행렬, 인접 리스트)그래프 탐색 알고리즘 (DFS, BFS)최단 경로 알고리즘 (Dijkstra, Floyd-Warshall)학습 목표:그래프의 표현 방법을 이해하고 구현할 수 있다.깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS) 알고리즘을 이해하고 적용할 수 있다.다양한 최단 경로 알고리즘을 이해하고 문제에 적용할 수 있다.학습 자료:그래프의 표현 방법 설명 및 구현깊이 우선 탐색(DFS) 알고리즘 설명 및 구현너비 우선 탐색(BFS) 알고리즘 설명 및 구현Dijkstra 알고리즘 설명 및 구현Floyd-Warshall 알고리즘 설명 및 구현실습 문제:1. 그래프 표현 방법인접 행렬과 인접 리스트를 사용하여 그래프를 구현하세요.# 인접 행렬def .. 2024. 6. 4. [알고리즘] 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. [알고리즘] 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)# 최하단/최상단 원소 확인queue[0]queue[-1.. 2023. 10. 5. 이전 1 다음 반응형
