[알고리즘 공부] 그래프 알고리즘

그래프 알고리즘

 

 오늘은 그래프 알고리즘에 대해 알아보도록 하겠습니다 (이번에는 간단히 이론만 하고 다음부터는 문제풀이 위주로 글을 작성하도록 하겠습니다). 이전 DFS/BFS와 최단 경로에서 배운 내용은 그래프 알고리즘의 유형으로 볼 수 있습니다. 이외에도 그래프 알고리즘은 다양한 유형이 있지만 코딩 테스트에서 출제 비중이 낮다고 하네요! 하지만 꼭 제대로 알고 넘어가야하는 알고리즘이라고 합니다. 

 

 이번에도 <이코테>에 따라서 앞서 배운 내용들을 기반으로 하는 데, 크루스칼 알고리즘(Kruskal Algorithms)은 그리디 알고리즘으로 분류디고 위상 정렬 알고리즘(Topology Algorithms)은 앞서 배운 큐 자료 구조 혹은 스택 자료 구조를 활용해야 구현할 수 있습니다. 그럼 그래프 알고리즘에 대해서 간단히 알아보도록 하겠습니다. 

 

 먼저, Graph란 노드(Node)와 노드 사이에 연결된 간선(Edge)의 정보를 가지고 있는 자료 구조를 의미합니다. 이는 알고리즘 문제중에서 '서로 다른 개체가 연결되어 있다.'는 내용이 나오면 가장 먼저 그래프 알고리즘을 떠올려야합니다. 특히 그래프 자료 구조 중에서 트리(tree) 구조는 다양한 알고리즘에서 사용되기 때문에 꼭 기억하시길 바랍니다. 이전 다익스트라 최단 경로 알고리즘에서는 우선 순위 큐가 사용되었는데, 우선순위 큐를 구현하기 위해 최소 힙이나 최대 힙을 이용할 수 있습니다. 여기서 최소 힙은 항상 부모 노드가 자식 노드보다 크기가 작은 자료구조로서 트리 자료구조에 속하게 됩니다. 따라서 트리 자료구조는 부모에서 자식으로 내려오는 계층적인 모델에 속하게 됩니다. 

 

 그래프의 구현방법은 아래와 같이 2가지가 있습니다.

• 인접 행렬 : 2차원 배열 사용
• 인접 리스트 : 리스트 사용

  2가지 방식 모두 그래프 알고리즘에서 매우 많이 사용되고 메모리와 속도 측면에서 구별되는 특징을 가진다는 것을 기억해두시길 바랍니다~!

---

마무리

  일단 이번 글까지해서 코딩 테스트에서 출제되는 알고리즘들에 대해 간단히 살펴보았습니다. 이제는 다양한 문제를 접하고 이러한 문제를 풀기위해서 어떤 알고리즘 유형이 사용되고 문제를 어떻게 풀어가야하는지 위주의 글로 작성해보도록 하겠습니다. 상반기 공고는 계속되고 마음이 급해지는 경향이 있지만 마음을 진정시키고 천천히 그리고 꼼꼼하게 문제를 풀어가도록 해야겠습니다. 과정이 어떻게 될지는 모르겠지만 차분하게 하나씩 풀어가봅니다. 

 

 

참 고

2023.12.08 - [IT/관련 정보] - [코딩 테스트] 이것이 취업을 위한 코딩테스트다 with 파이썬

[코딩 테스트] 이것이 취업을 위한 코딩테스트다 with 파이썬