1. 그래프의 정의
•
그래프는 정점과 간선으로 이루어진 자료구조이다.
•
정점과 간선으로 이루어짐 (그래프 O)
•
정점으로만 이루어짐 (그래프 X)
2. 그래프가 쓰이는 분야
•
그래프는 데이터베이스, 운영체제, AI 등 여러 분야에서 사용된다.
•
따라서, 다양한 상황을 그래프로 표현할 수 있으므로 코딩테스트 문제로 많이 출제된다.
3. 그래프를 배우는 이유
•
그래프는 코딩테스트에서 자주 나오는 유형/주제에 해당한다.
•
그래프는 틀이 정해져 있지 않아 상황에 맞게 직접 코드로 구현해야 한다.
◦
리스트, 딕셔너리, 셋과 같은 자료구조는 그 틀이 어느정도 정해져 있다.
▪
따라서, 이러한 자료구조는 라이브러리가 존재하며 사용법만 숙지해도 충분한다.
◦
하지만, 그래프의 경우 상황에 따라서 구현해야 하는 형식이 다르다.
▪
따라서, 그래프는 원리를 이해하고 직접 구현할 수 있어야 코딩테스트 문제를 해결할 수 있다.
4. 그래프 공부의 상한선
•
코딩테스트에 나오는 수준은 컴공 학부생 수준 정도만 공부하면 된다.
•
공부해야 하는 내용들
◦
그래프를 코드로 표현하는 방법
◦
그래프 순회 알고리즘
▪
DFS
▪
BFS
◦
그래프 최단 경로 알고리즘
▪
다익스트라
▪
벨만-포드
▪
플로이드-워셜
◦
사이클이 없는 방향 그래프 (DAG, Directed Acyclic Graph)
▪
DAG에 대한 개념
▪
위상 정렬 알고리즘
◦
최소 신장 트리 (MST, Minimum Spanning Tree)
▪
유니온 파인드(Union-Find) 자료구조/알고리즘
▪
크루스칼(Kruskal) 알고리즘
◦
트리 (Tree)
▪
트리의 정의
▪
트리의 순회 (전위, 중위, 후위)