탐색 알고리즘 ( Search Algorithm )
1) 탐색 알고리즘 이란?
탐색 알고리즘은 주어진 데이터 집합에서 특정 항목을 찾는 방법을 제공
2) 선형 탐색 ( Linear Search )
선형 탐색은 가장 단순한 탐색 알고리즘
배열의 각 요소를 하나씩 차례대로 검사하여 원하는 항목을 찾는다.
시간 복잡도: 최악의 경우 O(n)
간단 예시
using System;
public class LinearSearchExample
{
public static void Main()
{
// 탐색할 배열
int[] arr = { 5, 2, 9, 1, 5, 6 };
// 찾을 값
int target = 9;
// 선형 탐색 호출
int index = LinearSearch(arr, target);
// 결과 출력
if (index != -1)
Console.WriteLine($"{target}은(는) 배열의 인덱스 {index}에 위치합니다.");
else
Console.WriteLine($"{target}을(를) 찾을 수 없습니다.");
}
public static int LinearSearch(int[] arr, int target)
{
// 배열을 처음부터 끝까지 순차적으로 탐색
for (int i = 0; i < arr.Length; i++)
{
// 현재 요소가 찾는 값과 같으면 인덱스 반환
if (arr[i] == target)
return i;
}
// 찾는 값이 없으면 -1 반환
return -1;
}
}
// 탐색할 배열: {5, 2, 9, 1, 5, 6}
// 찾을 값: 9
// 선형 탐색 알고리즘:
LinearSearch 메서드가 배열을 처음부터 끝까지 순차적으로 탐색
현재 요소가 찾는 값과 같으면 해당 인덱스를 반환
배열 끝까지 찾는 값이 없으면 -1을 반환
// 탐색 결과 출력:
9을 찾으면 "9은(는) 배열의 인덱스 2에 위치합니다."와 같이 출력
찾는 값이 없으면 "9을(를) 찾을 수 없습니다."와 같이 출력.
// 선형 탐색은 간단하지만 배열이나 리스트의 크기가 큰 경우에는 효율이 떨어질 수 있다.
// 이 알고리즘은 배열이 정렬되어 있지 않아도 동작 한다. 하지만 처음부터 끝까지 모든 요소를 확인하기 때문에 최악의 경우 시간 복잡도는 O(n)
3) 이진 탐색 ( Binary Search )
이진 탐색은 정렬된 배열에서 빠르게 원하는 항목을 찾는 방법
중간 요소와 찾고자 하는 항목을 비교하여 대상이 중간 요소보다 작으면 왼쪽을, 크면 오른쪽을 탐색
시간 복잡도: 최악의 경우 O(log n)
간단 예시
using System;
public class BinarySearchExample
{
public static void Main()
{
// 정렬된 배열
int[] arr = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
// 찾을 값
int target = 5;
// 이진 탐색 호출
int index = BinarySearch(arr, target);
// 결과 출력
if (index != -1)
Console.WriteLine($"{target}은(는) 배열의 인덱스 {index}에 위치합니다.");
else
Console.WriteLine($"{target}을(를) 찾을 수 없습니다.");
}
public static 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;
}
// 찾는 값이 없으면 -1 반환
return -1;
}
}
// 정렬된 배열: {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
// 찾을 값: 5
// 이진 탐색 알고리즘:
BinarySearch 메서드가 배열의 왼쪽과 오른쪽을 계속해서 좁혀가며 중앙값을 기준으로 찾고자 하는 값을 확인
중앙값이 찾는 값과 일치하면 해당 인덱스를 반환
중앙값이 찾는 값보다 작으면 오른쪽을 탐색하고, 크면 왼쪽을 탐색
// 탐색 결과 출력:
5를 찾으면 "5은(는) 배열의 인덱스 4에 위치합니다."와 같이 출력
찾는 값이 없으면 "5을(를) 찾을 수 없습니다."와 같이 출력
// 탐색은 정렬된 배열에서 특히 효과적으로 동작하며, 최악의 경우 시간 복잡도는 O(log n)
중간 요소와 찾고자 하는 항목을 비교하여 대상이 중간 요소보다 작으면 왼쪽을, 크면 오른쪽을 탐색
이 문장은 바이너리 서치를 설명하는 전통적인 방식과 일치
대상 값이 중간 요소보다 작으면 왼쪽에서 계속 탐색하고, 크면 오른쪽에서 탐색을 계속
중앙값이 찾는 값보다 작으면 오른쪽을 탐색하고, 크면 왼쪽을 탐색
이 문장은 동일한 개념을 다른 말로 표현한 것
중간 요소가 대상 값보다 작으면 오른쪽에서 탐색하고, 크면 왼쪽에서 탐색
// 두 문장은 바이너리 서치의 논리적인 과정을 전달
비교를 통해 타겟 값을 중간 요소와 비교하고 이에 따라 탐색 범위를 조정, 이것이 포인트
두 문장이 동일한 개념을 전달하고 있다는 것
그래프 ( Graph )
1) 그래프 개념과 종류
정점(Vertex)과 간선(Edge)으로 이루어진 자료 구조
방향 그래프(Directed Graph)와 무방향 그래프(Undirected Graph)로 나뉨
가중치 그래프(Weighted Graph)는 간선에 가중치가 있음
2) 그래프 탐색 방법
깊이 우선 탐색 (Depth-First Search, DFS) :
DFS는 트리나 그래프를 탐색하는 알고리즘 중 하나
루트에서 시작하여 가능한 한 깊이 들어가서 노드를 탐색하고,
더 이상 방문할 노드가 없으면 이전 노드로 돌아가는 방식
시간 복잡도: 최악의 경우 O(V+E) (V는 노드 수, E는 간선 수)
너비 우선 탐색 (Breadth-First Search, BFS) :
BFS는 트리나 그래프를 탐색하는 알고리즘 중 하나
루트에서 시작하여 가까운 노드부터 방문하고, 그 다음 레벨의 노드를 방문하는 방식
시간 복잡도: 최악의 경우 O(V+E) (V는 노드 수, E는 간선 수)
간단 예시
using System;
using System.Collections.Generic;
public class Graph
{
private int V; // 그래프의 정점 개수
private List<int>[] adj; // 인접 리스트
// 그래프 생성자
public Graph(int v)
{
V = v;
adj = new List<int>[V];
// 각 정점에 대한 인접 리스트 초기화
for (int i = 0; i < V; i++)
{
adj[i] = new List<int>();
}
}
// 정점 v에서 정점 w로 간선 추가
public void AddEdge(int v, int w)
{
adj[v].Add(w);
}
// 깊이 우선 탐색 (Depth First Search)
public void DFS(int v)
{
bool[] visited = new bool[V]; // 방문 여부를 나타내는 배열
DFSUtil(v, visited);
}
// DFS의 실제 구현
private void DFSUtil(int v, bool[] visited)
{
visited[v] = true; // 정점 v를 방문했다고 표시
Console.Write($"{v} "); // 방문한 정점을 출력
// 현재 정점과 연결된 모든 인접 정점에 대해 DFS 호출 (재귀적으로)
foreach (int n in adj[v])
{
if (!visited[n])
{
DFSUtil(n, visited);
}
}
}
// 너비 우선 탐색 (Breadth First Search)
public void BFS(int v)
{
bool[] visited = new bool[V]; // 방문 여부를 나타내는 배열
Queue<int> queue = new Queue<int>(); // 큐를 사용하여 BFS 구현
visited[v] = true; // 정점 v를 방문했다고 표시
queue.Enqueue(v); // 큐에 정점 v를 추가
while (queue.Count > 0)
{
int n = queue.Dequeue(); // 큐에서 정점을 추출하고 출력
Console.Write($"{n} ");
// 현재 정점과 연결된 모든 인접 정점에 대해 BFS 호출
foreach (int m in adj[n])
{
if (!visited[m])
{
visited[m] = true; // 방문했다고 표시
queue.Enqueue(m); // 큐에 추가
}
}
}
}
}
public class Program
{
public static void Main()
{
// 그래프 생성
Graph graph = new Graph(6);
// 간선 추가
graph.AddEdge(0, 1);
graph.AddEdge(0, 2);
graph.AddEdge(1, 3);
graph.AddEdge(2, 3);
graph.AddEdge(2, 4);
graph.AddEdge(3, 4);
graph.AddEdge(3, 5);
graph.AddEdge(4, 5);
// 깊이 우선 탐색 수행 및 출력
Console.WriteLine("DFS traversal:");
graph.DFS(0);
Console.WriteLine();
// 너비 우선 탐색 수행 및 출력
Console.WriteLine("BFS traversal:");
graph.BFS(0);
Console.WriteLine();
}
}
// Graph 클래스는 그래프를 나타내며, 정점의 개수 및 인접 리스트를 초기화하는 생성자와 간선을 추가하는 메서드를 포함
// DFS 메서드는 깊이 우선 탐색을 수행하고, BFS 메서드는 너비 우선 탐색을 수행
// 깊이 우선 탐색과 너비 우선 탐색은 각각 DFSUtil 및 BFS 메서드 내에서 재귀적 또는 큐를 사용하여 구현
// Main 메서드에서는 그래프를 생성하고 간선을 추가한 후, 깊이 우선 탐색과 너비 우선 탐색을 호출하여 결과를 출력
최단 경로 알고리즘 ( Shortest path problem )
1) 최단 경로 알고리즘 개념과 종류
다익스트라 알고리즘(Dijkstra Algorithm) :
하나의 시작 정점에서 다른 모든 정점까지의 최단 경로를 찾는 알고리즘.
음의 가중치를 갖는 간선이 없는 경우에 사용
벨만-포드 알고리즘(Bellman-Ford Algorithm) :
음의 가중치를 갖는 간선이 있는 그래프에서도 사용할 수 있는 최단 경로 알고리즘.
음수 사이클이 있는 경우에도 탐지할 수 있다.
A* 알고리즘 (A-star Algorithm) :
특정 목적지까지의 최단 경로를 찾는 알고리즘
휴리스틱 함수를 사용하여 각 정점까지의 예상 비용을 계산하고, 가장 낮은 예상 비용을 가진 정점을 선택하여 탐색.
간단 예시
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++)
{
// 방문하지 않았고, 최소 거리를 가진 정점과 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);
}
}
// Dijkstra 메서드:
graph: 그래프의 인접 행렬 표현
start: 시작 정점의 인덱스
최단 경로를 찾아 distance 배열에 저장하고 출력
// distance 배열:
distance[i]: 시작 정점으로부터 정점 i까지의 최단 거리를 저장
초기에는 모든 거리를 무한대(int.MaxValue)로 설정
// visited 배열:
visited[i]: 정점 i를 방문했는지 여부를 나타내는 배열
초기에는 모든 정점이 방문되지 않았음을 나타내기 위해 false로 초기화
// 알고리즘 실행:
각 정점에 대해 현재까지 방문하지 않은 정점 중 최단 거리를 가진 정점을 선택하고 방문 처리
선택된 정점과 연결된 정점들의 거리를 업데이트.
모든 정점을 방문할 때까지 이 과정을 반복
// 최단 경로 출력:
최단 경로를 출력하기 위해 distance 배열을 사용
'TIL' 카테고리의 다른 글
11.22 (TIL -코딩 문제) (0) | 2023.11.22 |
---|---|
11.21 (TIL) (0) | 2023.11.21 |
11.17 (TIL) (1) | 2023.11.17 |
11.16 (TIL) (0) | 2023.11.16 |
11.15 (TIL) (0) | 2023.11.15 |