[TBC] Search Algorithm

추가할 것: Hash search / Trie / Heaptree

 

선형 탐색

Linear Search Algorithm - O(n)

배열의 0번째 인덱스부터, 찾으려는 값과 인덱스의 값을 하나씩 비교 (처음부터 끝까지 하나씩 확인)

값을 찾으면 해당 인덱스를 반환하고, 찾는 값이 없으면 -1을 반환

선형 탐색은 배열의 정렬 여부와 관계없이 시행할 수 있고 다른 탐색 알고리즘에 비해 정말 단순하고 간단한 구조이지만, 배열의 모든 요소를 하나씩 찾기 때문에 시간이 오래 걸려서 그다지 효율적인 편은 아니다.

https://www.geeksforgeeks.org/linear-search/?ref=lbp

---

이진 탐색

Binary Search Algorithm - O(log n)

데이터가 정렬된 상태에서 절반씩 범위를 줄여가며 특정 값을 찾는다

숫자 Up&Down 게임을 생각하면 쉽다. 

탐색을 할 때마다 탐색 범위를 1/2로 줄여나가기 때문에 정렬된 데이터의 양이 많을 때 높은 효율을 보인다. 

다만, 아래의 조건이 반드시 반영되어야 한다. 

1. 배열에만 구현 가능

2. 미리 정렬된 데이터를 사용해야 함 

 

https://www.geeksforgeeks.org/binary-search/

---

사용 예시:

사전 검색

도서관 도서 검색 시스템

대규모 시스템에 대한 리소스 상태 파악
시스템 부하 테스트에서 예측된 부하를 처리하는데 필요한 CPU양에 대해 파악할 때 사용

---

해시 탐색 - TBC

Hash Search Algorithm

 해시 탐색 알고리즘을 사용하기 위해서는 먼저 데이터를 저장하는 알고리즘과, 데이터를 탐색하는 알고리즘, 2개의 알고리즘을 구현해야 한다. 해시 함수를 이용해서 input값을 분류 및 저장을 하고, 탐색을 할 때에는 각 요소의 해시 value를 통해 찾는다. 

TBC

---

BFS / DFS 

그래프나 트리를 탐색하는 방법 

https://www.hackerearth.com/blog/wp-content/uploads/2015/05/dfsbfs_animation_final.gif

BFS

Breadth First Search(너비 우선 탐색)은 모든 분기점을 전부 검사하면서 진행하는 방식이다.  깊게 가기 전에 넓게 훑고 가는 느낌이다. 두 노드 사이의 최단 경로 또는 임의의 경로를 찾고 싶은 경우에 사용한다. 

BFS의 특징

• 보통 Queue를 사용한다.
• 반드시 어떤 노드를 방문했었는지 여부를 검사해야 한다. (예: boolean 배열 )
• 가중치가 없는 그래프에서 시작과 끝 정점 사이의 최단경로를 구할 수 있다. 

https://gmlwjd9405.github.io/2018/08/15/algorithm-bfs.html

---

DFS

Depth First Search(깊이 우선 탐색)은 하나의 경로를 끝까지 탐색 후, 찾는 값이 없으면 다음 경로로 넘어간다. 모든 노드를 확인해야 하는 경우에 사용한다. 

BFS보다 구현이 간단하지만 탐색 속도 측면에서는 느리다.

DFS의 특징

• 보통 재귀를 사용해 구현한다. 스택 배열을 쓸 수도 있지만 스택 오버 플로우를 주의해야 함. 
• 반드시 어떤 노드를 방문했었는지 여부를 검사해야 한다. (예: boolean 배열 )
• 경로의 끝까지 찾기 때문에, 무한한 길이를 갖는 트리나 그래프에서는 사용 X

https://gmlwjd9405.github.io/2018/08/14/algorithm-dfs.html