[묘공단] 완전 탐색이란?

알고리즘 기법 중 완전 탐색(Exhaustive Search)이란 것이 있다.

이름만 들어도 '전부 다 보는 기법' 뭐 이런 것이겠거니 유추가 되지 않는가?

 

그런데 완전 탐색에도 종류가 있다.

1. 브루트 포스(Brute Force): 가능한 모든 경우를 시도하는 방법이다. 비밀번호 해킹 같은 주제에서 듣기 쉽다.

2. 백트래킹(Backtracking): 가능한 모든 경우를 시도하되, 불필요한 경우를 미리 제거해 효율을 높이는 방법이다. 주로 재귀적으로 사용되며 유망하지 않은 경로는 더 이상 탐색하지 않는 식이다.

3. 재귀(Recursion): 문제를 여러 작은 문제로 나누어 푸는 방식이다. 재귀적으로 모든 가능한 경우를 시도한다.

4. 순열과 조합(Permutations and Combinations): 가능한 모든 순열이나 조합을 생성해서 문제를 해결하는 식이다.

---

완전 탐색은 일반적으로 문제의 크기가 작을 때 사용한다.

큰 문제에 이 방법을 적용하면 시간 복잡도가 급격히 늘어서 비효율적이다.

코테 통과를 못 할 거다.

 

다음과 같은 케이스에는 완전 탐색부터 고려하는 게 좋을 거 같다.

• 순열 생성: 주어진 숫자나 문자의 모든 순열을 생성하는 문제.
• N-Queen 문제: N x N 체스판에 N개의 퀸을 서로 공격할 수 없도록 배치하는 문제.
• 부분집합 합 문제: 주어진 숫자 집합에서 특정 합을 가지는 모든 부분집합을 찾는 문제. <- 코테 저레벨에서 자주 나온다.

더 나아가기 전에 단어 정리 한 번 하고 가자.

순열이란?

순열이란 주어진 집합의 원소들을 순서를 고려하여 배열하는 방법입니다. 예를 들어, 집합 {A, B, C}의 모든 순열은 다음과 같습니다:

• ABC
• ACB
• BAC
• BCA
• CAB
• CBA

즉, 순열은 n개의 원소를 가지는 집합에서 원소들의 순서가 바뀐 모든 가능한 경우를 의미합니다.

조합이란?

조합이란 주어진 집합에서 순서를 고려하지 않고 특정 개수의 원소를 선택하는 방법입니다. 즉, 순서는 중요하지 않으며, 선택된 원소의 집합만 중요합니다.

예시

집합 {A, B, C}에서 2개의 원소를 선택하는 모든 조합은 다음과 같습니다:

• AB
• AC
• BC

여기서 순서가 중요하지 않기 때문에, AB와 BA는 같은 조합으로 취급됩니다.

N-Queen 문제란?

N-Queen 문제는 N x N 크기의 체스판에 N개의 퀸을 서로 공격할 수 없도록 배치하는 문제입니다.

퀸은 체스 말 중 하나로, 같은 행, 같은 열, 대각선 상에 있는 모든 말들을 공격할 수 있습니다.

따라서, N개의 퀸이 서로 공격하지 않도록 배치하려면, 어떤 퀸도 다른 퀸과 같은 행, 같은 열, 또는 대각선 상에 위치할 수 없습니다.

내가 완전 탐색을 리서치하게 된 이유는,

https://school.programmers.co.kr/learn/courses/30/lessons/42842

프로그래머스

이 문제 때문이다.

 

이 문제를 완전 탐색으로 어떻게 풀 것인가?

어떻게 푸는 게 잘 푸는 것인가?

class Solution {
    public int[] solution(int brown, int yellow) {
        return findDivisors(yellow, brown);
    }
    private int[] findDivisors(int n, int brown) {
        int a = 0, b = 0;
        for(int i=1; i<=i*i; i++) {
            if(n % i == 0) {
                a = i;
                b = n / i;
                // a가 가로
                if(a >= b && brown == a * 2 + b * 2 + 4) {
                    return new int[]{a+2, b+2};
                } else if(b > a && brown == a * 2 + b * 2 + 4) {
                    return new int[]{b+2, a+2};
                }
            }
        }
        return new int[]{-1};
    }
}

 

딱히 알고리즘에 대한 고민 없이 풀었는데 아직 문제가 쉬워서 이런 방식으로도 풀리는 것 같다.

완전 탐색을 적용하기 더 좋은 문제가 있으면 그때 다시 정리해야겠다.

 

골든래빗 출판사의 묘공단 스터디를 진행하며

코딩 테스트 합격자 되기 - 자바 편 프로그래머스 제공 97 문제로 완벽 대비를 읽고 정리한 내용입니다.