탐색 알고리즘(Search Algorithm)
- 주어진 데이터 세트에서 특정한 값을 찾는 과정과 방법
선형 탐색(Linear Search)
- 탐색 시작 위치를 배열의 첫 번째 원소로 초기화.
- 현재 위치의 원소를 찾고자 하는 값과 비교.
- 값이 일치하면 해당 위치를 반환하고 탐색 종료.
- 값이 일치하지 않으면 다음 위치로 이동하여 비교를 반복.
- 배열의 끝까지 비교해도 찾는 값이 없으면 탐색을 종료.
int SequentialSearch(int[] arr, int target)
{
for (int i = 0; i < arr.Length; i++)
{
if (arr[i] == target)
{
return i;
}
}
return -1;
}
이진 탐색(Binary Search)
- 데이터가 정렬되어 있을 때 사용, 탐색 범위의 시작과 끝을 나타내는 두개의 위치점를 설정.
- 중간에 위치한 원소를 선택하고 이를 찾고자 하는 값과 비교
- 만약 중간 원소가 찾고자 하는 값과 일치하면 탐색 종료, 해당 원소의 위치 반환.
- 중간 원소가 찾고자 하는 값보다 작다면 탐색 범위의 시작 위치점를 중간 위치보다 하나 뒤로 이동.
- 중간 원소가가 찾고자 하는 값보다 크다면 탐색 범위의 끝 위치점을 중간 위치보다 하나 앞으로 이동.
- 탐색 범위가 충분히 줄어들어 값을 찾을 때까지 위 과정을 반복.
int BinarySearch(int[] arr, int target)
{
int left = 0;
int right = arr.Length - 1;
while (left <= right)
{
int mid = (left + right) / 2;
if (arr[mid] == target)
{
return mid;
}
else if (arr[mid] < target)
{
left = mid + 1;
}
else
{
right = mid - 1;
}
}
return -1;
}
그래프(Graph)
- 여러 객체 사이의 연결 관계를 표현하는 자료 구조.
- 정점(Vertex) (노드(Node)라고도 불리움) 과 간선(Edge)로 구성되며 간선이 정점을 연결하여 그래프를 형성.
- 무방향 그래프(Undirected Graph): 간선에 방향이 없는 그래프로, 간선을 통해 정점들이 양방향으로 연결됨. 이때, 무방향 그래프에서 특정 정점에 연결된 간선의 수를 정점의 차수(Degree)라고 함.
- 방향 그래프(Directed Graph): 간선에 방향이 있는 그래프로, 간선이 한 방향으로만 이동.
- 가중 그래프(Weighted Graph): 간선에 가중치가 할당된 그래프로, 경로의 가중치 합이 최소나 최대가 되는 경로를 찾는 문제에 사용됨. 가중치(Weight)는 간선에 할당된 값을 의미하며 경로(Path)는 정점과 간선을 번갈아가며 이동하는 순서를 의미함.
깊이 우선 탐색(DFS)
- 한 노드에서 시작하여 가능한 먼저 하나의 가지로 깊이 탐색을 진행하고, 더 이상 진행할 수 없을 때 다시 뒤로 돌아와 다른 가지를 탐색하는 탐색 방법.
- 스택을 이용하면 명시적으로 스택을 만들어서 탐색 순서를 관리하여 구현이 가능함.
- 재귀를 이용하면 시스템 스택을 활용하여 탐색 순서를 관리하여 구현이 가능함.
class GraphDFSExample
{
static Dictionary<char, List<char>> graph = new Dictionary<char, List<char>>
{
{'A', new List<char> {'B', 'C'}},
{'B', new List<char> {'A', 'D', 'E'}},
{'C', new List<char> {'A', 'F'}},
{'D', new List<char> {'B'}},
{'E', new List<char> {'B', 'F'}},
{'F', new List<char> {'C', 'E'}}
};
static Dictionary<char, bool> visited = new Dictionary<char, bool>();
static void DFS(char node)
{
if (!visited.ContainsKey(node))
{
Console.Write(node + " "); // 노드 방문 처리
visited[node] = true;
foreach (char neighbor in graph[node])
{
DFS(neighbor); // 재귀적으로 인접한 노드를 탐색
}
}
}
static void Main(string[] args)
{
DFS('A'); // 시작 노드 'A'에서 DFS 실행
}
}
//Output: 'A' -> 'B' -> 'D' -> 'E' -> 'F' -> 'C'
넓이 우선 탐색(BFS)
- 시작 노드에서부터 인접한 노드를 먼저 모두 탐색한 후, 그 다음 레벨의 인접한 노드를 탐색하는 방법.(깊이가 낮은 노드들 부터 차례로 모두 방문하는 알고리즘)
- 큐 자료구조를 사용하여 구현 가능. 선입선출 원칙에 따라 인접한 노드들을 탐색.
class GraphBFSExample
{
static Dictionary<char, List<char>> graph = new Dictionary<char, List<char>>
{
{'A', new List<char> {'B', 'C'}},
{'B', new List<char> {'A', 'D', 'E'}},
{'C', new List<char> {'A', 'F'}},
{'D', new List<char> {'B'}},
{'E', new List<char> {'B', 'F'}},
{'F', new List<char> {'C', 'E'}}
};
static void BFS(char startNode)
{
Queue<char> queue = new Queue<char>();
Dictionary<char, bool> visited = new Dictionary<char, bool>();
queue.Enqueue(startNode);
visited[startNode] = true;
while (queue.Count > 0)
{
char node = queue.Dequeue();
Console.Write(node + " ");
foreach (char neighbor in graph[node])
{
if (!visited.ContainsKey(neighbor))
{
queue.Enqueue(neighbor);
visited[neighbor] = true;
}
}
}
}
static void Main(string[] args)
{
BFS('A'); // 시작 노드 'A'에서 BFS 실행
}
}
//Output: 'A' -> 'B' -> 'C' -> 'D' -> 'E' -> 'F'
다익스트라 알고리즘(Dijkstra Algorithm)
- 하나의 시작 노드에서 다른 모드 노드까지의 최단 경로를 구하는 데 사용되는 알고리즘. 음이 아닌 가중치를 가진 그래프에서 동작. 시작 노드에서부터 거리가 가장 짧은 노드부터 탐색해 나감.
- 시작 노드의 거리를 0으로 설정하고, 나머지 노드들의 거리를 무한대로 초기화.
- 아직 처리하지 않은 노드들 중에서 가장 거리가 짧은 노드를 선택.
- 선택한 노드의 인접한 노드들을 탐색하여 거리를 업데이트. 만약 더 짧은 경로를 찾으면 해당 거리로 업데이트.
- 모든 노드를 처리할 때까지 위 단계 반복.
using System;
class DijkstraExample
{
static int V = 6; // 정점의 수
// 주어진 그래프의 최단 경로를 찾는 다익스트라 알고리즘
static void Dijkstra(int[,] graph, int start)
{
int[] distance = new int[V]; // 시작 정점으로부터의 거리 배열
bool[] visited = new bool[V]; // 방문 여부 배열
// 거리 배열 초기화
for (int i = 0; i < V; i++)
{
distance[i] = int.MaxValue;
}
distance[start] = 0; // 시작 정점의 거리는 0
// 모든 정점을 방문할 때까지 반복
for (int count = 0; count < V - 1; count++)
{
// 현재 방문하지 않은 정점들 중에서 최소 거리를 가진 정점을 찾음
int minDistance = int.MaxValue;
int minIndex = -1;
for (int v = 0; v < V; v++)
{
if (!visited[v] && distance[v] <= minDistance)
{
minDistance = distance[v];
minIndex = v;
}
}
// 최소 거리를 가진 정점을 방문 처리
visited[minIndex] = true;
// 최소 거리를 가진 정점과 인접한 정점들의 거리 업데이트
for (int v = 0; v < V; v++)
{
if (!visited[v] && graph[minIndex, v] != 0 && distance[minIndex] != int.MaxValue && distance[minIndex] + graph[minIndex, v] < distance[v])
{
distance[v] = distance[minIndex] + graph[minIndex, v];
}
}
}
// 최단 경로 출력
Console.WriteLine("정점\t거리");
for (int i = 0; i < V; i++)
{
Console.WriteLine($"{i}\t{distance[i]}");
}
}
static void Main(string[] args)
{
int[,] graph = {
{ 0, 4, 0, 0, 0, 0 },
{ 4, 0, 8, 0, 0, 0 },
{ 0, 8, 0, 7, 0, 4 },
{ 0, 0, 7, 0, 9, 14 },
{ 0, 0, 0, 9, 0, 10 },
{ 0, 0, 4, 14, 10, 0 }
};
int start = 0; // 시작 정점
Dijkstra(graph, start);
}
}
/* Output:
정점 거리
0 0
1 4
2 12
3 19
4 21
5 11
*/
