탐색 알고리즘

목차

1. 개요
2. 선형 구조 탐색 알고리즘
2.1. 순차 탐색(Sequential Search)
2.1.1. 의사 코드
2.1.2. 분석
2.1.3. 보초법을 이용한 최적화
2.2. 이진 탐색(Binary Search)
2.2.1. 의사 코드(재귀형)
2.2.2. 분석
2.3. 보간 탐색(Interpolation Search)
2.3.1. 위치 계산 공식
2.3.2. 분석
3. 비선형 구조 탐색 알고리즘
3.1. 이진 탐색 트리(Binary Search Tree)
3.1.1. 탐색 의사 코드
3.1.2. 분석
3.2. 너비 우선 탐색(BFS)
3.2.1. 의사 코드
3.2.2. 분석
3.3. 깊이 우선 탐색(DFS)
3.3.1. 의사 코드
3.3.2. 분석
4. 최단 경로 탐색 알고리즘
4.1. 다익스트라(Dijkstra) 알고리즘
4.1.1. 의사 코드
4.1.2. 분석
4.2. A* 알고리즘
4.2.1. 수식
4.3. 벨만-포드(Bellman-Ford) 알고리즘
4.3.1. 의사 코드
4.3.2. 분석
4.4. 플로이드-워셜(Floyd-Warshall) 알고리즘
4.4.1. 의사 코드
4.4.2. 분석
4.5. 보이어-무어(Boyer-Moore) 알고리즘
4.5.1. 분석
5. 문자열 탐색(String Matching)
5.1. KMP(Knuth-Morris-Pratt) 알고리즘
5.1.1. 실패 함수(pi) 의사 코드
5.1.2. 탐색 의사 코드

1. 개요 _{✎ ⊖}

탐색은 특정 데이터 집합에서 원하는 조건에 맞는 원소를 찾아내는 행위이다. 단순히 존재 여부를 파악하는 것부터, 해당 원소의 위치를 반환하거나, 그래프 구조에서 특정 목적지까지 가는 최적의 경로를 찾아내는 것까지 광범위한 영역을 포괄한다. 데이터가 저장된 방식과 정렬 상태에 따라 효율성이 극단적으로 차이 나기 때문에, 적절한 알고리즘 선택이 시스템의 성능을 결정짓는 핵심 요소가 된다.

2. 선형 구조 탐색 알고리즘 _{✎ ⊖}

가장 직관적인 탐색 방식으로, 데이터가 일렬로 나열된 선형 자료구조(배열, 연결 리스트 등)에서 사용된다.

2.1. 순차 탐색(Sequential Search) _{✎ ⊖}

선형 탐색(Linear Search)이라고도 불린다. 데이터의 처음부터 끝까지 하나씩 비교하며 원하는 값을 찾는 가장 기초적인 방식이다.

2.1.1. 의사 코드 _{✎ ⊖}

linearSearch(A[], n, x):
	for i ← 0 to n-1
		if (A[i] == x)
			return i
	return -1

2.1.2. 분석 _{✎ ⊖}

데이터의 정렬 여부와 무관하게 사용 가능하다.

최선의 경우: 첫 번째 원소가 찾는 값인 경우 \Theta(1)

최악의 경우: 찾는 값이 없거나 마지막에 있는 경우 \Theta(n)

평균적인 경우: 데이터가 무작위로 분포할 때 \Theta(n)

2.1.3. 보초법을 이용한 최적화 _{✎ ⊖}

반복문마다 인덱스 범위(i < n)를 체크하는 비용을 줄이기 위해, 배열의 끝에 찾는 값 x를 인위적으로 삽입하여 범위를 체크하는 조건문을 제거하는 기법이다.

2.2. 이진 탐색(Binary Search) _{✎ ⊖}

배열이 이미 정렬되어 있다는 전제하에 사용할 수 있는 강력한 알고리즘이다. 중앙값을 선택해 찾고자 하는 값과 비교한 뒤, 탐색 범위를 매번 절반으로 줄여나가는 분할 정복 방식을 취한다.

2.2.1. 의사 코드(재귀형) _{✎ ⊖}

