Linear Search
순차 탐색(Sequential Search)
정렬되어있지 않은 선형 자료구조에서 순차적으로 찾고 하는 데이터를 탐색하는 방법으로 가장 단순한 방식의 탐색이다.
public static int LinearSearch(int[] array, int target)
{
int count = 0;
for (int i = 0; i < array.Length; i++)
{
count++;
if(array[i] == target) return count;
}
return -1;
}정말 단순히 배열의 처음부터 끝까지 순회하며, 값(target)이 존재하는지 확인하는 과정을 거친다.
이진 탐색(Binary Search)
정렬이 되어있는 자료구조에서 2분할을 통해 탐색하는 방법으로, 정렬되어있는 자료구조에만 사용이 가능하다는 단점이 있으나 정렬되어있다는 가정하에 정말 빠르게 탐색이 가능한 방식이다.
public static int BinarySearch(int[] array, int target)
{
int low = 0;
int high = array.Length - 1;
int count = 0;
while(low <= high)
{
count++;
int mid = (low +high) / 2;
if(array[mid]>target)
{
high = mid - 1;
}
else if(array[mid]<target)
{
low = mid + 1;
}
else return count;
}
return -1;
}배열의 처음과 마지막 인덱스값을 더해 반으로 나누어 mid 인덱스를 구하고 해당 요소와 찾고자하는 값을 비교하여 배열을 줄여나가는 방식으로 구현되어있다. 이진 탐색이 얼마나 빠른지 순차 탐색과 비교해보자면 배열의 크기가 10000일 때 주어진 값을 찾는 탐색 횟수가 순차탐색은 평균 5000번, 이진 탐색은 평균 13번이 소요된다.
Non-Linear Search
비선형 자료 탐색은 트리나 그래프와 같은 비선형 구조의 모든 정점(데이터)을 탐색하는 것을 의미한다. 선형 구조와 달리 자료가 순차적으로 구성되어있지 않아 단순 반복문으로 처리하기 어렵다.
Breadth First Search(BFS)
너비 우선 탐색 방법인 BFS는 그래프의 분기를 만났을 때 모든 분기를 탐색한 뒤에 다음 깊이의 분기들을 탐색한다는 특징을 가지고 있다. 깊이 내려가지 않고, 먼저 분기를 확인한다는 특징 때문에 Queue를 활용하며, 탐색 이후 최단 경로를 보장해준다는 장점을 갖는다.
public static void BFS(bool[,] graph, int start, out bool[] visited, out int[] parent)
{
int size = graph.GetLength(0); // 정점의 수 표시
visited = new bool[size]; // 해당 정점의 방문 여부 표시
parent = new int[size]; // 해당 정점을 탐색한 정점 표시
for (int i = 0; i < size; i++)
{
visited[i] = false; // 방문된 적이 없을 때의 초기화 값
parent[i] = -1; // 나를 찾은 정점이 없을 때의 초기화 값
}
Queue<int> queue = new Queue<int>();
queue.Enqueue(start);
visited[start] = true;
while (queue.Count > 0)
{
int next = queue.Dequeue();
for (int vertex = 0; vertex < size; vertex++)
{
if (graph[next, vertex] == true &&
visited[vertex] == false)
{
queue.Enqueue(vertex);
visited[vertex] = true;
parent[vertex] = next;
}
}
}
}BFS 탐색을 하게 될 경우 out parameter로 방문 여부(visited)와 탐색 노드(parent)를 알 수 있게 되는데, 탐색 노드를 추적하여 나열한 것이 최단경로이다.
Depth First Search(DFS)
깊이 우선 탐색 방법인 DFS는 그래프의 분기를 만났을 때 해당 분기를 타고 내려가 끝까지 탐색한 뒤에 다른 분기를 확인하는 특징을 가지고 있다. 먼저 찾은 분기로 내려간다는 특징 때문에 Stack을 활용하며, 탐색 이후 최단 경로 보장을 할 수 없지만, 필요한 정점 데이터만 보관 가능하다는 장점을 갖는다. 보통 트리에서 활용되며, 그 이유는 트리의 경우 DFS를 사용해도 최단 경로가 보장되기 때문이다.
public static void DFS(bool[,] graph, int start, out bool[] visited, out int[] parent)
{
int size = graph.GetLength(0);
visited = new bool[size];
parent = new int[size];
for (int i = 0; i < size; i++)
{
visited[i] = false;
parent[i] = -1;
}
SearchNode(graph, start, visited, parent);
}
public static void SearchNode(bool[,] graph, int vertex, bool[] visited, int[] parent)
{
int size = graph.GetLength(0);
visited[vertex] = true;
for (int i = 0; i < size; i++)
{
if (graph[vertex, i] == true &&
visited[i] == false)
{
parent[i] = vertex;
SearchNode(graph, i, visited, parent);
}
}
}위에서 DFS 탐색의 경우 Stack을 활용한다고 했는데, 위 코드에서는 함수 스택을 사용하여 DFS를 구현한 것이다. 재귀 구조를 통해서 함수 스택을 쌓아 분기를 발견하면 타고 내려가도록 한 것이다.
Weight Graph Search
위에서 가중치가 없는 자료구조의 탐색 기법에 대해 알아보았다면, 여기서는 가중치 그래프의 탐색 기법을 알아보자. 보통 길찾기 알고리즘이라고 부르며, 가중치가 있는 경우 BFS 탐색으로 얻어낸 최단거리와 결과가 다를 수 밖에 없기에 조금 더 복잡한 알고리즘을 활용해야한다.
Dijkstra's Algorithm
다익스트라 알고리즘은 단일 출발지에서 모든 노드까지의 최단 경로를 찾는 알고리즘이다. 인접한 노드 중에 가장 짧은 거리를 선택하여 경로를 탐색하며 다음 일련의 로직을 가진다.
1. A에서 B로 가는 거리가 만약 C를 거쳐서 더 짧아지는 경우 AB를 AC + CB로 대체한다.
2. 이때 C 자리에 올 수 있는 후보들 중 계산 우선 순위는 가장 가까운 정점이 가장 높다. (AC < AD일 경우 C부터 탐색한다.)
const int INF = 99999;
public static void Dijkstra(int[,] graph, int start, out bool[] visited, out int[] parents, out int[] distance)
{
int size = graph.GetLength(0);
visited = new bool[size];
parents = new int[size];
distance = new int[size];
for (int i = 0; i < size; i++)
{
visited[i] = false;
parents[i] = -1;
distance[i] = INF;
}
distance[start] = 0;
for (int i = 0; i < size; i++)
{
int next = -1;
int minCost = INF;
for (int j = 0; j < size; j++)
{
if (!visited[j] && distance[j] < minCost)
{
next = j;
minCost = distance[j];
}
}
if (next < 0) break;
visited[next] = true;
for (int k = 0; k < size; k++)
{
if (distance[k] > distance[next] + graph[next, k])
{
distance[k] = distance[next] + graph[next, k];
parents[k] = next;
}
}
}
}다익스트라의 경우 distance 라는 지표 하나가 더 생성되는데, 이는 시작 정점과의 최단 거리를 의미한다. 해당 지표의 값은 탐색이 진행되며 계속 바뀌며, 탐색이 모두 끝났을 때 비로소 최단 경로를 의미하게된다. minCost는 단순히 2번 로직의 가장 가까운 정점을 찾기 위한 임시 변수로 이를 활용하여 가장 가까운 정점(next)을 j로 선정할 수 있게 된다.
distance[k]: 시작 정점부터 목적지(k)까지 직접 연결된 거리distance[next]: 시작 정점부터 중간점(next)까지의 거리graph[next,k]: 중간점부터 목적지까지의 거리
