그래프를 배우는 이유

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

안녕하세요 Gliver 입니다. 이번 글에서는 그래프(Graph)를 배우는 이유에 대해 알아보겠습니다. 목차 그래프란 무엇인가? 그래서 그래프가 어디에 쓰이는데? 그래프를 배우는 이유 그래프 공부의 상한선 그래프란 무엇인가? 정점과 간선으로 이루어진 구조를 그래프(Graph)라고 칭한다. (위키피디아) 보통 정점은 node 또는 vertex, 간선은 edge라고 부른다 아래의 그림1은 정점과 간선이 둘 다 존재하므로 그래프이지만, 그림2는 간선이 존재하지 않으므로 그래프가 아니다. 간선의 방향 유무에 따라 방향 그래프, 간선의 가중치 유무에 따라 가중 그래프, 서브 그래프를 컴포넌트라고 하는 등 그래프는 굉장히 다양한 개념을 가지는 데 이는 다음 장에서 살펴보도록 하겠다. 그래서 그래프가 어디에 쓰이는데..

https://gliver.tistory.com/34

1. 그래프의 정의

• 그래프는 정점과 간선으로 이루어진 자료구조이다.

2. 그래프가 쓰이는 분야

• 그래프는 데이터베이스, 운영체제, AI 등 여러 분야에서 사용된다.

• 따라서, 다양한 상황을 그래프로 표현할 수 있으므로 코딩테스트 문제로 많이 출제된다.

3. 그래프를 배우는 이유

• 그래프는 코딩테스트에서 자주 나오는 유형/주제에 해당한다.

• 그래프는 틀이 정해져 있지 않아 상황에 맞게 직접 코드로 구현해야 한다.
• 리스트, 딕셔너리, 셋과 같은 자료구조는 그 틀이 어느정도 정해져 있다.
• 따라서, 이러한 자료구조는 라이브러리가 존재하며 사용법만 숙지해도 충분한다.
• 하지만, 그래프의 경우 상황에 따라서 구현해야 하는 형식이 다르다.
• 따라서, 그래프는 원리를 이해하고 직접 구현할 수 있어야 코딩테스트 문제를 해결할 수 있다.

4. 그래프 공부의 상한선

• 코딩테스트에 나오는 수준은 컴공 학부생 수준 정도만 공부하면 된다.

• 공부해야 하는 내용들
• 그래프를 코드로 표현하는 방법
• 그래프 순회 알고리즘
• DFS
• BFS
• 그래프 최단 경로 알고리즘
• 다익스트라
• 벨만-포드
• 플로이드-워셜
• 사이클이 없는 방향 그래프 (DAG, Directed Acyclic Graph)
• DAG에 대한 개념
• 위상 정렬 알고리즘
• 최소 신장 트리 (MST, Minimum Spanning Tree)
• 유니온 파인드(Union-Find) 자료구조/알고리즘
• 크루스칼(Kruskal) 알고리즘
• 트리 (Tree)
• 트리의 정의
• 트리의 순회 (전위, 중위, 후위)