[개념 정리] 완전 탐색

완전 탐색이 뭘까?

 

이 글은 큰돌의 터전님의 강의인 10주 완성 C++ 코딩테스트 알고리즘 개념 교안을 참고하여 작성했습니다.

 

완전 탐색

완전탐색은 brute force라고도 불리며 모든 경우의 수를 탐색하는 알고리즘입니다.

경우의 수는 순열 또는 조합을 의미합니다. 보통 완전탐색은 경우의 수 생성 (순열/조합) + 각 경우마다 조건 검사 및 처리 (DFS 또는 BFS 등)으로 구성되어 있습니다. 

 

언제 완전탐색을 사용해야 할까요?

 

시간복잡도가 약 1억 번 이내라면 완전탐색을 써도 현실적으로 문제가 풀리게 됩니다. 컴퓨터가 1초에 약 1억 번 연산 가능하다고 보는 게 일반적 기준이기 때문입니다.

 

완전 탐색은 어떻게 구현할 수 있을까요?

 

완전 탐색을 하는 방법은 반복문을 활용한 완전 탐색, 재귀 호출을 활용한 완전 탐색으로 크게 2가지 방법이 존재합니다.

먼저, 반복문을 활용한 완전 탐색을 보겠습니다.

 

반복문을 활용한 완전탐색

반복문을 활용한 완전탐색은 for문, while문을 활용한 방법으로 2가지 방법이 존재합니다.

1부터 10까지 들어있는 배열을 완전탐색 해보겠습니다.

 

for문을 활용한 완전탐색을 구현한 코드는 다음과 같습니다.

public static void bruteForceWithFor() {
    for(int i = 0; i < numbers.length; i++) {
        System.out.print(numbers[i] + " ");
    }
}

 

출력한 결과는 다음과 같습니다.

 

 

while문을 활용한 완전탐색을 구현한 코드는 다음과 같습니다.

public static void bruteForceWithWhile() {

    int i = 0;

    while(i < 10) {
        System.out.print(numbers[i] + " ");
        i++;
    }
}

 

출력한 결과는 다음과 같습니다.

 

두 방법 모두 완전 탐색이 잘 되는 것을 확인할 수 있습니다.

반복문을 활용한 완전 탐색을 알아봤습니다. 이번엔 재귀 호출을 통한 반복문을 알아보겠습니다.

 

재귀 호출을 활용한 완전탐색

 

재귀 호출을 활용한 완전탐색을 구현한 코드는 다음과 같습니다.

public static void bruteForceWithRecur(int i) {
    if(i == numbers.length) {
        return;
    }

    System.out.print(numbers[i] + " ");
    bruteForceWithRecur(++i);
}

 

 

출력한 결과는 다음과 같습니다.

 

언제, 재귀 호출을 사용해야 할까요?

 

반복문으로 완전탐색이 가능하다면 반드시 반복문을 우선 사용하는 것이 좋습니다.
왜냐하면, 재귀 호출은 함수 호출마다 추가적인 비용(call stack 관리 등)이 발생하기 때문에, 반복문보다 성능이 더 나쁠 가능성이 높습니다.

 

만약, 반복문으로 구현하기가 힘든 경우나 어떠한 행위는 반복하는데 매개변수만 수정해서 넘기면 될 거 같은 경우엔  재귀함수를 사용하면 됩니다.