브루트 포스

목차

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. 순열 생성

nnn개의 숫자 또는 문자에서 가능한 모든 순열을 생성하는 경우.

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인 두 숫자가 없는 경우
    }
}

 

참고 문서

https://velog.io/@limchard/Algorithm-%EC%A0%84%EC%B2%B4%ED%83%90%EC%83%89-%EB%B8%8C%EB%A3%A8%ED%8A%B8%ED%8F%AC%EC%8A%A4-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-Brute-Force-Algorithm#%EB%B8%8C%EB%A3%A8%ED%8A%B8-%ED%8F%AC%EC%8A%A4%EC%9D%98-%EC%A2%85%EB%A5%98