[13강] 그래프(Graph)를 배우는 이유

---

안녕하세요 Gliver 입니다.

이번 글에서는 그래프(Graph)를 배우는 이유에 대해 알아보겠습니다.

 

목차

1. 그래프란 무엇인가?
2. 그래서 그래프가 어디에 쓰이는데?
3. 그래프를 배우는 이유
4. 그래프 공부의 상한선

 

 

그래프란 무엇인가?

정점과 간선으로 이루어진 구조를 그래프(Graph)라고 칭한다. (위키피디아)

보통 정점은 node 또는 vertex, 간선은 edge라고 부른다

 

아래의 그림1은 정점과 간선이 둘 다 존재하므로 그래프이지만, 그림2는 간선이 존재하지 않으므로 그래프가 아니다.

그림1

그림2

 

간선의 방향 유무에 따라 방향 그래프, 간선의 가중치 유무에 따라 가중 그래프,

서브 그래프를 컴포넌트라고 하는 등 그래프는 굉장히 다양한 개념을 가지는 데 이는 다음 장에서 살펴보도록 하겠다.

 

 

 

그래서 그래프가 어디에 쓰이는데?

위의 그래프 정의만 봐서는 도대체 어디에 쓰이는지 의문이 들 것이다.

 

그래서 이에 대한 답을 하기 전에 한 가지 질문을 던져 보겠다.

 

'그래프로 표현할 수 없는 상황이 있는가?'

 

내 경험상 어떠한 상황을 그래프로 표현할 수 없는 경우는 거의 없었다.

따라서, 그래프가 어떤 특정한 상황에서 쓰여서 중요하다기보단 대부분의 상황을 표현할 수 있어서 중요한 것이다!

 

TMI로 내가 배운 과목에서 그래프가 어디에 쓰였는지 간략하게 말해보겠다.

 

데이터베이스 같은 경우에 B-Tree, B+Tree 등 파일을 저장하는 구조에서 그래프가 쓰인다.

운영체제 같은 경우에 데드락의 자원 할당 그래프에서 그래프가 쓰인다.

데이터마이닝 같은 경우에 PageLank 알고리즘에서 그래프가 쓰인다.

딥러닝 같은 경우에 신경망 학습 구조에서 그래프가 쓰인다.

 

당연히, 이보다 더 많은 과목/분야에서 쓰이므로 그래프의 활용도는 굉장히 높다고 할 수 있겠다.

위의 내용들에서 그래프가 쓰인 다는 것이 안 와닿을 수 있지만, 그래프가 많이 쓰인다는 것만 기억하자

 

 

 

그래프를 배우는 이유

그래프를 배우는 이유는 위의 내용을 읽어보면 대충 감이 올 것이다.

 

그래프는 대부분의 상황을 표현할 수 있으며, 이 때문에 실무에서도 분야에 따라 꽤 자주 쓰인다.

이 때문에 코딩테스트 문제를 보면 보통 그래프 문제가 1개 정도는 출제된다

 

또한 다른 자료구조(리스트, 딕셔너리, 셋)와 같이 그 틀이 일정하지 않아 상황에 맞게 직접 구현해야 한다.

따라서, 그래프를 상황에 맞게끔 구현하는 것은 라이브러리의 몫이 아닌 개발자의 몫인 것이다.

 

이러한 점들이 그래프를 자유자재로 다루는 것이 중요한 이유이며 우리가 배워야 하는 이유라고 할 수 있다.

 

 

 

그래프 공부의 상한선

이제 그래프가 중요하며 개발을 하는 데에 있어 중요하다는 것은 알았을 것이다.

 

그렇다면, 그래프를 어느 정도 수준까지 공부하는 것이 좋을까?

 

이에 대한 답은 자신이 가려는 방향과 깊이에 따라서 달라진다.

만약, 자신이 프로그래밍 대회 수상을 목표로 하고 있다면 그 깊이는 전문서적에 나오는 수준까지 해야할 것이다.

