1. 선형구조 탐색

선형 구조를 탐색하는데 쓰이는 알고리즘이다.

1. 선형 탐색(Linear Search)

선형 탐색(linear search) 또흔 순차 탐색(Sequential Search)이라고도 한다.
이 방식은 탐색에서 가장 확실하면서도 가장 느린 방식이다.

<선형 탐색>
자료구조에서 순차적으로 찾고자 하는 데이터를 탐색
시간복잡도 - $O(n)$

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. 이진 탐색(Binary Search)

<이진 탐색>
정렬이 되어있는 자료구조에서 2분할을 통해 데이터를 탐색한다. 단, 이진 탐색은 정렬이 되어 있는 자료에만 적용 가능하다
시간복잡도 - $O(logn)$

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;
	}

이진 탐색은 오름차순이던 내림차순이던 정렬이 되어있어야 사용이 가능하다. 이진 탐색은 선형 탐색과 비교하였을 때 크면 클 수록 효율적이다. 하나씩 차례로 찾는 것과 비교하였을 때 이진 탐색은 중간을 찍고 찾는 값이 중간 값보다 큰지 작은지 판단 후 이동을 반복하기에 연산 1회 당 탐색할 숫자가 절반으로 줄어들기 때문이다.

2. 구조/조건 기반 그래프 탐색 알고리즘

가중치와 무관하게 구조와 조건, (백트래킹 / 순열 / 경로 찾기 - DFS), (레벨 탐색 / 거리 기반 그룹 - BFS)을 탐색한다

1. DFS(깊이 우선 탐색, Depth-First Search)

그래프의 분기를 만났을 때 최대한 깊이 내려간 뒤, 분기의 탐색을 마쳤을 때 다음 분기를 탐색한다. DFS는 스택, 재귀를 통해 구현한다.

• 메서드 또한 스택 형식의 순서로 작동되기 때문에 메서드로도 구현 가능(재귀 함수)

장점: 탐색 단계에 필요한 메모리만큼만 사용, 함수 호출 스택을 사용해서 비교적 빠르다 => 현재 탐색 상황에서 필요한 정점 데이터만 보관 가능하고 탐색이 끝나면 버려도 무관하다.
단점: 최단 경로 보장 $X$

일반적으로 트리에 사용 선호한다. (트리에서는 어차피 경로가 하나밖에 없어서 최단 경로를 보장하지 못한다는 단점을 보완할 수 있다.)

        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);
			}
		}
	}

2. BFS(너비 우선 탐색, Breadth-First Search)

그래프의 분기를 만났을 때 모든 분기들을 탐색한 뒤,
다음 깊이의 분기들을 탐색
큐를 통해 탐색

장점: 최단 경로 보장
단점: 다른 정점에 대한 정보를 대기열에 소유하고 있어야 하기 때문에 불필요한 데이터를 보관하고 있어야 한다. => 현재 탐색 상황에서 필요하지 않은 정점 데이터도 큐에 보관할 필요가 있다.

일반적으로 그래프에 사용 선호(DFS와 반대 상황)

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]) //방문한 적(이미 찾은 적) 없는 정점 = (parents[vertex] != -1)이랑 같은 뜻 
				{
					visited[i] = true; // 수업 의사 코드 주석에 넣기
					parents[i] = next; //
					queue.Enqueue(i); //
				}
			}
		}
	}

해당 노드가 누구에 의해 찾아졌는지(Parent - Child), 연결이 되었는지(Visited) 이 두가지 결과값을 무방향 그래프에서 얻을 수 있다.

최단 거리를 찾기 위해서는 부모와 자식의 연결을 역순으로 따라가면 알 수 있다.

그러나 DFS, BFS의 탐색에서 어떤 것이 더 빠르다는 보장은 없다.

3. 최단 경로 기반 탐색

1. 다익스트라 알고리즘

다익스트라 알고리즘은 특정한 노드에서 출발하여 다른 노드까지 가는 각각의 최단 경로를 구하는 알고리즘이다. 또한 다익스트라 알고리즘은 양수 가중치일 때 사용을 한다.

가중치가 있을 때는 직접적인 거리가 가중치 때문에 더 멀 수도 있기 때문에 아래와 같은 개념을 활용한다.
ex) 0 - 2 보다 0 - 1 - 2 가 더 빠를 수도 있음

다익스트라 알고리즘 컨셉은

1. 가장 가까운 정점(대체된 것도 포함해서 비교)부터 탐색

2. 그 정점을 통해 갈 수 있는 다른 정점들의 거리를 업데이트
   $\overrightarrow{AC}$ $>$ $\overrightarrow{AB}$ $+$ $\overrightarrow{BC}$ 일 때 $\overrightarrow{AC}$ $=$ $\overrightarrow{AB}$ $+$ $\overrightarrow{BC}$ 로 교체하는 것이다.

3. 모든 노드를 방문할 때까지 반복

const int INF = 99999;

	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;
				}
			}
		}
	}