/* 본 게시물은 ' 뇌를 자극하는 알고리즘 | with 박상현 ' 의 내용을 토대로 작성되었습니다. */
참고 자료
[BoostCourse - 모두를 위한 컴퓨터 과학(CS50) - 검색 알고리즘] : https://www.boostcourse.org/cs112
#검색(탐색) 알고리즘
오늘 배울 알고리즘은 고성능 데이터 탐색을 구현하는데 필요한 기초가 될 것이다. 이번에 다룰 알고리즘은 순차 탐색, 이진 탐색이다. 이들을 다 배운다면 우리는 주어진 배열 속에서 특정 값을 찾을 수 있다. 자, 순차 탐색에 대해 먼저 알아보자.
1. 순차 탐색
순차 탐색(선형 검색)은 데이터 집합의 처음부터 끝까지 차례대로 모든 요소를 비교해서 데이터를 찾는 탐색 알고리즘이다. 다시 말해, 선형검색은 원하는 원소가 발견될 때까지 처음부터마지막 자료까지 차례대로 검색한다. (순차 탐색은 한쪽 방향으로만 탐색을 수행한다고해서 선형 검색(탐색)이라고도 부른다.)
선형 검색의 장점
이 선형 검색 알고르짐은 정렬되어 있지 않은 데이터 집합 속에서 원하는 데이터를 찾을 수 있는 유일한 방법인데다 구현 또한 간단해서 버그를 만들 가능성이 적다. 이는 극적으로 높은 성능이 필요하지 않거나 데이터 집합의 크기가 작은 곳에서는 자주 사용된다.
선형 검색의 단점
하지만 선형검색은 효율성 측면에서 떨어진다. 하나의 예시로 배열의 길이가 n이라고 했을 때, 최악의 경우 리스트의 모든 원소를 확인해야 하므로 n번만큼 실행된다. 여기서 최악의 상황은 찾고자 하는 자료가 맨 마지막에 있거나 리스트 안에 없는 경우를 말한다. 따라서, 리스트의 자료가 크면 클수록 효율성은 점차 떨어질 것이다.
cf> 그렇다면 효율성을 높일 수 있는 방법은 없을까?
당연히 있다. 데이터 집합을 정렬시키면 된다. 단, 정렬은 시간이 오래 걸리고 공간을 더 차지한다. 하지만 이 추가적인 과정을 진행하면 여러 번 리스트를 검색해야 할 때 시간을 단축할 수 있을 것이다. (정렬 알고리즘도 다음에 다뤄보겠다.)
다른 방법으로는 자기 구성법이 있다. 자기 구성법은 자주 사용되는 데이터를 데이터 집합의 앞쪽에 배치함으로써 순차 탐색의 검색 효율을 끌어올리는 방법이다. 그렇다면 여기서 '자주 사용되는 데이터는 어떻게 선별할까?' 라고 궁금해 할 수 있다. 데이터를 선별하는 방법은 다음과 같다.
- 전진 이동법 : 어느 데이터가 한번 탐색되고 나면, 그 항목을 데이터 집합의 가장 앞에 위치시키는 방법이다.
- 전위법 : 탐색된 데이터를 탐색된 데이터의 바로 앞 데이터와 교환하는 방법이다.
- 계수법 : 데이터 집합 내의 각 요소들이 탐색된 횟수를 별도의 공간에 저장해 두고, 탐색된 횟수가 높은 순으로 데이터 집합을 재구성하는 방법이다.
선형 검색 예시
fun main() {
val mutableList = mutableListOf<Int>(1, 2, 3, 4, 5, 6)
for (i in 0 until mutableList.size){
if(mutableList[i] == 2){
println("found ${mutableList[i]}, Index of ${mutableList[i]} is $i")
return
}
}
println("not found")
}주어진 리스트에서 특정 값을 찾기 위해 선형 검색을 사용한 예시이다. for 문과 if 문을 이용해 선형검색을 구현했다.
2. 이진 탐색
이진 탐색은 정렬된 데이터 집합에서 사용할 수 있는 '고속' 탐색 알고리즘이다. '이진 탐색'이라는 이름은 이 알고리즘의 핵심이 탐색의 범위를 1/2씩 줄여나가는 방식에 있기 때문에 붙여진 것이다. 이진 탐색을 수행하는 과정은 다음과 같다.
- 데이터 집합의 중앙에 있는 요소를 고른다.
- 중앙 요소의 값과 찾고자 하는 목표 값을 비교한다.
- 목표 값이 중앙 요소의 값보다 작다면 중앙을 기준으로 데이터 집합의 왼편에 대해 새로 검색을 수행하고 크다면 오른편에 대해 이진 탐색을 새로이 수행한다.
- 찾고자 하는 값을 찾을 때까지 1번~3번 과정을 반복한다.
이진 탐색의 예시
object BinarySearch {
fun findValueByBinarySearch(dataSet: Array<Int>, target: Int): Int{
// 배열의 인덱스 범위
var left = 0
var right = dataSet.size - 1
// while 반복 문을 통한 이진 탐색
while(left <= right){
val mid = (left + right) / 2
if (target == dataSet[mid]){
return mid // target 의 index 반환
}
else if (target >= dataSet[mid]){ // target 이 중앙값보다 클 때
left = mid + 1
}
else { // target 이 중앙값 보다 작을때
right = mid - 1
}
}
return -1
}
}
fun main(){
val arr = arrayOf<Int>(1,2,3,4,5,6,7,8,9,10)
val value = BinarySearch.findValueByBinarySearch(arr, 3)
println(value)
}이진 탐색의 과정을 코드로 구현했다. 위 코드에서는 while 문을 통해 탐색을 반복시켜줬지만, 재귀 함수를 통해서도 이진 탐색을 구현할 수 있다.
이진 탐색의 성능
이진 탐색은 처음 탐색을 시도할 때 탐색 대상의 범위가 1/2로 줄어든다. 그리고 그 다음 시행에서는 1/4 그 다음은 1/16로 탐색 범위가 줄어든다. 이런 식으로 탐색 대상의 범위가 계속 줄어들어 '1'이 되면 탐색을 종료한다. 물론 이전에 값을 찾으면 탐색을 중지한다. 여기서 줄어드는 규칙이 보인다. 데이터의 개수를 n, 시행 횟수를 x라 할 때, x = log2(n)이다. 즉, 이진 탐색의 반복 횟수는 최대 log2(n)이다. 따라서 이진 탐색의 Big-O 값은 O(log n)이다. ( log2(n) 의 경우 밑이 10인 log n으로 계산한다)
재귀를 이용한 이진 탐색 vs 반복을 이용한 이진 탐색
object BinarySearch {
// val arr = arrayOf<Int>(1,2,3,4,5,6,7,8,9,10)
val arr = Array<Int>(100000) { i -> i + 1 }
fun binarySearchByWhile(target: Int): Int{
// 배열의 인덱스 범위
var left = 0
var right = arr.size - 1
// while 반복 문을 통한 이진 탐색
while(left <= right){
val mid = (left + right) / 2
if (target == arr[mid]){
return mid // target 의 index 반환
}
else if (target >= arr[mid]){ // target 이 중앙값보다 클 때
left = mid + 1
}
else { // target 이 중앙값 보다 작을때
right = mid - 1
}
}
return -1
}
fun binarySearchByRecursion(target: Int, left:Int = 0, right: Int = arr.size - 1): Int{
if (left == right){
return -1 // 탐색 실패
}
if (left <= right){
val mid = (left + right) / 2
if (target == arr[mid]){
return mid
}
else if (target <= arr[mid]){
return binarySearchByRecursion(target, left, arr[mid] - 1)
}
else if (target >= arr[mid]){
return binarySearchByRecursion(target, arr[mid] + 1, right)
}
}
return -1
}
}
@ExperimentalTime
fun main(){
//while
val measuredTime = measureTimedValue {
BinarySearch.binarySearchByWhile(1)
}
println("IndexOfTarget => ${measuredTime.value} || measured time ==>${measuredTime.duration}")
//recursion
val measuredTime2 = measureTimedValue {
BinarySearch.binarySearchByRecursion(1)
}
println("IndexOfTarget => ${measuredTime2.value} || measured time ==>${measuredTime2.duration}")
}실행 결과
내가 참고한 자료에 따르면 반복 구조를 사용하는 것이 재귀 호출로 구현하는 것보다 효율적이라고 한다. 하지만 결과는 반복보다 재귀를 이용한 방법이 빨랐다. 왜 반복 구조가 더 효율적이라고 하는 것일까?
관련글
[Iterative and Recursive Binary Search Algorithm] : https://iq.opengenus.org/binary-search-iterative-recursive/
위 글의 결론을 보면, 반복 이진 탐색 과 재귀 이진 탐색은 둘 다 같은 시간 복잡도를 갖지만, 공간(메모리) 사용 측면에서 다르다. 재귀 이진 탐색은 스택을 계속해서 쌓기 때문에 log(n) 최대 공간을 차지하지만, 반복 이진 탐색에서는 O(1)의 공간 만큼 차지한다. 즉, 공간 효율면에서 반복이 재귀 보다 효율적이라고 표현한 것이다.
개인적으로 결론을 내려보면, 메모리 효율을 중요시 하면 반복을 실행 시간을 중요시 하면 재귀를 사용하면 된다.
