[알고리즘 개념] 완전 탐색

완전 탐색

 

컴퓨터의 순기능을 이용하여, 모든 경우의 수를 탐색하는 방법이다.

 

모든 경우를 살펴보기 때문에 무조건 답을 찾을 수 있다는 장점이 있지만,

답을 찾는데 시간이 효율적이지 못하다는 단점이 있다.

 

따라서, 탐색할 요소가 적거나 N제한이 작은 경우에 완전 탐색을 사용한다.

 

 

구현 방법

 

1. 반복문 이용

- for문과 if문을 이용하여 코드를 작성한다.

재귀를 이용하는 것보다 코드 작성이 쉽지만, 중첩이 많이 일어난다는 단점이 있다.

 

for(int i = 0 ; i < n ; i++)
    for(int j = i + 1; j < n; j++)
        for(int k = j + 1; k < n; k++)
            for(int l = k + 1; l < n; l++)
                cout << i << " " << j << " " << k << " " << l << endl;

 

2. 재귀 이용

- 함수의 return 값을 이용하여 반복해준다.

코드 작성은 반복을 이용하는 것보다 어렵지만, 코드가 더 직관적이고 깔끔하다.

 

void pick(int n , vector<int>& picked, int toPick){
    //기저 사례 : 더 고를 원소가 없을 때 고른 원소들을 출력
    if(toPick == 0) { printPicked(picked); return ;}
    //고를 수 있는 가장 작은 번호를 계산
    int smallest = picked.empty() ? 0 : picked.back() + 1;
    //이 단계에서 원소 하나를 고른다
    for(int next = smallest; next < n; next++){
        picked.push_back(next);
        pick(n, picked, toPick - 1);
        picked.pop_back();
    }
}