만약, 자신이 코딩테스트 합격을 목표로 하고 있다면 그 깊이는 학부생 수준이면 될 것이다.

 

여기서는 '코딩테스트 합격을 목표로 한다면 어디까지 해야 할까'에 초점을 맞추어 살펴보자.

나의 '알고리즘 카테고리'의 '그래프 알고리즘'의 목차가 학부생 수준의 내용이므로 이를 기준으로 설명하겠다

 

그래프(Graph) 기본

이 장에서는 노드와 간선으로 이루어진 그래프를 코드로 어떻게 표현하는지를 배운다.
그래프를 코드로 표현할 때 쓰이는 방법은 크게 인접 리스트, 인접 행렬, 간선 리스트 3가지가 있다.

그래프(Graph) 순회 (DFS & BFS)

그래프를 코드로 표현할 줄 알았다면 이제는 처리를 할 수 있어야 한다.
이 장에서는 그 처리 중에서 가장 기본적인 처리인 그래프 순회에 대해서 배운다.
그래프 순회에 관한 알고리즘(방법)은 크게 DFS(Depth First Search)와 BFS(Breadth First Search) 2가지가 있다.

그래프(Graph) 최단 경로 알고리즘

그래프를 순회하는 것을 넘어서 어떤 정점 A에서 다른 정점 B로 가는 최단 경로를 알 수 있으면 좋지 않을까?
이 장에서는 이러한 처리를 하는 알고리즘에 대해서 배운다.
이러한 처리를 하는 알고리즘은 크게 벨만-포드, 다익스트라, 플로이드-워셜 3가지가 있다.

사이클이 없는 방향 그래프 (DAG)

그래프는 정점 A와 정점 B 중에서 무엇이 더 먼저냐에 대한 답을 할 수 없다.
배열 같은 경우는 인덱스가 낮은 원소가 먼저라고 할 수 있는 선형 구조이지만
그래프는 정점 간의 순서를 정의할 수 없는 비선형 구조이기 때문이다

하지만, 그래프도 어떠한 특수한 경우에 정점 간의 순서를 매길 수 있으며 이러한 그래프를 DAG(Directed Acyclic Graph)라고 한다.
그리고 이러한 DAG에서 정점의 순서에 따라 정렬하는 것을 위상 정렬(Topological Sort)이라고 한다.

이 장에서는 이러한 DAG와 위상 정렬에 대해서 배운다.

최소 신장 트리 (MST)

간선의 가중치가 있는 경우에 이 간선들의 가중치의 합을 구할 수 있을 것이다.
그리고 우리는 모든 두 정점 간의 경로가 존재하는 선에서 간선을 제거하는 연산을 할 수 있다고 가정해보자.
이때, 이러한 연산들의 결과로 간선들의 가중치의 합을 가장 작게 만든 그래프를 MST(Minimum Spanning Tree)라고 하는 것이다.
Minimum Spanning Graph가 아닌 Tree인 이유는 결과가 항상 Tree 형태가 나오기 때문이다
(물론, Tree도 Graph에 포함되기 때문에 Graph라고 해도 틀린 말은 아니다)

이 장에서는 MST에 대해서 배우고, 또 MST를 구할 때 쓰이는 자료구조(Union-Find) 알고리즘(Kruskal)에 대해서도 배운다.

 

 

이렇게 6개 정도의 카테고리를 공부하면 코딩테스트에서 나오는 그래프 문제는 모두 풀 수 있을 것이다.

이 6개 카테고리의 내용이 코딩테스트에서 나오는 그래프 개념의 상한선이라고 생각하면 된다

 

사실, 트리(Tree) 또한 그래프의 특수한 경우라고 말할 수 있고 중요하지만 여기에서는 언급하지 않았다.

시간이 된다면 트리(Tree)에 대해 설명하는 글도 올려 보도록 하겠다.

 

 

 

 

---

궁금한 점이나 코멘트는 댓글로 남겨주세요!

 

• 알고리즘 공부법 : https://gliver.tistory.com/6
• 알고리즘 목차: https://gliver.tistory.com/7