[알고리즘] 개념 정리

이분 탐색 / 이진 탐색이란, 오름차순으로 정렬된 리스트에서 검색 범위를 좁히면서 특정한 값을 검색하는 알고리즘이다.

그리디 알고리즘이란, 선택지를 결정할 때마다 그 때 최적인 값을 선택하는 방식으로 최적해를 구할 때 사용되는 근사적인 방법론이다.

그래프란 정점(Vertex)과 간선(Edge)으로 구성된 집합으로, 각 요소들 간의 연결 관계를 이진으로 표현하는 자료 구조이다.

위상 정렬이란 방향성이 있는 그래프에서 정점의 간선의 방향에 맞게 나열하는 방식의 정렬이다. 위상 정렬 동작 과정으로는 진출차수를 기반으로 하는 DFS와 진입차수를 기반으로 하는 BFS가 있다.

그래프 알고리즘이란, 그래프와 같은 복잡하고 연결성이 높은 자료구조에서 순회 (Graph Traversal), 탐색 및 검색 (Graph Search) 등과 같은 목적으로 사용되는 알고리즘이다. 주로 사용되는 그래프 알고리즘은 크게 5 가지로 정리할 수 있다.

그래프에서 간선을 하나씩 추가하면 최소 신장 트리를 만드는 방식의 알고리즘이다. 간선을 추가할 때는 그리디 알고리즘을 사용하여 선택 당시 가중치가 최소인 간선을 선택한다.

그래프에서 정점을 하나씩 추가하면 최소 신장 트리를 만드는 방식의 알고리즘이다. 정점을 추가할 때는 그리디 알고리즘을 사용하여 선택 당시 정점과 연결된 간선의 가중치가 최소인 정점을 선택한다.