완전탐색과 이진탐색

🌟 들어가기 전

알고리즘 공부를 하면서 가장 많이 쓰는 탐색 기술!!

레벨이 오르면 가장 많이 쓰는게 BFS와 DFS이다.

하지만 가장 간단하고 기본적인 탐색 기술은 아무래도 완전탐색이 아닌가 싶다.

 

기본이 되면서도 가벼운 완전탐색과 이진탐색을 알아보기로 하였다.

 

🔍 세부 내용

완전 탐색

모든 경우의 수를 탐색하여 답을 찾는 방식이다.

예를 들어 [1,2,3,4,5]의 배열이 있으면 5라는 숫자를 찾으려면 배열을 모두 돌아야만 찾을 수가 있다.

 

이렇게 모든 배열을 탐색하는 방법도 완전 탐색에 들어간다.

완전 탐색은 모든 원소를 순회해야 하므로 O(N)이라는 시간 복잡도를 가지고 있다.

 

그래서 코딩테스트 문제를 풀 때 완전탐색을 하는 경우에는 시간 초과 이슈가 발생할 수도 있다.

 

예시)

/* 배열에서 특정 숫자 찾기 */
fun bruteForceSearch(arr: List<Int>, target: Int): Boolean {
    for (num in arr) {
        if (num == target) return true
    }
    return false
}

 

이진 탐색

정렬된 배열에서 중간값을 기준으로 절반씩 범위를 줄여가며 찾는 방법이다.

 

위 예시처럼 [1,2,3,4,5]라는 배열이 있다.

이 배열이 정렬이 되어있는 경우에는 4이라는 숫자를 찾기 위해 이진 탐색을 사용할 수 있다.

 

배열 양 끝에 있는 1과 5의 중간 값을 찾아 확인을 하면 3이다.

3은 우리가 찾을 4보다는 작은 값이기 때문에 3 이후 값만 확인하면 된다.

 

이렇게 절반씩 끊어서 값을 찾는 탐색 기법을 이진 탐색이라고 한다.

이진 탐색은 범위를 절반씩 범위를 줄여가는 방식이기에 O(logN)의 시간 복잡도를 가지고 있다.

 

예시)

fun binarySearch(arr: List<Int>, target: Int): Boolean {
    var left = 0
    var right = arr.size - 1

    while (left <= right) {
        val mid = (left + right) / 2
        when {
            arr[mid] == target -> return true
            arr[mid] < target -> left = mid + 1
            else -> right = mid - 1
        }
    }
    return false
}

 

완전탐색 vs 이진탐색 성능 비교

만약 1,000,000개의 숫자 중에서 하나를 찾는다고 하면?

• 완전탐색: O(N) → 최대 1,000,000번 비교
• 이진탐색: O(log N) → 약 20번 비교

⮕ 데이터가 많을수록 이진탐색이 훨씬 빠름! 🚀

이진탐색을 사용할 수 있다면 최대한 활용하는 것이 좋고, 정렬되지 않은 데이터라면 완전탐색을 사용할 수 있다.

 

🤔 배운 점 & 느낀 점

가장 기본적인 탐색 방법이어도 한번씩은 짚고 넘어가주는 게 좋다.

무조건 BFS나 DFS가 능사는 아니다.

어쩔 때는 완전 탐색이 성능이 더 좋을수도 ㅋㅋㅋㅋ