1. 📖 순차탐색(Sequential Search)
순차 탐색은 말그대로 순차적으로 찾고자 하는 데이터를 찾을 때 사용하는 알고리즘입니다.
리스트나 배열의 데이터를 처음부터 끝까지 차례대로 비교하면서 원하는 값을 찾는거죠.
순차 탐색은 정렬되어 있지 않아도 사용할 수 있어서 구현이 비교적 간단합니다.
하지만 리스트나 배열의 크기가 커질수록 탐색 시간이 길어지기 때문에 효율성이 떨어지는 문제가 있습니다.
그래서 보통은 간단한 검색기능을 구현할 때 사용합니다.
시간 복잡도: O(n)
공간 복잡도: O(1)
1-2 🖥️ 순차탐색 구현
pubilc static int SequentialSearch1(int[] array, int target) // 배열 이용
{
for (int i = 0; i < array.Length; i++)
{
if (array[i] == target)
{
return i;
}
}
return -1;
}
public static int SequentialSearch<T>(IList<T> list, in T item) where T : notnull // 리스트 이용
{
for (int i = 0; i < list.Count; i++)
{
if (list[i].Equals(item))
{
return i;
}
}
return -1;
}2. 📖 이진탐색(Binay Search)
이진탐색의 경우 순차탐색과 마찬가지로 배열과 리스트에서 특정값을 탐색하는 것은 동일하나
절반으로 나누어 분할한 다음 특정한 값을 찾는 것이 차이점입니다.
그리고 이진탐색은 정렬이 되어있지 않으면 사용할 수 없는 것이 특징입니다.
탐색 범위를 절반씩 줄이면서 찾기 때문에 순차탐색과 달리 빠른 속도를 가집니다.
시간 복잡도: O(log n)
공간 복잡도: O(1)
2-1 🔖 이진 탐색의 동작 원리
✅ 중간 값 선택
배열이나 리스트의 중간 값 선택합니다.
✅ 비교 및 분할
찾고자 하는 값과 중간 값을 비교하여 찾고자 하는 값이 중간 값보다 크면 오른쪽, 작으면 왼쪽을 선택합니다.
✅ 반복
선택한 절반에서 다시 중간 값을 선택하고 비교하는 과정을 반복합니다.
✅ 종료
값을 찾거나 더 이상 나눌 수 없는 경우 탐색을 종료합니다.
2-2 🖥️ 이진탐색 구현
public static int BinarySearch1(int[] array, int target) // 배열 이용
{
int low = 0;
int high = array.Length - 1;
while (low <= high)
{
int mid = (low + high) / 2;
if (array[mid] > target)
{
high = mid - 1;
}
else if (array[mid] < target)
{
low = mid + 1;
}
else
{
return mid;
}
}
return -1;
}
public static int BinarySearch<T>(IList<T> list, in T item) where T : IComparable<T> // 리스트 이용
{
int low = 0;
int high = list.Count - 1;
while (low <= high)
{
int middle = (low + high) / 2;
int compare = list[middle].CompareTo(item);
if (compare < 0)
{
low = middle + 1;
}
else if (compare > 0)
{
high = middle - 1;
}
else
{
return middle;
}
}
return -1;
}3. 📖 비선형 자료구조 탐색 알고리즘
3-1 🔖 깊이 우선 탐색 (Depth-First Search)
경로를 끝까지 탐색한 후 다른 경로를 탐색하는 방식입니다.
즉 그래프의 분기를 만났을 때 최대한 깊이 내려간 뒤, 분기의 탐색을 마쳤을 때 다음 분기를 탐색하는 식으로 진행되는 탐색 과정입니다.
깊이 우선 탐색의 경우 탐색 상황에서 필요한 정점 데이터만 보관 가능하고 탐색이 끝나면 버리는 특징을 가지고 있습니다.
최단경로를 보장하지 않는 단점이 있지만 트리는 경로가 하나 밖에 없기 때문에
트리로 구현하는 것이 유리합니다.
3-1-1 ✔️ DFS 구현 원리
깊이 우선 탐색은 스택으로 구현합니다.
A
/ \
B C
/ \ \
D E F
시작 노드 : A 노드에서 시작합니다.
①
A 노드를 방문하고 출력합니다.
A의 인접 노드 중 방문하지 않은 노드를 선택합니다. 먼저 B를 선택합니다.
A -> {B}
②
B 노드를 방문하고 출력합니다.
B의 인접 노드 중 방문하지 않은 노드를 선택합니다. D와 E가 있지만, D를 먼저 선택합니다.
B -> {D}
③
D 노드를 방문하고 출력합니다.
D의 인접 노드는 없으므로 되돌아가서 E를 선택합니다.
B -> {E}
④
E를 방문하고 출력합니다.
E의 인접 노드가 없으므로 되돌아가서 C를 선택합니다.
E -> { }
⑤
C를 방문하고 출력합니다.
C의 인접 노드는 F이므로 F를 선택합니다.
C -> {F}
⑥
F를 방문하고 출력합니다.
3-1-2 🖥️ DFS 구현 코드
public static void DFS(bool[,] graph, int start, out bool[] visited, out int[] parents)
{
int size = graph.GetLength(0);
visited = new bool[size];
parents = new int[size];
for (int i = 0; i < size; i++)
{
visited[i] = false;
parents[i] = -1;
}
SearchNode(graph, start, visited, parents);
}
private static void SearchNode(bool[,] graph, int vertex, bool[] visited, int[] parents)
{
int size = graph.GetLength(0);
visited[vertex] = true;
for (int i = 0; i < size; i++)
{
if (graph[vertex, i] && // 연결되어 있는 정점이며,
!visited[i]) // 방문한적 없는 정점
{
parents[i] = vertex;
SearchNode(graph, i, visited, parents);
}
}
}3-2 🔖 너비 우선 탐색 (Breadth-First Search)
너비 탐색 시작 정점에서 가까운 정점부터 먼 정점으로 순차적으로 탐색하는 방식인데
그래프의 분기를 만났을 때 모든 분기들을 탐색한 뒤, 다음 깊이의 분기들을 탐색합니다.
앞에서 본 DFS은 해당 분기에 들어가면 깊게 내려간 다음에 다음 분기로 갔다면 BFS의 경우 모든 분기를 탐색하면서 깊이 내려가는 특징을 가지고 있는 것이 차이점입니다.
너비 우선 탐색은 최단 경로를 보장하는 장점은 잇지만 현재 탐색 상황에서 필요하지 않은 정점 데이터도 큐에 보관하면서 진행되는 단점을 가지고 있습니다.
최단 경로를 찾아주기 때문에 그래프로 구현하는 것이 더 유리한 면이 있습니다.
3-2-1 ✔️ BFS 구현 원리
너비우선탐색은 큐로 구현합니다.
A
/ \
B C
/ \ \
D E F
/ \ / \
G H I J시작 노드 : A 노드에서 시작
①
A 노드를 방문하고 출력합니다.
A의 인접 노드 중 방문하지 않은 노드를 선택합니다. B와 C를 선택합니다.
A -> {B, C}
②
B, C 노드를 방문하고 출력합니다.
B의 인접 노드 중 방문하지 않은 노드를 선택합니다. D와 E를 선택합니다.
C의 인접 노드 중 방문하지 않은 노드를 선택합니다. F를 선택합니다.
B -> {D, E}
C -> {F}
③
D, E, F 노드를 방문하고 출력합니다.
D의 인접 노드 중 방문하지 않은 노드를 선택합니다. G와 H를 선택합니다.
E의 인접 노드가 없으므로 끝납니다.
F의 인접 노드 중 방문하지 않은 노드를 선택합니다. J와 K를 선택합니다.
D -> {G, H}
E -> { }
F -> {I, J}
④
G, H, I, J 노드를 방문하고 출력합니다.
G, H, I, J 노드 모두 인접노드가 없으므로 끝냅니다.
G -> { }
H -> { }
I -> { }
J -> { }
이런 식으로 가까운 정점부터 순차적으로 탐색하고 그 정점과 인접한 모든 분기들을 탐색한 뒤, 다음 깊이의 분기들을 탐색하는 방식으로 반복하는 방식입니다.
3-2-2 🖥️ BFS 구현 코드
public static void BFS(bool[,] graph, int start, out bool[] visited, out int[] parents)
{
int size = graph.GetLength(0);
visited = new bool[size];
parents = new int[size];
for (int i = 0; i < size; i++)
{
visited[i] = false;
parents[i] = -1;
}
Queue<int> queue = new Queue<int>();
queue.Enqueue(start);
visited[start] = true;
while (queue.Count > 0)
{
int next = queue.Dequeue();
for (int i = 0; i < size; i++)
{
if (graph[next, i] &&
!visited[i])
{
visited[i] = true;
parents[i] = next;
queue.Enqueue(i);
}
}
}
}4. 📖 가중치 그래프인 경우 탐색 알고리즘
4-1 🔖 다익스트라 알고리즘 (Dijkstra's Algorithm)
앞에서 배운 BFS의 경우 최단 경로를 찾는 알고리즘이라고 언급했었는데
이는 가중치가 없는 그래프에서만 적용되는 내용입니다.
다익스트라 알고리즘은 가중치 그래프에서 최단경로를 찾는 알고리즘입니다.
여기서 음의 가중치를 포함한 그래프에는 적용할 수 없습니다.
다익스트라의 경우 특정한 한 노드에서 각 모든 노드까지의 최단거리를 찾는 알고리즘입니다.
알고리즘 작동 원리는 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택 후, 해당 노드를 거쳐 다른 노드로 가는 비용 계산하는 식으로 진행됩니다.
4-1-1 ✔️ 다익스트라 알고리즘 원리
① 시작 정점을 설정합니다.
② 시작 정점에서의 거리를 0으로 설정하고 모든 정점의 거리는 무한대로 초기화합니다.
③ 현재 정점에서 인접 정점으로 가는 경로의 거리를 계산하여 기존 거리보다 짧으면 업데이트합니다.
④ 아직 방문하지 않은 정점들 중에서 가장 거리가 짧은 정점을 선택하고,
해당 정점을 새로운 현재 정점으로 설정합니다. 여기서 ③ 과정을 수행합니다.
⑤ 모든 정점을 방문할 때까지 이 과정을 반복합니다.
4-1-2 🖥️ 다익스트라 알고리즘 구현코드
public static void ShortestPath(int[,] graph, int start, out bool[] visited, out int[] distance, out int[] parents)
{
int size = graph.GetLength(0);
visited = new bool[size];
distance = new int[size];
parents = new int[size];
for (int i = 0; i < size; i++) // 초기값 넣기
{
distance[i] = INF;
parents[i] = -1;
visited[i] = false;
}
distance[start] = 0;
for (int i = 0; i < size; i++)
{
// 1. 방문하지 않은 정점 중 가장 가까운 정점부터 탐색
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;
// 2. 직접연결된 거리보다 거쳐서 더 짧아진다면 업데이트
for (int j = 0; j < size; j++)
{
// distance[j] : 목적지까지 직접 연결된 거리
// distance[next] : 탐색중인 정점까지 거리
// graph[next, j] : 탐색중인 정점부터 목적지의 거리
if (distance[j] > distance[next] + graph[next, j])
{
distance[j] = distance[next] + graph[next, j];
parents[j] = next;
}
}
}
}