- 해당 알고리즘은 경우의 수가 작을 때 사용하는 것이 일반적입니다. - 대표적인 예시로는 좌물쇠의 비밀번호를 알 수 없는 경우 모든 경우를 대입하여서 비밀번호를 찾아가는 경우가 있습니다.
[ 더 알아보기 ] 💡 브루트 포스(Brute-Force)의 의미
- 영어로 부르트 포스는 "난폭한 힘, 폭력"이라는 뜻을 의미하며 무식하지만 확실한 방식을 의미합니다. 이는 수행하는데 오래 걸리는 데다 자원이 많이 소요되지만 이론적으로 가능한 수를 모두 검색하기에 예상된 결과를 얻을 수 있습니다.
💡 완전 탐색에서 브루트 포스란?
- 모든 경우의 수를 탐색하여 최적의 결과를 찾아가는 완전탐색에서 브루트 포스는 모든 경우를 다 검사하여 원하는 값을 탐색하는 방법입니다. 💡 브루트 포스를 이용한 공격방식이란?
- 해커들은 이 알고리즘을 이용하여 다양한 공격을 시도합니다. - 예를 들어, 로그인 페이지에서 사용자 이름과 비밀번호를 입력하여 로그인하는 경우 해커들은 브루트 포스 알고리즘을 이용하여 가능한 모든 비밀번호를 시도하면서 로그인을 시도합니다. 이러한 공격을 방지하기 위해서는 강력한 비밀번호를 사용하고 로그인 시도 횟수를 제안하는 등의 보안 조치를 취해야 합니다.
1. 브루트 포스의 사용예시
1. 배열 탐색
💡 배열 탐색
- 배열에서 특정 값을 찾는 문제에서 브루트 포스 알고리즘은 배열을 모두 탐색하여 값을 찾는 방식으로 문제를 해결합니다.
public static int findIndex(int[] arr, int target) {
for (int i = 0; i < arr.length; i++) {
if (arr[i] == target) {
return i;
}
}
return -1;
}
2. 문자열 비교
💡문자열 비교
- 문자열 비교 문제에서 브루트 포스 알고리즘은 가능한 모든 문자열 쌍을 비교하여 최소값 또는 최대값을 찾는 방식으로 문제를 해결합니다.
public static int stringCompare(String s1, String s2) {
int n1 = s1.length(), n2 = s2.length();
int min = Math.min(n1, n2);
for (int i = 0; i < min; i++) {
if (s1.charAt(i) != s2.charAt(i)) {
return s1.charAt(i) - s2.charAt(i);
}
}
if (n1 == n2) {
return 0;
} else if (n1 > n2) {
return s1.charAt(min);
} else {
return s2.charAt(min);
}
}
int a = 10; // 1010
int b = 12; // 1100
int result1 = a & b; // 1000
int result2 = a | b; // 1110
int result3 = a ^ b; // 0110
int result4 = a << 1; // 10100
int result5 = a >> 1; // 0101
2. 비트마스크의 사용 예시
1. 권한 관리
💡 보통 권한은 4가지 이상으로 구분되어 있는 경우가 많습니다. 이때 각 권한을 비트로 표현하여 하나의 정수값으로 나타내면 매우 간편해집니다.
public static final int PERMISSION_READ = 1 << 0; // 0001
public static final int PERMISSION_WRITE = 1 << 1; // 0010
public static final int PERMISSION_DELETE = 1 << 2; // 0100
public static final int PERMISSION_EXECUTE = 1 << 3; // 1000
int userPermission = PERMISSION_READ | PERMISSION_WRITE; // 0011
int groupPermission = PERMISSION_READ | PERMISSION_EXECUTE; // 1001
boolean hasReadPermission = (userPermission & PERMISSION_READ) != 0; // true
boolean hasDeletePermission = (groupPermission & PERMISSION_DELETE) != 0; // false
2. 집합 관리
💡 집합을 비트로 표현하여 메모리를 절약할 수 있습니다. 예를 들어, 0부터 31까지의 정수 중에서 3, 5, 7번째 원소를 포함하는 집합을 나타내면 다음과 같이 표현할 수 있습니다.
💡 여러 상태를 하나의 정수 값으로 나타내어 관리할 수 있습니다. 예를 들어, 주어진 수가 2의 거듭제곱인지 여부를 판단할 때 다음과 같은 방법을 사용할 수 있습니다.
public static final int FLAG_POWER_OF_TWO = 1 << 0; // 0001
public static final int FLAG_NEGATIVE = 1 << 1; // 0010
int number = 8; // 2의 거듭제곱
int flags = 0;
if ((number & (number - 1)) == 0) { // 2의 거듭제곱인 경우
flags |= FLAG_POWER_OF_TWO;
}
if (number < 0) { // 음수인 경우
flags |= FLAG_NEGATIVE;
}
if ((flags & FLAG_POWER_OF_TWO) != 0) {
System.out.println(number + " is power of two");
}
if ((flags & FLAG_NEGATIVE) != 0) {
System.out.println(number + " is negative");
}
- 해결책으로 가는 도중에 막히게 되면 그 지점으로 다시 돌아가서 다른 경로를 탐색하는 방식을 의미합니다. 이를 통해 모든 가능한 경우의 수를 탐색하여 해결책을 찾습니다.
- 해당 알고리즘을 사용할때 주로 재귀함수를 사용하여 구현하며 스택을 이용하여서 사용하는 경우도 있습니다. - 재귀함수를 이용하는 경우 해결책을 찾기 위해 생성, 검사, 선택, 이동, 되돌아가기 등 과정이 재귀적으로 수행됩니다. - 스택을 이용하는 경우 이전 상태로 되돌아가기 위해 스택에 현재 상태를 저장하고, 되돌아갈 때 스택에서 상태를 꺼내오는 형태로 수행합니다.
[더 알아보기] 💡 완전 탐색에서 백트래킹이란?
- 모든 경우의 수를 탐색하여 최적의 결과를 찾아가는 완전탐색에서 백트래킹은 해결책을 찾아가는 도중에 막히게 되면 다시 돌아가서 다른 경로로 탐색을 하여 결국 모든 가능한 경우의 수를 탐색하여 해결책을 찾아가는 방식으로 사용됩니다.
💡 해당 기능은 factorial() 함수에 파라미터로 값을 넘길 경우 재귀함수로 반복하여 모든 경우의 수를 체크하여 결과값을 반환하는 함수입니다.
public class Main {
public static void main(String[] args) {
System.out.println(factorial(5));// 5! = 5 * 4 * 3 * 2 * 1 = 120
}
public static int factorial(int n) {
if (n == 0) {// 기본 케이스
return 1;
} else {// 재귀 케이스
return n * factorial(n - 1);
}
}
}
2. N 자연수의 합 계산 방법
💡 해당 기능은 sumNaturalNumber() 함수에 파라미터로 값을 넘길 경우 재귀함수를 반복하여 모든 경우의 수를 체크하여 결과값을 반환하는 함수입니다.
public class Main {
public static void main(String[] args) {
System.out.println(sumNaturalNumber(5));// 15
}
public static int sumNaturalNumber(int n) {
if (n == 1) {
return 1;
} else {
return n + sumNaturalNumber(n - 1);
}
}
}
3. 거듭제곱(pow) 계산
💡 해당 기능은 거듭제곱으로 base, exponent 값을 파라미터로 받아서 모든 경우의 수를 체크하여 결과값을 반환하는 함수입니다.
public class Main {
public static void main(String[] args) {
System.out.println(power(2, 5));// 15
}
public static int power(int base, int exponent) {
if (exponent == 0) {
return 1;
} else {
return base * power(base, exponent - 1);
}
}
}
7) 깊이 우선 탐색(DFS: Depth-First Search) / 너비 우선 탐색(Breadth-First Search: BFS)
💡 깊이 우선 탐색(DFS: Depth-First Search) / 너비 우선 탐색(Breadth-First Search: BFS)은 비 선형 구조에서 주로 사용되며 선형 구조에서는 큰 의미를 갖지 않습니다.
💡 깊이 우선 탐색(DFS: Depth-First Search) 이란?
- 루트 노드에서 시작하여 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법을 의미합니다. - 해당 방식은 자료구조의 ‘스택’을 이용하여서 구현할 수 있습니다.
💡 너비 우선 탐색(Breadth-First Search: BFS) 이란?
- 루트 노드에서 시작하여 인접한 노드를 먼저 탐색하는 방법을 의미합니다. - 해당 방식은 자료구조의 ‘큐’를 이용하여서 구현할 수 있습니다.
분류
깊이 우선 탐색(DFS)
너비 우선 탐색(BFS)
자료구조
스택
큐
탐색방식
깊이 우선
너비 우선
모든 경로 탐색
O
X
최단 경로 탐색
X
O
재귀 구현 가능
O
X
반복문 구현 가능
X
O
메모리 사용량
적음
많음
💡 [참고] 스택과 큐에 대한 정의를 알고 싶으시고 활용 방법에 대해 궁금하시면 아래의 링크를 참고하시면 도움이 됩니다.