binarySearch(A[], low, high, x):
	if (low > high)
		return -1
	mid ← ⌊(low + high) / 2⌋
	if (A[mid] == x)
		return mid
	else if (A[mid] > x)
		return binarySearch(A, low, mid - 1, x)
	else
		return binarySearch(A, mid + 1, high, x)

2.2.2. 분석 _{✎ ⊖}

매 비교마다 탐색해야 할 데이터의 양이 절반으로 줄어든다. 점화식은 T(n) = T(n/2) + \Theta(1)이며, 마스터 정리에 의해 수행 시간은 모든 경우에 \Theta(\log n)이다. 데이터가 많아질수록 순차 탐색보다 압도적으로 유리하다.

2.3. 보간 탐색(Interpolation Search) _{✎ ⊖}

이진 탐색의 한계를 보완한 알고리즘이다. 정렬된 데이터가 선형적으로 고르게 분포되어 있다고 가정하고, 전화번호부에서 이름을 찾듯 예상 위치를 수식으로 계산하여 탐색한다.

2.3.1. 위치 계산 공식 _{✎ ⊖}

pos = low + \frac{x - A[low]}{A[high] - A[low]} \times (high - low)

2.3.2. 분석 _{✎ ⊖}

데이터가 고르게 분포되어 있다면 \Theta(\log(\log n))이라는 놀라운 속도를 보여주지만, 데이터 분포가 불균형할 경우 최악의 경우 \Theta(n)까지 떨어진다.

3. 비선형 구조 탐색 알고리즘 _{✎ ⊖}

데이터 간의 관계가 계층적이거나 망(Network) 형태일 때 사용하는 알고리즘이다.

3.1. 이진 탐색 트리(Binary Search Tree) _{✎ ⊖}

각 노드가 최대 두 개의 자식을 가지며, 왼쪽 자식은 부모보다 작고 오른쪽 자식은 부모보다 큰 규칙을 유지하는 트리이다.

3.1.1. 탐색 의사 코드 _{✎ ⊖}

treeSearch(x, k):
	if (x == NULL or k == x.key)
		return x
	if (k < x.key)
		return treeSearch(x.left, k)
	else
		return treeSearch(x.right, k)

3.1.2. 분석 _{✎ ⊖}

트리의 높이를 h라 할 때 시간 복잡도는 O(h)이다. 균형이 잘 잡힌 경우 \Theta(\log n)이지만, 한쪽으로 치우친 사선 트리(Skewed Tree)가 되면 \Theta(n)이 되어 선형 탐색과 다를 바 없어진다. 이를 방지하기 위해 AVL 트리나 레드-블랙 트리와 같은 자가 균형 이진 탐색 트리를 사용한다.

3.2. 너비 우선 탐색(BFS) _{✎ ⊖}

시작 노드에서 인접한 노드를 먼저 모두 방문한 뒤, 다음 깊이로 넘어가는 방식이다. 최단 경로를 보장하는 성질이 있다. 큐(Queue) 자료구조를 필수적으로 사용한다.

3.2.1. 의사 코드 _{✎ ⊖}

BFS(G, s):
	for each vertex v ∈ G.V - {s}
		v.visited ← FALSE
		v.dist ← ∞
	s.visited ← TRUE
	s.dist ← 0
	enqueue(Q, s)
	while (Q is not empty)
		u ← dequeue(Q)
		for each v ∈ G.Adj[u]
			if (v.visited == FALSE)
				v.visited ← TRUE
					v.dist ← u.dist + 1
					enqueue(Q, v)

3.2.2. 분석 _{✎ ⊖}

모든 정점 V와 간선 E를 한 번씩 확인하므로 \Theta(V + E)이다. 가중치가 없는 그래프에서 시작점으로부터의 최단 거리를 구하는 데 최적이다.

3.3. 깊이 우선 탐색(DFS) _{✎ ⊖}

한 방향으로 갈 수 있는 데까지 깊이 들어갔다가, 더 이상 갈 곳이 없으면 되돌아오는 방식이다. 스택(Stack)이나 재귀 호출을 사용하여 구현하며, 모든 노드를 방문하고자 할 때 유용하다.

3.3.1. 의사 코드 _{✎ ⊖}

DFS(u):
	u.visited ← TRUE
	for each v ∈ G.Adj[u]
		if (v.visited == FALSE)
			DFS(v)

