C++ 코딩테스트 Week 04
Brute force(완전 탐색)
용어 정리
(나무 위키)
브루트 포스(brute force), **키 전수조사(exhaustive key search) 또는 **무차별 대입(無差別代入)은 조합 가능한 모든 문자열을 하나씩 대입해 보는 방식으로 암호를 해독하는 방법이다. 흔히 암호학에서 연구되나, 다른 알고리즘 분야에서도 사용되고 있다.
흔히 단순무식하게 수학 문제를 푸는 방법인 ‘계산 노가다‘의 학술적 개념이다.
1.1. 특징[편집]
영어 brute는 “짐승 같은, 난폭한”이라는 뜻이고, brute-force는 “(정제되지 않은) 난폭한 힘, 폭력”이라는 뜻이다. 시간과 자원이 엄청나게 들어서 얼핏 보면 무식하고 비효율적이라고 생각할 수도 있겠지만, 정확도 100%를 보장한다는 점에서 암호 해독법 중 가장 확실하고 무서운 방법이다. 이론적으로 가능한 모든 경우의 수를 다 검색해 보는 것이라 정확도 100%가 항상 보장되니, 암호학에서는 가장 확실한 방법으로 통용되고 있다. 무엇보다도 암호 확인 작업은 손으로 입력한 문자열의 동일 여부를 확인하는 것이기 때문에, 가능한 경우의 수를 하나씩 대입하다 보면 언젠가는 암호를 찾을 수 있게 되는 식이다. 다만 정말로 그냥 무식하게 때려 박는 건 아니고, 숫자만 섞어서 대입해 보기 한 번, 로마자만 섞어서 대입해 보기 한 번 이런 식으로 하다가 안 되면 나머지를 순차적으로 하는 식으로 특정 규칙에 따라 우선순위를 두고 하기도 한다.
브루트 포스의 특징은 거의 완벽하게 병렬 작업이 가능하다는 점이다.[1] 이 때문에 병렬 프로그래밍 기법을 사용하거나, GPGPU를 이용하기도 하며, 여러 대의 컴퓨터를 연결해서 동시에 작업할 수도 있다. 이렇게 하면 투자 자원에 비례해서 문제를 해결하는 시간을 줄일 수 있다. 즉, 컴퓨터를 10대 쓰면 10일 걸릴 작업을 1일 만에 끝낼 수 있다는 이야기이다. (암달의 법칙 때문에 이런 식으로 병렬화가 잘 되는 작업은 흔치 않다.)
90년대 초 김재열이 ‘청와대 해킹사건’을 저지르는 과정에서 국세재판소 비밀번호를 알아낼 때 이런 식으로 일일이 노가다를 했다. 그렇게 알아낸 비밀번호는 12345.
진짜로 0부터 하나씩 시도했으면 어이 터졌을 듯하다
cpp 기준 1초당 1억번(10^8)의 연산이 가능하므로, 문제의 시간 조건에 따라 적용해보면 된다.
반복문
배열(벡터)를 탐색하는 경우
#include <iostream>
#include <vector>
using namespace std;
int main(){
int target;
cin>>target;
vector<int> v={1,3,2,5,6,7};
for(int i=0;i<v.size();i++){
if(v[i]==target){
cout<<target<<"'s index : "<<i<<"\n";
break;
}
}
return 0;
}
숫자를 1부터 M까지 탐색하는 경우
아래 코드는 “2400”이 포함된 N번째 수를 찾는 코드이다
#include <iostream>
using namespace std;
int cnt,n;
int main(){
cin>>n;
int num=2400;
while(true){
string a=to_string(num);
if(a.find("2400")!=string::npos){
cnt++;
if(n==cnt){
cout<<a<<"is "<<n<<"th number contains 2400"<<endl;
break;
}
}
num++;
}
return 0;
}
참고로
string의 find() 함수는 해당 패턴이 문자열에 존재하지 않을 경우 string::npos를 반환함을 이용하는 코드이다
위 경우 m번째 수가 n이라면, 시간 복잡도는 O(n)이 걸리는 brute force 코드이다.
재귀함수
사실 재귀함수와 반복문을 풀 수 있는 게 동일하다
그러나 반복문으로 하는게 원만해서는 더 낫다.
왜냐하면 함수 호출에 대한 오버헤드가 크기 때문이다.
예제
N개의 요석후보가 주어질때, 숫자의 합이 소수가 되는 경우의 수를 출력 (N<=100)
input:
10
24 35 38 40 49 59 60 67 83 98
output:
176
[출처] [알고리즘 강의] 3주차. 완전탐색, 백트래킹|작성자 큰돌
메인 아이디어 : 숫자를 포함하거나, 안하거나 를 고려하면된다.
즉, 총 경우의 수는 2^N이고 2^100=8^33 여서 시간초과가 발생할 것으로 보이나, 그냥 가자.
#include <iostream>
#include <vector>
using namespace std;
int N,temp;
vector<int> v;
int checkPrime(int number){
if(number<=1) return 0;
if(number==2) return 1;
if(number%2==0) return 0;
for(int i=3;i*i<=number;i++){
if(number%i==0) return 0;
}
return 1;
}
int go(int index,int sum){
//base condition
if(index==N){
return checkPrime(sum);
}
return go(index+1,sum+v[index])+go(index+1,sum);
}
int main(){
cin>>N;
for(int i=0;i<N;i++){
cin>>temp;
v.push_back(temp);
}
cout<<go(0,0);
return 0;
}
포함시키거나 포함시키지 않음을 완탐으로 해서 경우의 수를 반환하는 재귀함수 이용하는 코드였다.
Back Tracking
백트래킹이란 완탐에서 가지치기만 더한 것을 의미한다.
즉, 완전 탐색을 하면서, 만일 특정 조건을 만족하게 된다면 바로 재귀를 종료하여 불필요한 탐색을 피한다.
예제
N과 N개의 자연수가 주어질때 몇개의 숫자를 골라 합을 mod 11했을때 나오는 가장 큰 수를 구하라
Input:
10
24 35 38 40 49 59 60 67 83 98
output:
10
[출처] [알고리즘 강의] 3주차. 완전탐색, 백트래킹|작성자 큰돌
완탐했을 경우 : 이때는 일딴 전부 더하고, depth가 N이 되면 비로소 그때야 mod 연산을 하기 때문에 비효율적
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int N,temp,ret;
int mod=11;
vector<int> v;
void go(int idx,int sum){
if(idx==N){
ret=max(ret,sum%mod);
return;
}
go(idx+1,sum+v[idx]);
go(idx+1,sum);
}
int main(){
cin>>N;
for(int i=0;i<N;i++){
cin>>temp;
v.push_back(temp);
}
go(0,0);
cout<<ret;
return 0;
}
백트래킹으로 만일 10이 나오면 조기 종료하도록 한 코드(mod 11의 최댓값은 10임)
한줄만 추가해주었을 뿐인데 함수 호출이 눈에 띄게 감소함
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int N,temp,ret;
int mod=11;
vector<int> v;
void go(int idx,int sum){
if(ret==10) return; // here!!!
if(idx==N){
ret=max(ret,sum%mod);
return;
}
go(idx+1,sum+v[idx]);
go(idx+1,sum);
}
int main(){
cin>>N;
for(int i=0;i<N;i++){
cin>>temp;
v.push_back(temp);
}
go(0,0);
cout<<ret;
return 0;
}
Restore
재귀함수를 이용할때는 다시 올라올때 원상태로 복원하는 것이 중요하다.
예를 들어 방문했던 노드의 방문기록을 다시 지우는 것이 이 예시이다.
예시 코드 (dfs)
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
bool visited[4];
vector<int> adj[4];
vector<int> v;
void printVector(){
for(int i:v) cout<<i<<" ";
cout<<endl;
}
void go(int idx){
//base case
if(v.size()==3){
printVector();
return;
}
//branch
for(int there : adj[idx]){
if(visited[there]) continue;
visited[there]=true;
v.push_back(there);
go(there);
visited[there]=false; //restore
v.pop_back(); //restore
}
}
int main() {
adj[0].push_back(1);
adj[1].push_back(2);
adj[1].push_back(3);
adj[1].push_back(0);
adj[2].push_back(1);
adj[3].push_back(1);
visited[0] = true; // 0부터 시작
v.push_back(0);
go(0);
return 0;
}
위와 같이 restore을 시켜줘야 이후 탐색이 영향을 받지 않게 된다.
예제
문제 : 긍정왕 홍철이의 구걸 여행
홍철이는 3 * 3 맵에서 {0, 0} 지점에서 길을 잃어버렸다. 긍정왕 홍철이는 길을 잃어버린 김에 구걸을 하면서 돈을 모으면서 여행을 가려고 한다. 목적지는 {2, 2}이며 방문한 정점은 다시 방문할 수 없고 해당 맵에 구걸로 얻을 수 있는 돈들이 있다. 홍철이는 4방향(상하좌우)로 움직일 수 있다. {2, 2}까지 간다고 했을 때 이 돈들을 모으는 모든 경우의 수를 출력하여라.
맵 :
{10, 20, 21},
{70, 90, 12},
{80, 110, 120}
[출처] [알고리즘 강의] 3주차. 완전탐색, 백트래킹 작성자 큰돌
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int N=3;
vector<int> v;
int a[3][3] = {
{10, 20, 21},
{70, 90, 12},
{80, 110, 120}
};
const int dy[]={-1,0,1,0};
const int dx[]={0,1,0,-1};
bool visited[N][N];
void print(){
for(int i:v) cout<<i<<" ";
cout<<endl;
}
void go(int y,int x){
if(y==N-1&&x==N-1) {
print();
return;
}
for(int i=0;i<4;i++){
int next_y=y+dy[i];
int next_x=x+dx[i];
if(next_y<0||next_x<0||next_y>=N||next_x>=N) continue;
if(visited[next_y][next_x]) continue;
visited[next_y][next_x]=true;
v.push_back(a[next_y][next_x]);
go(next_y,next_x);
visited[next_y][next_x]=false;
v.pop_back();
}
}
int main(){
visited[0][0]=true;
v.push_back(a[0][0]);
go(0,0);
return 0;
}
단순 방향벡터에다가 경로를 원복하는 원탐문제이다.
Leave a comment