브루트 포스
완전 탐색 기법으로 오래 걸리는 데다 자원이 엄청나게 들어서 얼핏 보면 무식하다고 생각할 수도 있겠지만, 항상 정확도 100%를 보장한다는 점에서 암호 해독법 중 가장 확실하고 무서운 방법이다.
이론적으로 가능한 모든 경우의 수를 다 검색해 보는 것이라 정확도 100%가 항상 보장되니, 암호학에서는 가장 확실한 방법으로 통용되고 있다.
→ 우선 완전 검색으로 접근하여 해답 도출 후, 성능 개선을 위해 다른 알고리즘을 사용하고 해답을 확인하는 것이 바람직
순조부
브루트 포스에서 사용되는 알고리즘 중 필수적으로 알아야 하는 것이 순열, 조합, 부분집합이다.
순열
우선 순열부터 소개하겠다.
순열이란 서로 다른 것들 중 몇 개를 뽑아서 한 줄로 나열하는 것
즉, 서로 다른 n개 중 r개를 택하는 것 이다.
수학적으로
이라고 표기하며 팩토리얼(Factorial)이라 부른다.
import java.util.Arrays;
import java.util.Iterator;
import java.util.Scanner;
public class PermutationTest {
//평소엔 매개변수로 넘기자
static int N, R, totalCnt;
static int[] numbers, input; //뽑힌 애들
static boolean[] isSelected;
// nPn : n개의 입력받은 수 중 n개를 모두 뽑아 순서적으로 나열한 것
// nPr : n개의 입력받은 수 중 r개를 모두 뽑아 순서적으로 나열한 것(1<=r<=n)
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
N = sc.nextInt();
R = sc.nextInt();
totalCnt = 0;
input = new int[N];
numbers = new int[R];
isSelected = new boolean[N]; // 수가 1부터 시작해서 인덱스도 1부터 논리적 매칭 사용
for (int i = 0; i < N; i++) {
input[i] = sc.nextInt();
}
perm(0);
System.out.println("총 경우의 수 : "+totalCnt);
}
private static void perm(int cnt) { //cnt : 직전까지 뽑은 순열에 포함된 수의 개수, cnt+1번째 해당하는 순열에 포함될 수를 뽑기
if(cnt == R) { //기저조건
totalCnt++;
System.out.println(Arrays.toString(numbers));
return;
}
// 가능한 모든 수에 대해 시도(input 배열의 모든 수 시도)
for (int i = 0; i < N; i++) { // 선택지
// 시도하는 수가 선택되었는지 판단
if(isSelected[i]) continue;
// 선택되지 않았다면 수를 사용
numbers[cnt] = input[i];
isSelected[i] = true;
// 다음수 뽑으러 가기
perm(cnt+1);
// 사용했던 수에 대한 선택 되돌리기
isSelected[i] = false;
}
}
}조합
다음은 조합이다.
조합이란 서로 다른 n개의 원소 중 r개를 순서 없이 골라낸 것 이다.
→ 재귀적 표현
import java.util.Arrays;
import java.util.Iterator;
import java.util.Scanner;
public class CombinationTest {
//평소엔 매개변수로 넘기자
static int N, R, totalCnt;
static int[] numbers, input;
// nCr : n개의 입력받은 수 중 r개를 모두 뽑아 순서 없이 나열한 것(1<=r<=n)
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
N = sc.nextInt();
R = sc.nextInt();
totalCnt = 0;
input = new int[N]; //n개의 원소를 가지고 있는 배열
numbers = new int[R]; //r개의 크기의 배열, 조합이 저장될 배열
for (int i = 0; i < N; i++) {
input[i] = sc.nextInt();
}
comb(0, 0);
System.out.println("총 경우의 수 : "+totalCnt);
}
private static void comb(int cnt, int start) { //cnt : 직전까지 뽑은 조합에 포함된 수의 개수, start : 시도할 수의 시작 위치
if(cnt == R) { //기저조건
totalCnt++;
System.out.println(Arrays.toString(numbers));
return; //조합생성완료
}
// 가능한 모든 수에 대해 시도(input 배열의 모든 수 시도)
// start 부터 처리 시 중복 수 추출 방지 및 순서가 다른 조합 추출 방지
for (int i = start; i < N; i++) { // 선택지
// start 위치부터 처리했으므로 중복체크 필요없음!!
// 앞쪽에서 선택되지 않았다면 수를 사용
numbers[cnt] = input[i];
// 다음수 뽑으러 가기
comb(cnt + 1, i + 1);
}
}
}부분집합
마지막으로 부분집합 이다.
집합에 포함된 원소들을 선택하는 것
다수의 중요 알고리즘들 → 원소들의 그룹에서 최적의 부분 집합을 찾는 것
집합의 원소가 n개일 때, 공집합을 포함한 부분집합의 수 ⇒ 개
= 각 원소를 부분 집합에 포함시키거나 포함시키지 않는 2가지 경우를 모든 원소에 적용한 경우의 수
import java.util.Scanner;
public class SubSetTest {
static int N, totalCnt;
static int[] numbers, input; //뽑힌 애들
static boolean[] isSelected;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
N = sc.nextInt();
totalCnt = 0;
input = new int[N];
numbers = new int[N];
isSelected = new boolean[N]; // 수가 1부터 시작해서 인덱스도 1부터 논리적 매칭 사용
for (int i = 0; i < N; i++) {
input[i] = sc.nextInt();
}
subset(0);
System.out.println("총 경우의 수 : "+totalCnt);
}
private static void subset(int index) { // index : 부분집합에 고려할 대상 원소의 인덱스 cnt : 직전까지 고려한 원소 수
if(index == N) { // 더이상 고려할 원소가 없다면 부분집합의 구성이 완성
totalCnt++;
for (int i = 0; i < N; i++) {
System.out.print(isSelected[i]?input[i]:"X");
System.out.print("\t");
}
System.out.println();
return;
}
// 원소 선택
isSelected[index] = true;
subset(index+1);
// 원소 미선택
isSelected[index] = false;
subset(index+1);
}
}