3.3.2. 분석 _{✎ ⊖}

BFS와 동일하게 \Theta(V + E)의 시간이 소요된다. 그래프의 사이클 존재 여부 판단, 위상 정렬, 단절점 찾기 등에 활용된다.

4. 최단 경로 탐색 알고리즘 _{✎ ⊖}

단순히 노드를 찾는 것을 넘어, 간선에 가중치(비용)가 있는 경우 최소 비용 경로를 찾는 특수 탐색이다.

4.1. 다익스트라(Dijkstra) 알고리즘 _{✎ ⊖}

음의 가중치가 없는 그래프에서 특정 시작 노드로부터 다른 모든 노드까지의 최단 경로를 구한다. 그리디(Greedy) 알고리즘의 일종이다.

4.1.1. 의사 코드 _{✎ ⊖}

dijkstra(G, s):
	for each v ∈ G.V
		d[v] ← ∞
	d[s] ← 0
		PQ.push(s, d[s])
		while (PQ is not empty)
			u ← PQ.pop_min()
			for each v ∈ G.Adj[u]
				if (d[v] > d[u] + w(u, v))
					d[v] ← d[u] + w(u, v)
					PQ.update_priority(v, d[v])

4.1.2. 분석 _{✎ ⊖}

우선순위 큐(Heap)를 사용할 경우 O(E \log V)의 복잡도를 가진다. 내비게이션 경로 탐색의 가장 고전적이고 핵심적인 알고리즘이다.

4.2. A* 알고리즘 _{✎ ⊖}

다익스트라 알고리즘에 휴리스틱(Heuristic, 추정치)을 결합한 알고리즘이다. 목표점까지의 예상 거리를 고려하여 탐색 방향을 설정하므로 다익스트라보다 훨씬 빠르다.

4.2.1. 수식 _{✎ ⊖}

f(n) = g(n) + h(n)

g(n): 출발지에서 현재 노드까지의 실제 비용

h(n): 현재 노드에서 목표지까지의 예상 비용(휴리스틱)

4.3. 벨만-포드(Bellman-Ford) 알고리즘 _{✎ ⊖}

다익스트라와 달리 음의 가중치가 있는 그래프에서도 최단 경로를 찾을 수 있다. 정점의 개수가 V일 때, 모든 간선을 V-1번 완화(Relaxation)하는 방식이다.

4.3.1. 의사 코드 _{✎ ⊖}

bellmanFord(G, s):
	for each v ∈ G.V
		d[v] ← ∞
	d[s] ← 0
	for i ← 1 to |V|-1
		for each edge (u, v) ∈ G.E
			if (d[v] > d[u] + w(u, v))
				d[v] ← d[u] + w(u, v)
	
	for each edge (u, v) ∈ G.E
		if (d[v] > d[u] + w(u, v))
			return "음의 사이클 존재"
	return d

4.3.2. 분석 _{✎ ⊖}

시간 복잡도는 \Theta(VE)이다. 매 단계 모든 간선을 확인하므로 다익스트라보다 느리지만, 음의 사이클을 찾아낼 수 있다는 강력한 장점이 있다.

4.4. 플로이드-워셜(Floyd-Warshall) 알고리즘 _{✎ ⊖}

모든 정점 쌍(All-pairs) 사이의 최단 경로를 한 번에 구하는 알고리즘이다. 동적 계획법 원리를 이용한다.

4.4.1. 의사 코드 _{✎ ⊖}

floydWarshall(W[][]):
	d[][] ← W
	for k ← 0 to n-1
		for i ← 0 to n-1
			for j ← 0 to n-1
				d[i][j] ← min(d[i][j], d[i][k] + d[k][j])
	return d

4.4.2. 분석 _{✎ ⊖}

3중 for 루프를 사용하므로 시간 복잡도는 \Theta(n^3)이다. 구현이 매우 간단하며, 정점의 개수가 적을 때 모든 경로를 구하기에 최적이다.

4.5. 보이어-무어(Boyer-Moore) 알고리즘 _{✎ ⊖}

