[자료구조/알고리즘] 완전 탐색 / 이진 탐색 알고리즘

[완전 탐색 알고리즘]

Brute-Force : 시행착오 방법론으로 모든 값을 대입하는 방법

완전 탐색 알고리즘(Brute-Froce Algorithm) : 무차별 대입 방법으로, 모든 가능성을 시도하여 문제를 해결하는 방법

* 공간/시간 복잡도를 고려하지 않기 때문에 Greey Algorithm이 아님

 

[사용 경우] (문제의 더 적절한 해결법을 찾기 전 사용함)

1) 프로세스 속도를 높이는데 사용할 수 있는 다른 알고리즘이 없는 경우

2) 문제를 해겨하는 여러 솔루션이 있고 각 솔루션을 확인해야 할 경우

 

[사용 예시]

1) 순차 검색 알고리즘(Sequential Search)

Ex. 배열 내 특정값 존재 여부 확인(처음부터 차례대로 검색)

 

2) 문열 매칭 알고리즘(Brute-Force Matching)

Ex. 길이가 n인 문자열과 길이가 m인 문자열 패턴을 포함하는지 검색

 

3) 선택 정렬 알고리즘(Selection Sort)

Ex. 전체 배열을 검색하여 현재 요소와 비교하고 컬렉션이 완전히 정렬될 때까지 값을 고려하는 정렬 알고리즘

 

4) 기타

 - 버블 정렬 알고리즘(Bubble Sort)

 - Tree 자료구조의 완전 탐색 알고리즘(BFS, DFS)

 - 동적 프로그래밍(Dynamic Programming; DP)

 

[이진 탐색 알고리즘]

이진 탐색 알고리즘(Binary Search Algorithm)

: 데이터가 정렬된 상태에서 절반씩 범위를 나눠 분할 정복기법으로 특정한 값을 찾아내는 알고리즘

 

[동작 단계]

1. 정렬된 배열의 가장 중간 인덱스를 지정

2. 찾으려는 값이 지정한 인덱스의 값과 동일할 경우 종료, 아니라면 중간 값보다 큰지, 작은지 확인

3. 값이 있는 부분과 없는 부분을 분리 (탐색 범위가 절반으로 줄어듦)

4. 값이 있는 부분에서 다시 1단계부터 반복 진행

 

[사용 경우]

1) 정렬된 배열에서 요소를 더 효율적으로 검색할 경우

2) 데이터 양이 많을수록 효율이 높아 정렬된 데이터 양이 많을 경우

 * 시간 복잡도 O(log n)  >> 동작단계 3번에 의해 탐색 범위가 절반으로 줄어들기 때문

 * 데이터 양이 적고 데이터가 앞에 위치할 경우  Linear Search Algorithm이 더 빠를 수 있음

 

[한계]

1) 배열에서만 구현 가능

2) 정렬이 되어 있어야만 구현 가능(규모가 작을 경우 정렬 후 사용하더라도 효율이 높지 않을 수 있음)

 

[사용예시]

 - 사전 검색

 - 도서관 도서 검색

 - 대규모 시스템에 대한 리소스 상황 파악

 - 반도체 테스트 프로그램 >> 디지털/아날로그 레벨 측정에 사용