ComputerScience/알고리즘
브루트 포스
slown
2025. 1. 4. 22:07
목차
1.브루트 포스?
2.브루트 포스의 장단점
3.브루트 포스의 종류 및 예제
1.브루트 포스?
브루트 포스(brute Force)는 "완전 탐색" 기법으로도 불리며, 가능한 모든 경우의 수를 전부 탐색하여 문제의 답을 찾는 알고리즘 설계 방식입니다. 직관적이고 간단하게 구현할 수 있지만, 시간 복잡도가 높아 성능이 좋지 않을 수 있습니다.
2.브루트 포스의 장단점
브루트포스의 장점
- 알고리즘을 설계하고 구현하기 쉽다
- 모든 경우의 수를 탐색하기 때문에 100% 정확성을 보장한다.
브루트포스의 단점
- 메모리 효율면에서 매우 비효율적이다.
- 알고리즘의 실행 시간이 매우 오래걸린다. (시간복잡도가 높다)
3.브루트 포스의 종류 및 예제
브루트 포스의 종류를 보자면 다음과 같습니다.
- 선형 구조 : 순차 탐색
- 비선형 구조 : 백트래킹, DFS, BFS
그리고 대표적인 예제는 다음과 같습니다.
1. 비밀번호 크래킹
모든 가능한 비밀번호 조합을 시도하여 올바른 비밀번호를 찾는 방식.
public class BruteForceCracking {
private static final String TARGET_PASSWORD = "abc";
public static void main(String[] args) {
char[] charset = "abcdefghijklmnopqrstuvwxyz".toCharArray(); // 사용 가능한 문자 집합
int maxLength = 3; // 비밀번호 최대 길이
crackPassword(charset, maxLength, "");
}
// Brute force로 비밀번호를 생성하고 비교
public static void crackPassword(char[] charset, int maxLength, String current) {
if (current.length() > maxLength) {
return;
}
// 목표 비밀번호와 비교
if (current.equals(TARGET_PASSWORD)) {
System.out.println("Password found: " + current);
System.exit(0); // 프로그램 종료
}
// 가능한 모든 문자 조합 생성
for (char c : charset) {
crackPassword(charset, maxLength, current + c);
}
}
}2. 순열 생성
nn개의 숫자 또는 문자에서 가능한 모든 순열을 생성하는 경우.
import java.util.ArrayList;
import java.util.List;
public class PermutationGenerator {
public static void main(String[] args) {
int[] numbers = {1, 2, 3};
List<List<Integer>> permutations = new ArrayList<>();
generatePermutations(numbers, new ArrayList<>(), permutations);
// 결과 출력
System.out.println("All permutations:");
for (List<Integer> permutation : permutations) {
System.out.println(permutation);
}
}
// 순열 생성 함수
public static void generatePermutations(int[] nums, List<Integer> current, List<List<Integer>> result) {
if (current.size() == nums.length) {
result.add(new ArrayList<>(current));
return;
}
for (int num : nums) {
if (current.contains(num)) { // 중복 방지
continue;
}
current.add(num); // 숫자 추가
generatePermutations(nums, current, result);
current.remove(current.size() - 1); // 되돌리기
}
}
}
3. 배열에서 두 수의 합 찾기
배열에서 두 수의 합이 특정 값이 되는 쌍을 찾는 문제
public class FindPair {
public static void main(String[] args) {
int[] nums = {2, 7, 11, 15};
int target = 9;
int[] result = findPair(nums, target);
if (result != null) {
System.out.println("Pair found: (" + result[0] + ", " + result[1] + ")");
} else {
System.out.println("No pair found.");
}
}
public static int[] findPair(int[] nums, int target) {
for (int i = 0; i < nums.length; i++) {
for (int j = i + 1; j < nums.length; j++) {
if (nums[i] + nums[j] == target) {
return new int[]{nums[i], nums[j]}; // 합이 target인 두 숫자 리턴
}
}
}
return null; // 합이 target인 두 숫자가 없는 경우
}
}
참고 문서