알고리즘 / 자료구조’ 시리즈

[이.취.코] Chap 10. 그래프 이론 - 개념

  • 0
  • 0
0
0

1. 배운 내용 복습

DFS/BFS와 최단 경로에서 다룬 내용은 모두 그래프 알고리즘의 한 유형으로 볼 수 있다. 그래프 알고리즘은 굉장히 다양한데, 코딩 테스트에서 출제 비중이 낮은 편이지만 꼭 제대로 알아야 하는 알고리즘이다.

크루스칼 알고리즘(Kruskal Algorithms)은 그리디 알고리즘으로 분류되며, 위상 정렬 알고리즘(Toplology Algorithms)은 큐 자료 구조 혹은 스택 자료구조를 활용해야 구현할 수 있다.

그래프(Graph)란 노드(Node)와 노드 사이에 연결된 간선(Edge)의 정보를 가지고 있는 자료구조를 의미한다. 알고리즘 문제를 접했을 떄 서로 다른 개체(혹은 객체) 가 연결되어 있다는 이야기를 들으면 가장 먼저 그래프 알고리즘이 떠올라야 한다. 여러 개의 도시가 연결되어 있다와 같은 내용이 등장하면 그래프 알고리즘을 의심해보자.

그래프 자료구조 중에서 트리(Tree) 자료구조는 다양한 알고리즘에 사용되므로 꼭 기억하자. 다익스트라 최단 경로 알고리즘에서는 우선순위 큐가 사용되었는데, 우선순위 큐를 구현하기 위해 최소 힙(Min Heap)이나 최대 힙(Max Heap)을 이용할 수 있다. 최소 힙은 항상 부모 노드가 자식 노드보다 크기가 작은 자료구조로서 트리 자료구조에 속한다. 트리 자료구조는 부모에서 자식으로 내려오는 계층적인 모델에 속한다. 컴퓨터 공학에서 트리는 방향 그래프라고 간주된다.

그래프트리
방향성방향 그래프, 무방향 그래프방향 그래프
순환성순환 및 비순환비순환
루트 노드의 존재 여부루트 노드가 없음루트 노드가 존재
노드간 관계성부모와 자식 관계 없음부모와 자식 관계
모델의 종류네트워크 모델계층 모델

그래프의 구현 방법은 아래와 같으며 그래프 알고리즘에서 많이 사용된다. 두 방식은 메모리와 속도 측면에서 구별되는 특징을 가진다.

V = 노드의 개수
E = 간선의 개수

인접 행렬(Adjacency Matrix)인접 리스트(Adjacency List)
요약2차원 배열을 사용하는 방식리스트를 사용하는 방식
메모리 공간간선 정보를 저장하기 위해 O(V^2)만큼의 메모리 공간 필요간선의 개수만큼인 O(E)만큼만 메모리 공간 필요
특정 노드 A에서 다른 특정 노드 B로 이어진 간선의 비용O(1) 시간으로 알 수 있다.O(V)만큼 시간이 소요된다.

우선순위 큐를 사용하는 다익스트라 최단 경로 알고리즘은 인접 리스트를 사용
플로이드 워셜 알고리즘은 인접 행렬을 사용

어떤 문제를 만나든 메모리와 시간을 염두에 두고 알고리즘을 선택해서 구현해야 한다. 노드의 개수가 적은 경우에는 플로이드 워셜 알고리즘을 이용할 수 있다. 노드와 간선의 개수가 모두 많으면 우선순위 큐를 이용하는 다익스트라 알고리즘을 이용하면 유리하다.

2. [서로소 집합 (Disjoint Sets)]

3. [신장 트리 (Spanning Tree)]

4. [위상 정렬 (Topology Sort)]

참고문헌

나동빈, "이것이 취업을 위한 코딩 테스트다 with 파이썬", 초판, 2쇄, 한빛미디어, 2020년

#코딩테스트 #파이썬 #나동빈 #한빛미디어 #이것이취업을위한코딩테스트다 #개념

0분전
작성된 댓글이 없습니다. 첫 댓글을 달아보세요!
    댓글을 작성하려면 로그인이 필요합니다.