패턴의 오른쪽 끝부터 거꾸로 비교하는 독특한 방식이다. 일치하지 않는 문자가 패턴에 없다면 패턴의 길이만큼 통째로 건너뛸 수 있어 실제 응용에서 가장 빠른 성능을 보여준다.

4.5.1. 분석 _{✎ ⊖}

평균적으로 O(n/m) 수준의 성능을 보여주며, 대부분의 텍스트 에디터에서 찾기(Ctrl+F) 기능의 표준으로 사용된다.

5. 문자열 탐색(String Matching) _{✎ ⊖}

텍스트 내에서 특정 패턴 문자열을 찾는 탐색이다.

5.1. KMP(Knuth-Morris-Pratt) 알고리즘 _{✎ ⊖}

패턴 내의 중복되는 부분(접두사와 접미사)을 미리 분석하여, 불일치가 발생했을 때 처음부터 다시 비교하지 않고 건너뛰는 방식이다.

5.1.1. 실패 함수(pi) 의사 코드 _{✎ ⊖}

getPi(P[]):
	m ← length(P)
	pi[] ← 0
	j ← 0
	for i ← 1 to m-1
		while (j > 0 and P[i] != P[j])
			j ← pi[j-1]
		if (P[i] == P[j])
			pi[i] ← ++j
	return pi

5.1.2. 탐색 의사 코드 _{✎ ⊖}

KMP(T[], P[]):
	n ← length(T); m ← length(P)
	pi ← getPi(P)
	j ← 0
	for i ← 0 to n-1
		while (j > 0 and T[i] != P[j])
			j ← pi[j-1]
		if (T[i] == P[j])
			if (j == m-1)
				return i - m + 1
			else
				j++
	return -1

탐색 알고리즘

1. 개요 ✎ ⊖

2. 선형 구조 탐색 알고리즘 ✎ ⊖

2.1. 순차 탐색(Sequential Search) ✎ ⊖

2.1.1. 의사 코드 ✎ ⊖

2.1.2. 분석 ✎ ⊖

2.1.3. 보초법을 이용한 최적화 ✎ ⊖

2.2. 이진 탐색(Binary Search) ✎ ⊖

2.2.1. 의사 코드(재귀형) ✎ ⊖

2.2.2. 분석 ✎ ⊖

2.3. 보간 탐색(Interpolation Search) ✎ ⊖

2.3.1. 위치 계산 공식 ✎ ⊖

2.3.2. 분석 ✎ ⊖

3. 비선형 구조 탐색 알고리즘 ✎ ⊖

3.1. 이진 탐색 트리(Binary Search Tree) ✎ ⊖

3.1.1. 탐색 의사 코드 ✎ ⊖

3.1.2. 분석 ✎ ⊖

3.2. 너비 우선 탐색(BFS) ✎ ⊖

3.2.1. 의사 코드 ✎ ⊖

3.2.2. 분석 ✎ ⊖

3.3. 깊이 우선 탐색(DFS) ✎ ⊖

3.3.1. 의사 코드 ✎ ⊖

3.3.2. 분석 ✎ ⊖

4. 최단 경로 탐색 알고리즘 ✎ ⊖

4.1. 다익스트라(Dijkstra) 알고리즘 ✎ ⊖

4.1.1. 의사 코드 ✎ ⊖

4.1.2. 분석 ✎ ⊖

4.2. A* 알고리즘 ✎ ⊖

4.2.1. 수식 ✎ ⊖

4.3. 벨만-포드(Bellman-Ford) 알고리즘 ✎ ⊖

4.3.1. 의사 코드 ✎ ⊖

4.3.2. 분석 ✎ ⊖

4.4. 플로이드-워셜(Floyd-Warshall) 알고리즘 ✎ ⊖

4.4.1. 의사 코드 ✎ ⊖

4.4.2. 분석 ✎ ⊖

4.5. 보이어-무어(Boyer-Moore) 알고리즘 ✎ ⊖

4.5.1. 분석 ✎ ⊖

5. 문자열 탐색(String Matching) ✎ ⊖

5.1. KMP(Knuth-Morris-Pratt) 알고리즘 ✎ ⊖

5.1.1. 실패 함수(pi) 의사 코드 ✎ ⊖

5.1.2. 탐색 의사 코드 ✎ ⊖