완전 탐색 알고리즘 - Brute Force

완전 탐색 알고리즘 - Brute Force

: 모든 경우의 수를 확인하여 답을 찾아내는 알고리즘.

 

 

BF는, 모든 경우의 수를 확인하기 때문에 성공하면 100% 정확한 답을 찾아낼 수 있다.

 

만들기가 비교적 쉽고 병렬 작업이 가능하다는 장점을 가지고 있지만,

시간적인 측면에서는 비효율적이라는 단점을 가지고 있다.

 

탐색해야 할 요소들이 많은 경우에는 보다 효율적인 방법을 찾아서 사용하는 것이 좋겠지만,

개수가 정해져 있거나 적은 경우에는 완전 탐색을 사용하여 보다 쉽고 정확하게 답을 구할 수 있다.

 

 

 

완전 탐색을 구현하기 위해서는,

 

1. 반복문을 사용하거나 (for, while)

2. 재귀 함수를 사용할 수 있다. (return function / 같은 함수 호출의 반복)

 

 

 

재귀 함수의 경우, 더 이상 함수를 return 하지 않아야 하는 작업에 다다를 때까지 함수를 재호출한다.

return 시에 함수가 아닌 값을 return 하는 경우를 기저 사례 Base Case라고 한다. 

 

 

 

반복문의 경우는 원하는만큼 반복하면 되기에 재귀 호출보다는 접근하고 구현하기 쉽다.

 

재귀 함수의 경우는 여러 가지 예시가 있는데, 그 중에 최대공약수 GCD를 구하는 코드가 있다.

 

 

최대공약수 Greatest Common Divisor 재귀 함수 코드 with Kotiln

fun greatest_common_divisor(numA: Int, numB: Int): Int{
    if(numB == 0) return numA;	// Base Case일 경우 함수 호출을 멈추고 값을 반환
    else return greatest_common_divisor(numB, numA%numB) // 함수 재호출
}

fun main() {
    println(greatest_common_divisor(72, 90)) // 18, 재귀함수 시작
}