c로 배우는 쉬운 자료구조 개정3판 8단원 연습문제

문서 내 토픽

1. 그래프

그래프에 관한 설명 중 옳은 문장은 2개입니다. 무방향 그래프를 인접 행렬로 표현하면 항상 대칭인 행렬이 되며, 무방향 그래프에서 모든 정점의 차수를 더하면 간선 수와 같습니다. 정점이 v개인 무방향 완전 그래프의 간선 수는 v^2개이며, 정점이 v개, 간선이 e개인 그래프를 인접 행렬로 표현하면 필요한 메모리는 O(v+e)입니다. 인접행렬로 표현된 그래프에서 너비 우선 탐색의 수행 시간은 O(v^2)입니다.
2. 그래프 표현

그래프는 정점 집합 V와 간선 집합 E로 이루어집니다. 정점이 a,b,c 세 개 존재하고 간선이 a와 b사이에 하나, b와 c 사이에 하나 존재한다면, 정점 집합 V는 V={a,b,c}이고 간선 집합 E는 E={(a,b),(b,c)}로 표현할 수 있습니다.
3. 그래프 탐색

깊이 우선 탐색에서 크루스칼 알고리즘은 최소비용신장트리를 구하는 데 사용되며, 너비 우선 탐색에서 노드 1부터 시작하여 수행할 경우 1-2-3-4-5-6-7-8의 순서로 탐색할 수 있습니다. 인접 리스트로 표현된 그래프에 대해 노드 0부터 시작하여 깊이 우선 탐색을 수행하면 0,1,3,2,5,6,4의 순서로 탐색할 수 있습니다.
4. 최소 비용 신장 트리

최소 비용 신장 트리는 가중치 그래프에서 가중치 합이 최소인 신장 트리를 말합니다. 크루스칼 알고리즘과 프림 알고리즘을 이용해 최소 비용 신장 트리를 구할 수 있습니다. 크루스칼 알고리즘은 가중치가 낮은 간선부터 삽입하여 트리를 구축하고, 프림 알고리즘은 하나의 정점에서 시작하여 가중치가 가장 낮은 간선부터 삽입하여 트리를 확장합니다.
5. 최단 경로 알고리즘

다익스트라 알고리즘은 하나의 정점을 출발점으로 삼고 다른 모든 정점을 도착점으로 하는 단일점에서의 최단 경로를 찾는 알고리즘입니다. 이 알고리즘은 distance[w] <- min(distance[w], distance[u] + weight[u][w]) 식을 사용하여 최단 경로를 계산합니다.

Easy AI와 토픽 톺아보기

1. 그래프

그래프는 데이터 구조와 알고리즘 분야에서 매우 중요한 개념입니다. 그래프는 노드(vertex)와 간선(edge)으로 구성되며, 이를 통해 다양한 실세계 문제를 모델링할 수 있습니다. 그래프는 사회 네트워크 분석, 교통 네트워크 최적화, 웹 페이지 랭킹 등 다양한 분야에서 활용됩니다. 그래프 이론은 컴퓨터 과학, 수학, 물리학 등 여러 학문 분야에서 깊이 연구되고 있으며, 앞으로도 중요한 역할을 할 것으로 예상됩니다.
2. 그래프 표현

그래프를 표현하는 방법에는 인접 행렬, 인접 리스트, 간선 리스트 등 다양한 방법이 있습니다. 각각의 표현 방법은 장단점이 있으며, 문제의 특성과 요구사항에 따라 적절한 표현 방법을 선택해야 합니다. 인접 행렬은 메모리 사용이 많지만 간선 접근이 빠르고, 인접 리스트는 메모리 사용이 적지만 간선 접근이 상대적으로 느립니다. 간선 리스트는 간선 정보만 저장하므로 메모리 사용이 가장 적지만 노드 정보 접근이 어렵습니다. 그래프 문제를 해결할 때는 이러한 표현 방법의 특성을 잘 이해하고 활용해야 합니다.
3. 그래프 탐색

그래프 탐색은 그래프 내의 노드와 간선을 체계적으로 방문하는 과정입니다. 대표적인 그래프 탐색 알고리즘으로는 깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS)이 있습니다. DFS는 한 경로를 끝까지 탐색한 뒤 다른 경로로 이동하는 방식이며, BFS는 한 레벨의 노드들을 모두 탐색한 뒤 다음 레벨로 이동하는 방식입니다. 이 두 알고리즘은 각각 장단점이 있어 문제의 특성에 따라 적절히 선택해야 합니다. 그래프 탐색은 최단 경로 찾기, 연결 요소 찾기, 사이클 탐지 등 다양한 그래프 문제를 해결하는 데 활용됩니다.
4. 최소 비용 신장 트리

최소 비용 신장 트리(Minimum Spanning Tree, MST)는 그래프의 모든 노드를 연결하면서 간선의 총 가중치가 최소가 되도록 하는 트리 구조입니다. MST는 네트워크 설계, 전력망 구축, 통신망 구축 등 다양한 분야에서 활용됩니다. 대표적인 MST 알고리즘으로는 Kruskal 알고리즘과 Prim 알고리즘이 있습니다. Kruskal 알고리즘은 가중치가 가장 작은 간선부터 선택하여 MST를 구성하고, Prim 알고리즘은 특정 노드에서 시작하여 인접한 간선 중 가중치가 가장 작은 간선을 선택하여 MST를 구성합니다. 이 두 알고리즘은 각각 장단점이 있어 문제의 특성에 따라 적절히 선택해야 합니다.
5. 최단 경로 알고리즘

최단 경로 알고리즘은 그래프에서 두 노드 간의 최단 경로를 찾는 알고리즘입니다. 대표적인 최단 경로 알고리즘으로는 Dijkstra 알고리즘, Bellman-Ford 알고리즘, Floyd-Warshall 알고리즘 등이 있습니다. Dijkstra 알고리즘은 단일 출발점에서 모든 노드까지의 최단 경로를 찾는 알고리즘이며, Bellman-Ford 알고리즘은 음의 가중치를 가진 간선이 있는 경우에도 최단 경로를 찾을 수 있습니다. Floyd-Warshall 알고리즘은 모든 노드 쌍 간의 최단 경로를 찾는 알고리즘입니다. 이러한 최단 경로 알고리즘은 교통 네트워크 최적화, 통신망 설계, 물류 관리 등 다양한 분야에서 활용됩니다.

주제 연관 리포트도 확인해 보세요!