완전탐색 알고리즘이란? |
완전탐색은 가능한 모든 경우의 수를 다 체크해서 정답을 찾는 방법
무식하게 푼다는 의미인 Brute-Force(브루트 포스) 라고도 부름
근데 그냥 브루트포스는 완전탐색의 여러 종류 중 하나라고 이해하는게 더 나을 듯 함
완전탐색은 모든 경우의 수를 확인하므로 N의 크기가 너무 크면 비효율적이게 되므로 N의 크기가 작을때만 완전탐색을 사용한다.
브루트포스의 대표적인 예시로 네자리수 비밀번호를 찾는다면 0000~9999를 직접 다 입력해보는 방식
하지만 문제해결 알고리즘을 사용할때에는 알고리즘이 효율적인지 고려해야 하므로 브루트포스는 항상 좋은 방법이 아니다.
브루트포스 외에 더 효율적인 방법이 있다면 해당 방법을 사용하는것이 좋다.
대표적인 완전탐색 알고리즘
1. Brute Force 기법 : 반복문 / 조건문을 활용해 모든 경우를 테스트하는 방법
2. 순열(Permutation) : N개의 원소 중 R개의 원소를 중복 허용 없이 나열하는 방법
3. 재귀 호출(Recursive)
4. 비트마스크 : 2진수 표현 기법을 활용하는 방법
5. DFS : 그래프 완전탐색 방법
1. Brute Force |
반복문 / 조건문을 활용해 모든 경우를 테스트하는 방법
네자리수 비밀번호를 찾는다면 0000 ~ 9999를 모두 입력해보는 방식
#include <iostream>
void bruteForce(const int pw)
{
for (int i = 0; i < 10000; i++) {
if (pw == i) {
printf("%04d", i);
break;
}
}
}
int main()
{
const int password = 1234;
bruteForce(password);
return 0;
}
2. 순열(Permutation) |
1) 순열이란
N개의 원소 중 R개의 원소를 중복 허용 없이 나열하며 순서가 다르다면 다른 수열로 연산하는 방법
예를들어 수열 { 1, 2, 3 }이 있다면 이 수열을 { 1, 2, 3 }과 { 3, 2, 1 }로 보는것의 차이가 필요한 경우 순열을 사용한다.
2) 순열의 특징
- N개의 서로 다른 데이터가 수열로 이루어져있다면 순열의 전체 가지수는 N!가지가 됨
- 같은 데이터로 이루어진 수열이지만 그 순서에 의미가 있고 바로 이전/다음 수열을 알 수 있음
- 수열의 i번째 값부터 모두 내림차순이라면 해당 순열은 1번째값~i번째값으로 시작하는 순열 중 최종순열
- 수열의 i번째 값부터 모두 오름차순이라면 해당 순열은 1번째값~i번째값으로 시작하는 순열 중 최초순열
자세히 설명해 보자면 만약 {1, 2, 3} 수열을 순열로 모두 나열한다면
{ 1 2 3 } // 최초순열은 오름차순
{ 1 3 2 }
{ 2 1 3 }
{ 2 3 1 }
{ 3 1 2 }
{ 3 2 1 } // 최종순열은 내림차순가지수가 3!인 6가지 종류가 나오며 최초순열을 오름차순이며 최종순열은 내림차순이 된다.
또한 1로 시작하는 순열 중 최초순열은 { 1 2 3 }이 되므로 1의 뒷부분부터 오름차순이고
1로 시작하는 순열 중 최종순열은 { 1 3 2 }가 되므로 1의 뒷부분부터 내림차순이다.
3) 순열을 만드는 알고리즘
우선 감사하게도 STL algorithm 헤더에 순열 알고리즘이 구현되어 있다.
/*
조건 1) 오름차순으로 정렬된 컨테이너로만 사용 가능
조건 2) default값이 오름차순으로 된 순열 생성이다
조건 3) 중복된 원소가 있다면 결과에서는 한번만 출력함
예를들어 수열이 { 0 0 1 }이라면
6가지 순열이 아닌 중복 제외된 {0 0 1}, {0 1 0}, {1 0 0} 3가지만 만들어줌
bool next_permutation (BidirectionalIterator first, BidirectionalIterator last);
bool next_permutation (BidirectionalIterator first, BidirectionalIterator last, Compare comp);
다음 순열이 존재하면 해당 컨테이너를 다음 순열로 만들고 true를 리턴
다음 순열이 없다면 false를 리턴
이전 순열은 prev_permutation
*/
#include <iostream>
#include <vector>
#include <algorithm>
int main() {
vector<int> vec{1, 2, 3};
sort(v.begin(), v.end());
do {
for (int v : vec) {
cout << v << ' ';
}
cout << endl;
} while (next_permutation(v.begin(), v.end()));
return 0;
}
원리를 살펴보자면 1 ~ 10으로 구성된 수열이 있다면
...
{ 3 4 5 10 9 8 7 6 2 1 } // 3 4 5 로 시작하는 순열 중 최종순열
{ 3 4 6 1 2 5 7 8 9 10 } // 3 4 6 로 시작하는 순열 중 최초순열
...위 모습처럼 될 텐데 i = 3라고 할때 최종순열의 바로 다음순열인 최초순열을 만드는 방법은
1 ~ (i -1)번째 순열까지는 그대로 두고(위에서는 3 4까지)
i번째 값을 (i + 1) ~ N중 i보다는 크지만 (i + 1) ~ N중 가장 작은 값과 교환하고
(i + 1) ~ N은 오름차순으로 만들면 된다.
위 규칙을 통해 이전 / 다음 순열을 구하거나 모든 순열을 완전 탐색으로 구하는 로직을 수현할 수 있으나 해당 알고리즘은 N개의 숫자에 대한 순열을 모두 구하게 만드는 알고리즘이며 시간복잡도가 O(N!)가 되므로 너무 높으므로 N의 크기가 아주 작을때만 사용해볼만하다.
C++과 Python에서는 순열함수를 제공하지만 Java에서는 제공하지 않는다고 한다.
직접 구현해보려면 아래의 로직대로 해보면 될 듯 하다.
※ 순열을 구현하는 방법
현재 순열을 구성하는 배열을 A라고 하고 i,j는 그 배열의 index 값을 의미한다고 하자.
예를 들어 A={7, 2, 3, 6, 5, 4, 1}이고 i, j는 각각의 index 값이다.
아래에서는 현재의 다음 순열을 구하는 로직을 기반으로 설명한다.
1. A[i-1] <= A[i]를 만족하는 i 중 가장 큰 값을 찾는다.
(혹은 뒤에서부터 찾는 경우 A[i-1] >= A[i] 중 가장 작은 i를 찾는다.)
→ 현재 i값을 기준으로 이후는 모두 내림차순으로 되는 경우를 찾는 다는 것이다. 현재 기준 최종 순열을 찾음
A배열을 보면 A[i-1] < A[i]가 되는 가장 큰 i는 6인 3번째(0부터 시작)이다. 즉, i=3이 된다.
2. j >= i 중, A[j] > A[i-1]을 만족하는 가장 큰 j의 값을 찾는다.
→ 현재가 최종 순열 상태이므로 i-1번째 숫자를 변경하여 최초 순열을 찾아야 한다.
A배열을 기준으로 i-1번째 숫자는 3으로 3보다 큰 경우는 6, 5, 4이나 그 중 j 값이 가장 큰 경우는 4이다.
3. A[i-1]과 A[j]를 Swap한다.
→ i-1인 2번째 숫자 3과 j인 5번째 숫자 4를 변경한다. A 배열은 다음과 같이 변경된다.
A={7, 2, 4, 6, 5, 3, 1}
4. i이후의 순열을 모두 뒤집는다.
→ 최초 순열 상태로 만들어야 하므로 i번째부터는 오름차순으로 만들어야 한다. A 배열은 다음과 같이 변경된다.
A={7, 2, 4, 1, 3, 5, 6}
출처 : https://hongjw1938.tistory.com/78
3. 재귀 호출(Recursive) |
재귀는 말 그대로 자기 자신을 호출하는 것을 의미한다.
주로 각 원소가 포함되거나 or 포함되지 않거나 두가지 선택을 가질때 사용한다.
다만 반복문으로 될 것 같으면 무조건 반복문을 사용하는게 우선이다.
함수를 여러번 호출하는것은 코스트가 크고 함수 콜 스택이 깊어지면 프로그램이 죽을 수도 있다.
반복문으로 안될것같거나 너무 복잡해지거나 어떤 행위를 반복은 하는데 매개변수만 변경해서 넘기면 될 것 같을때 사용한다.
예시)
숫자 1, 2, 3이 써있는데 세명의 사람이 그 숫자 중 하나를 선택하는 모든 경우의 수
1 1 1이 될수도 있고 1 1 2나 1 3 2나 3 1 2 등 각자 선택한 숫자의 모든 경우의 수를 반복문으로 쓴다면
3중 for문이 되겠지만 숫자가 10개라면 O(N^10)이므로 가치없는 알고리즘이 됨
예시의 일반적인 알고리즘 틀은 아래 코드와 같음
int arr[3];
void getRecursion(int idx)
{
if(idx > 2) {
for(int i = 0; i < 3; i++) { // 여기서의 3은 출력할 숫자의 갯수
std::cout << arr[i] << ' ';
}
std::cout << '\n';
}
else {
for(int i = 1; i <= 3; i++) { // 여기서의 1과 3은 출력할 숫자의 숫자 범위
arr[idx] = i;
getRecursion(idx + 1);
}
}
}
출처 : https://seminzzang.tistory.com/100
자세한 동작 방식은 위 사이트에서 볼 수 있음
재귀함수 구현시 중요점
1) 재귀를 탈출하기 위한 탈출조건이 필요
2) 현재 함수의 상태를 저장하는 parameter가 필요
3) return문을 신경써야 함
DP의 Top-Down방식에서 사용하는 재귀와의 차이점은 DP는 작은 문제들의 해결을 모아서 큰 문제를 해결하는 모양새라면
완전탐색에서의 재귀는 큰 문제와 작은 문제의 구조가 다르거나, 이전 결과를 반드시 기억하지 않아도 해결 가능한 모든 방법을 탐색한다는 차이점이 있음
즉 DP의 Top-Down은 일반적인 재귀 중에서도 DP의 조건을 만족 하는 경우에 사용하는 것
4. 비트마스크 |
비트마스크란 비트(bit) 연산을 이용해 부분집합을 표현하는 방법에 대한 것
다른 글에 정리해 뒀으므로 링크만 남겨둠
https://smallpants.tistory.com/103
비트마스킹
비트마스킹이란? 비트마스킹 혹은 비트마스크라고 불리며 2진수를 이용하는 컴퓨터의 연산을 이용하는 방식 비트마스크는 완전탐색에서 문제에서 나올수 있는 모든 경우의 수가 각각의 원소가
smallpants.tistory.com
5. DFS |
그래프 자료구조에서 모든 정점을 탐색하기 위한 방법
DFS는 다른 글에 정리해뒀으니 링크만 걸어 둠
https://smallpants.tistory.com/88
그래프이론, DFS, BFS, 트리순회
그래프이론 먼저 그래프와 트리에 관련된 알고리즘인 만큼 그래프와 트리 자료구조에 대한 이해가 먼저 필요함 자료구조 1. 단순 구조 - 흔히 말하는 자료형(data type)으로 C언어에서의 bool, char, in
smallpants.tistory.com
6. 백트래킹 |
백트래킹이란 완전탐색 중 DFS나 재귀호출을 사용할때 시간절약을 위한 전략이다.
완전탐색은 말 그대로 모든 경우의 수를 완전히 전부 탐색하는 개념이지만 이미 조건에 맞지 않은 방향으로 진행중이라면 굳이 해당 방향은 완전탐색할 필요는 없으므로 그 쪽으로 진행하지 않고 시간을 절약하는 것
완전탐색에 가지치기가 추가된 개념이며 해를 찾아 나가는 모습이 트리의 모양(상태공간트리)이라서 DFS와 유사하다.
두가지 기법을 사용한다.
1) Promising : 해당 루트가 조건에 맞는지 검사하는 기법
2) Pruning : 가지치기, 조건에 맞지 않으면 포기하고 다른 루트로 바로 돌아서서 탐색의 시간을 절약하는 기법
어떤 제약조건을 만족하는 해를 찾으면서 각 후보군을 DFS로 확인하며 점진적으로 상태공간트리를 탐색하다가 현재 진행중인 답이 제약조건을 만족하는지 체크(Promising - 솔루션이 될수 있는지)하고
만약 조건에 맞지 않는다면 해당 루트로는 가지 않는다고 표시하고(Pruning - 가지를 쳐버림) 다음 후보군으로 넘어가거나 이전의 상태로 돌아간다.
예시 1) 쉬운 백트래킹 예제
모든 케이스를 브루트포스 할 필요가 없는게 눈으로 보이는 케이스
숫자배열 { 24 35 38 40 49 59 60 67 83 98 }이 있을때 11로 나눈 나머지가 가장 큰 수를 구하라고 한다면
완전 탐색으로 모든 수를 11로 나눠보고 가장 큰 값을 찾아도 되겠지만 이렇게 하면 숫자 배열이 아주 크다면 너무 오랜 시간을 소비하므로
11로 나눴을때 나올수 있는 가장 큰 값인 10이 나오면 바로 반복문이나 재귀를 종료하게 만들면 시간절약을 할 수 있음
즉 간단하게 if(mod = 10) return; 한줄 추가해줌으로써 굳이 끝까지 완전탐색을 하지 않아도 되도록 시간절약을 해주는 것
예시 2) 대표적인 백트래킹 예제
https://www.acmicpc.net/problem/15649
15649번: N과 M (1)
한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해
www.acmicpc.net
1부터 N까지의 자연수 중에 중복없이 M개를 고른 수열을 모두 나열하라.
예를들어 N = 4, M = 3이라면 1~4 중에 3개를 나열하는 중복없이 방법이므로
1 2 3
1 2 4
1 3 2
1 3 4
2 1 3
2 1 4
....위처럼 숫자들이 쭉 나열되어야 함
#include <iostream>
#define MAX 9
using namespace std;
int n,m;
int arr[MAX];
bool visited[MAX];
void dfs(int depth) {
if (depth == m) { // 조건과 맞으면 출력
for (int i = 0; i < m; i++) {
cout << arr[i] << " ";
}
cout << "\n";
return;
}
for (int i = 1; i <= n; i++) {
if (!visited[i]) { // 현재 방문되어있는 상태인지 검사
visited[i] = true;
arr[depth] = i;
dfs(depth + 1); // 재귀
visited[i] = false;
}
}
}
int main() {
cin >> n >> m;
dfs(0);
return 0;
}
예시 3) 꽤 어려운 백트래킹 예제
https://www.acmicpc.net/problem/9663
9663번: N-Queen
N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.
www.acmicpc.net
정말 아무리 봐도 접근 방법조차 떠오르지 않아서 풀이 방법만 보고 직접 코드 짜보려고 노력함
다만 몇가지 난항이 있었음
1) 개인적으로 가장 못하고 두려워하는 분야가 재귀
2) dfs방식 중에 가기전에 확인하고 가는 방식과, 일단 가고 안되면 돌아오는 방식 두가지가 있는데
이 중 개인적으로 가기 전에 확인하는 방식만 주로 써왔음
이 방법으로 하면 코드가 훨씬 지저분해짐, 둘 다 더 쉬운 상황이 있으니 익혀야 함
3) 완전탐색/백트래킹/재귀 자체가 정말 천재가 아니고서야 경험이 꽤 쌓여야 접근 방식이라도 보일것같음
일단 대략적으로 느껴지는건 처음것 선택한 후 두번째것 선택하고 세번째것 선택하는데 세번째것 선택에서 조건과 맞지 않으면 두번째것 선택을 바꿔야 하므로 되돌아가야함. 이런 경우가 발생한다면 재귀를 사용한다라고 떠올려야 할듯
#include <bits/stdc++.h>
using namespace std;
int N;
int arr[15];
int ans;
bool check(int x)
{
for (int i = 0; i < x; i++) {
if (arr[x] == arr[i] || (x - i) == abs(arr[x] - arr[i])) return false;
}
return true;
}
void reculsive(int x)
{
if (x == N) ans++;
else {
for (int i = 0; i < N; i++) {
arr[x] = i;
if (check(x)) reculsive(x + 1);
}
}
}
void solve()
{
cin >> N;
reculsive(0);
cout << ans;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(NULL);
solve();
return 0;
}
출처 및 참고 사이트
https://seminzzang.tistory.com/100
https://hongjw1938.tistory.com/78
https://blog.naver.com/jhc9639/222300377004
https://buganddog.tistory.com/7