본문으로 바로가기

[알고리즘] 완전탐색

category 알고리즘/알고리즘 개념 2018. 4. 11. 21:46

글에 앞서...


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

활용하기 때문입니다.


재귀함수의 기본적인 이해


** 재귀함수란?

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

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


** 재귀함수 호출방식

1
2
3
4
5
void RecursiveFunction(void)
{
    printf("Recursive function example1 \n");
    RecursiveFunction();
}

cs


※ 기저 사례 (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



댓글을 달아 주세요