[알고리즘] 완전탐색

글에 앞서...

재귀적 호출에 대한 개념을 먼저 설명드릴까합니다. 그 이유는 알고리즘에서 해당 호출방식을 자주

활용하기 때문입니다.

재귀함수의 기본적인 이해

** 재귀함수란?

: 함수 내에서 자기 자신을 다시 호출하는 함수

: 자신이 수행할 작업을 유사한 형태의 여러 조각으로 쪼갠 뒤 그 중 한 조각을 수행하고, 나머지를 자기 자신을 호출해 실행하는 함수

** 재귀함수 호출방식

void RecursiveFunction(void)
{
    printf("Recursive function example1 \n");
    RecursiveFunction();
}

※ 기저 사례 (base case)

▷ 더 이상 쪼개지지 않는 가장 작은 작업, 즉 최소한의 작업에 도달했을 때 답을 곧장 반환하는 조건문에 포함될 내용

▷ 기저 사례를 선택할 때는 존재하는 모든 입력이 항상 기저 사례의 답을 이용해 계산될 수 있도록 신경써야 한다.

완전탐색(exhaustive search)

① 완전탐색이란?

▷ '무식하게 푼다(brute-force)'는 컴퓨터의 빠른 계산 능력을 이용해 가능한 경우의 수를 일일이 나열하면서 답을 찾는 방법을 의미. 이렇게 가능한 방법을 전부 만들어 보는 알고리즘을 뜻한다.

▷ 완전 탐색은 컴퓨터의 빠른 계산 속도를 잘 이용하는 방법이다.

▷ (예제) n개의 원소 중 m개를 고르는 모든 조합을 출력하는 코드

▷ 완전 탐색 방법

1. Brute Force : for문과 if문을 이용하여 처음부터 끝까지 탐색하는 방법
2. 비트마스크
3. 순열 : 순열의 시간 복잡도는 O(N!)
4. 백트래킹
5. BFS

  위의 5가지 방법을 이용한 완전탐색 방법 모두를 익히는 것을 추천합니다!!!

  모든 경우의 수를 탐색하는 방법은 문제를 접했을 때 가장 쉬운 방법이지만, 기초라고도 볼 수 있습니다.

  그리고 문제에서 제한조건과 위의 몇 가지 SKILL을 추가하여 푼다면 문제 해결 시간을 크게 향상 시킬 수 있습니다.

② 완전 탐색 문제

※ 코드 보기를 누르시면 제가 해결한 코드를 보실 수 있습니다.

(백준 10974) 모든순열 (https://www.acmicpc.net/problem/10974)

(백준 10819) 차이를 최대로 (https://www.acmicpc.net/problem/10819)

(백준 6603) 로또 (https://www.acmicpc.net/problem/6603)   [방법1 설명] ▷ 기본 모든 순열 코드 + 오름차순 조건만 추가하면 된다.   [방법2 설명] ▷ 백트래킹 알고리즘을 적용해서 푸는 것이 가능하다. ▷ 출력 예제를 보면 모든 경우의 수를 오름차순으로 출력하므로, DFS를 통해 깊이 탐색한 후 6개를 고르면 백트래킹을 통해 고르지 않은 다음 번호를 고르면 된다. ▷ depth가 6이 안되는 재귀함수들은 계속적으로 dfs를 호출, 결국엔 depth가 6인 배열들만 출력된다.

(백준 2309) 일곱난쟁이 (https://www.acmicpc.net/problem/2309) [설명] ▷ 9명 중 7명이 진짜 난쟁이이므로, 2명을 제외한 키의 합이 100인 경우를 찾으면 된다.

(백준 10971) 외판원 순회 2 (https://www.acmicpc.net/problem/10971) [설명] ▷ 백준 2098 - 외판원순회도 풀어보는 것을 추천한다.

(백준 1759) 암호 만들기 (https://www.acmicpc.net/problem/1759) [설명] ▷ 백트래킹 알고리즘에 제한조건(자음 2개이상 && 모음 1개이상)만 추가해줘서 풀면 됩니다.

※ 참고 [설명] ▷ 0과 1로 이루어진 모든 n 자리 경우의 수 출력

참고

1. 윤성우의 열혈 자료구조
2. 프로그래밍 대회에서 배우는 알고리즘 문제해결전략
3. http://baactree.tistory.com/30?category=732753
4. https://kks227.blog.me/220769870195
5. http://ikso2000.tistory.com/81?category=778103