[알고리즘] 완전탐색 (브루트 포스 알고리즘) 이란

 

완전탐색 알고리즘의 개념

완전탐색이란 모든 경우의 수를 시도하여 정답을 찾는 방법입니다. 무식하게 푼다하여 Brute Force라고도 합니다.

가장 간단한 방법으로 구현이 쉽다는 장점이 있지만 시간이 오래걸린다는 단점이 있습니다.

 

ex) 1,2,3,4,5,6,7,8 중에 2개를 뽑아서 합이 3인 순열을 구해주세요

 

완전탐색을 사용하면

[1,2], [1,3], [1,4] .... [7,8] 순으로 모든 경우의 수를 탐색을 시작하여 답을 도출합니다

정답 -> [1,2] , [2,1]

 

 

완전탐색 종류

브루트포스 -> 특별한 기법 없이 for문 if문을 사용하여 모든 경우의 수를 탐색해 답을 구합니다.

 

순열 -> 순열 또는 조합을 통해 서로 다른 n개를 나렬하는것 또는 n개를 뽑는것 을 구할 수 있습니다

func permutation<T: Comparable>(_ array: [T], _ n: Int) -> [[T]] {
    var result = [[T]]()
    if array.count < n { return result }

    var visited = Array(repeating: false, count: array.count)
    
    func cycle(_ now: [T]) {
        if now.count == n {
            result.append(now)
            return
        }
        
        for i in 0..<array.count {
            if visited[i] {
                continue
            } else {
                visited[i] = true
                cycle(now + [array[i]])
                visited[i] = false
            }
        }
    }
    
    cycle([])
    
    return result
}

func combination<T: Comparable>(_ array: [T], _ n: Int) -> [[T]] {
    var result = [[T]]()
    if array.count < n { return result }

    var stack = array.enumerated().map { ([$0.element], $0.offset) }
    
    while stack.count > 0 {
        // print(stack)
        let now = stack.removeLast()
        
        let elements = now.0
        let index = now.1
        
        if elements.count == n {
            result.append(elements.sorted())
            continue
        }
        
        guard index+1 <= array.count-1 else { continue }
        
        for i in index+1...array.count-1 {
            stack.append((elements + [array[i]], i))
        }
        
    }
    
    return result
}

 

 

BFS/DFS -> 너비우선 탐색 , 깊이우선 탐색을 의미합니다

 

BFS 는 현재 정점과 인접한 정접을 우선으로 탐색입니다.

DFS 는 현재 인접한 정점을 탐색 후 그 더 깊은 인접한 정점을 끝까지 탐색하는

방식입니다.

 

 

왜 사용해야할까 or 나만의 고민

개발의 과정에는 2가지가 있다고 생각합니다.

 

구현과 최적화

 

최적화를 도저히 진행할 수 없을때 사용하여 구현을 먼저 진행합니다. ( 완전탐색 )

그후 더 효율적인 방법이 존재하면은 변경을 시도합니다.

데이터의 값이 적을때 사용하면은 빠르게 구현 가능하기 때문에 장점으로 작용합니다.