Skip to content

Week3

Directory actions

More options

Directory actions

More options

Latest commit

 

History

History

Week3

readme.md

파일명 분류 설명
bfs_iterative.py 알고리즘 너비 우선 탐색(BFS)은 시작 노드에서 가까운 노드부터 넓게 탐색하는 방식으로, 최단 경로 찾기에 효과적입니다. 이 코드는 '선입선출(FIFO)' 구조의 큐(Queue) 자료구조를 사용하여 BFS를 반복문으로 구현하는 방법을 보여줍니다. collections.deque를 활용하여 효율적인 큐 동작을 보여줍니다.
bfs_shortest_path.py 알고리즘 BFS의 가장 강력한 특징 중 하나인 최단 경로 탐색 원리를 보여주는 코드입니다. 모든 간선의 가중치가 1로 동일할 때, BFS는 시작점에서부터 거리가 1, 2, ... 순서로 탐색하므로 목표 지점을 발견하는 순간 그 경로가 최단 경로가 됩니다. 큐에 (노드, 현재까지의 거리)를 함께 저장하여 거리를 계산합니다.
connected_components.py 알고리즘 그래프에서 서로 연결된 노드들의 묶음인 '연결 요소(Connected Components)'의 개수를 찾는 방법을 보여줍니다. 전체 노드를 순회하며 아직 방문하지 않은 노드를 새로운 연결 요소의 시작점으로 간주하고, DFS 탐색을 통해 연결된 모든 노드를 방문 처리하는 과정을 반복하여 개수를 셉니다.
dfs_iterative.py 알고리즘 재귀 호출의 깊이 제한 문제 등을 피하기 위해 스택(Stack)과 반복문을 사용하여 깊이 우선 탐색(DFS)을 구현하는 방법을 보여줍니다. '후입선출(LIFO)' 구조의 스택을 이용하여 가장 최근에 방문한 노드의 이웃부터 탐색하는 DFS의 동작 방식을 동일하게 구현합니다.
dfs_recursive.py 알고리즘 깊이 우선 탐색(DFS)의 가장 직관적인 구현 방식인 재귀 함수를 활용하는 방법을 보여줍니다. 한 방향으로 갈 수 있을 때까지 깊이 탐색하다가 막다른 길에 도달하면, 바로 직전 갈림길로 돌아와 다른 경로를 탐색하는 과정을 간결한 재귀 코드로 표현합니다.
graph_adjacency_list.py 자료구조 그래프를 표현하는 가장 일반적인 방법인 '인접 리스트(Adjacency List)'를 구현합니다. 딕셔너리를 사용하여 각 노드를 키(key)로, 해당 노드에 직접 연결된 이웃 노드들의 리스트를 값(value)으로 저장하는 방식으로, 특정 노드의 모든 이웃을 효율적으로 찾는 데 유리합니다.
graph_adjacency_matrix.py 자료구조 2차원 리스트(행렬)를 사용하여 그래프를 표현하는 '인접 행렬(Adjacency Matrix)' 방식을 보여줍니다. matrix[i][j]의 값이 1이면 두 노드가 연결되었음을, 0이면 연결되지 않았음을 의미합니다. 두 노드 간의 연결 여부를 O(1)의 빠른 속도로 확인할 수 있는 장점이 있습니다.
graph_conversion.py 자료구조 메모리 효율성이 중요한 경우 등 상황에 따라 그래프 표현 방식을 변환하는 방법을 보여줍니다. 메모리를 많이 차지할 수 있는 인접 행렬을, 실제 간선의 수만큼만 공간을 사용하는 인접 리스트로 변환하는 코드를 통해 두 방식의 장단점과 변환 로직을 이해할 수 있습니다.
maze_solver.py 알고리즘 2차원 리스트로 표현된 미로에서 출발점부터 도착점까지의 최단 경로를 찾는 문제를 BFS를 이용하여 해결합니다. 미로의 각 칸을 노드로, 상하좌우 이동을 간선으로 간주하여 그래프 탐색 문제로 변환하고, BFS를 통해 최단 경로를 찾는 과정을 보여주는 재미있는 예제입니다.
path_existence.py 알고리즘 그래프 탐색의 기본적인 활용 사례로, 두 노드 사이에 경로가 존재하는지 여부를 확인하는 방법을 보여줍니다. 시작 노드부터 DFS 또는 BFS 탐색을 시작하여 목표 노드에 도달할 수 있는지를 확인하는 간단하고 명확한 알고리즘을 제시합니다.