[알고리즘] 완전 탐색이란?

완전 탐색이란?

완전 탐색이란 말 그대로 모든 경우의 수를 다 만들어보고 답을 찾는 방법이다.
만약 자물쇠의 비밀번호가 3자리라면 000 ~ 999까지 최대 1000번의 경우의 수를 만들어 정답을 찾을 것이다.
이러한 완전 탐색 방법은 최적의 해를 찾을 수는 있지만 시간 복잡도와 공간 복잡도가 너무 커서 입력 값이 작을 때 주로 사용한다.

완전 탐색 종류

완전 탐색은 아래 사진과 같이 7가지 알고리즘이 존재한다.

브루트 포스(Brute Force)

발생할 수 있는 모든 경우를 탐색하는 방법이다.
시간 복잡도가 매우 커질 수 있기 때문에 주로 가능한 경우가 적고 완전 탐색으로 충분히 빠르게 해결할 수 있는 기초적인 문제에서 사용한다.
주로 반복문과 조건문으로 모든 경우를 탐색하거나 재귀를 이용하여 구현한다.

반복문

• 아래 코드는 반복문을 이용하여 숫자 1부터 n까지의 합을 계산하는 예시 코드이다.

public class BruteForceLoop {
    public static void main(String[] args) {
        int n = 3; // 예시로 3을 사용
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                System.out.println("(" + i + ", " + j + ")");
            }
        }
    }
}

• 출력 결과
• (1, 1) (1, 2) (1, 3) (2, 1) (2, 2) (2, 3) (3, 1) (3, 2) (3, 3)

재귀

• 아래 코드는 숫자 1부터 n까지의 합을 재귀를 이용하여 계산하는 예시 코드이다.

public class SimpleRecursion {
    public static void main(String[] args) {
        int n = 5; // 예시로 5를 사용
        int result = sum(n);
        System.out.println("Sum of 1 to " + n + " is: " + result);
    }

    public static int sum(int n) {
        if (n == 1) {
            return 1;
        }
        return n + sum(n - 1);
    }
}

• 호출 순서

sum(5): 5 + sum(4)
sum(4): 4 + sum(3)
sum(3): 3 + sum(2)
sum(2): 2 + sum(1)
sum(1): 1

• 출력 결과

Sum of 1 to 5 is: 15

비트마스크

 

백트레킹(Backtracking)

백트레킹이란 해를 찾는 도중에 해가 될 수 없다 판단되면 이전으로 되돌아가서 새로운 경로를 찾는 방식이다.
백트레킹에서 핵심 Key는 더 이상 탐색할 필요가 없는 상태를 제외하는 것이고 이것을 가지치기라고 한다.
가지치기를 통해 반복분의 횟수를 줄일 수 있어서 효율적이지만 최악의 경우에는 완전 탐색을 하기 때문에 백트레킹에서는 가지치기가 매우 중요하다.

순열 탐색

고등학교 확률과 통계에서 배운 순열 개념을 이용한 완전 탐색 방법이다.

순열이란
서로 다른 n개 중 r개를 선택하는 경우의 수 (nPr)
ex. arr = [1, 2, 3] 일 때 2자리 숫자를 만드는 경우의 수 - 3P2 = 3[(1,2), (1,3), (2,3)]

• 순열에 원소들을 하나씩 채워가는 방식
  • 중첩 for문 or 재귀로 구현 가능
• 시간 복잡도가 O(n!)이므로 n의 값이 매우 작을 때만 사용 가능하다.

swap을 이용한 순열 구현

• 배열에서 두 요소의 위치를 바꿔가며 모든 경우의 수를 구하는 방식이다.
• 인덱스 0부터 다음 인덱스와 위치를 바꾸는 작업을 마지막 인덱스까지 반복하며 모든 경우를 구한다.
• A, B, C 세 요소가 있을 때 특정 값을 고정 시키고 나머지 값들을 교환하면서 새로운 경우의 수를 구한다.

visited 배열을 이용한 순열 구현

• 현재 인덱스의 값을 선택한 후 해당 인덱스를 visited[] 배열에 넣는다. [1, 0, 0]
• visited[] 배열에서 체크되지 않은 가장 작은 인덱스를 선택하여 visited[] 배열에 넣는다.
  • 1회전: [1, 2, 0]
  • 2회전: [1, 2, 3]
  • 이 과정을 마지막 인덱스까지 반복한다.
    즉, 한 loop 내에서(depth) 작은 인덱스부터 visited가 아니라면 visited[] 배열에 넣는다.

visited 배열을 이용한 방식은 swap을 이용한 방식보다 효율적이다.

재귀 함수(Recursion Function)

함수 내부에서 자기 자신을 호출하는 함수를 의미한다.

• 예시 코드
  • 주어진 숫자 n까지의 합을 계산하는 재귀 함수
  • sum() 함수 내부에서 sum() 함수를 호출하는 방식

public class SimpleRecursion {
    public static void main(String[] args) {
        int n = 5; // 예시로 5를 사용
        int result = sum(n);
        System.out.println("Sum of 1 to " + n + " is: " + result);
    }

    // n까지의 합을 계산하는 재귀 함수
    public static int sum(int n) {
        if (n == 1) {
            return 1;
        }
        return n + sum(n - 1);
    }
}

DFS, BFS

DFS와 BFS는 뒤에서 자세히 설명할 것이기 때문에 간단하게만 설명하겠다.

DFS(Depth-First Search): 깊이 우선 탐색

한 방향으로 갈 수 있을 때까지 가다가 막히면 이전 노드로 돌아와서(백트레킹) 새로운 길을 찾는 방법이다.

• 모든 노드를 탐색해야 하는 경우 사용
• BFS보다 구현이 간단함
• 모든 노드를 탐색하기 때문에 BFS보다는 탐색 속도가 느림
• 미로 찾기 문제에서 사용(최단 경로는 BFS)

DFS의 한계

DFS의 단점은 크게 2가지 존재

1. 연산 횟수 기하급수적 증가

DFS는 가능한 모든 경우의 수를 탐색한다.
때문에 미로의 크기가 커지면 커질 수록 연산 횟수는 기하급수적으로 커진다.

• 예를 들어 갈 수 있는 길이 3가지 모두 존재하는 갈림길이 3개 있다고 가정해보자.

1		1	1	1	1	1
1		1		1		1
1	1	1	1	1	1	1	1	1
		1		1		1		1
		1	1	1	1	1		👑

3가지 가능한 경우가 존재하는 갈림길이 3개 존재한다.
따라서, 갈림길에서 선택할 수 있는 경우의 수는 3^3가지이다.
그런데 만약 갈림길이 1000개라면 경우의 수는 3^1000으로 기하급수적으로 늘어난다.

2. 최단 거리 보장 X

상, 하, 좌, 우의 우선순위를 미리 정해서 탐색한다.
이때 우선순위를 어떻게 정하느냐에 따라서 거리가 달라지기 때문에 항상 최단거리를 보장하지 못한다.
따라서, 최단 거리를 찾기 위해서는 DFS보다 BFS를사용한다.

BFS(Breadth-First Search): 너비 우선 탐색

루트 노드에서 시작해서 인접한 노드들을 탐색하는 방법으로 시작 정점에서 가장 가까운 노드부터 방문하고 가장 먼 노드는 가장 마지막에 방문하는 방법이다.

• 최단 경로 문제에서 주로 사용

BFS 한계

BFS의 한계는 크게 2가지 존재

1. DFS에 비해 큰 저장공간 필요

DFS는 한 길만 쭉 파다 돌아와서 다시 다른 길을 파기 떄문에 저장 공간은 크게 필요하지 않다. 하지만 BFS는 다음 탐색할 노드를 동시에 여러 개 저장하기 때문에 갈림길이 많을 수록 유망하지 않은 노드 모두 저장하기 때문에 큰 저장공간이 필요하다.

2. 규모가 클 경우 비효율적

DFS는 규모가 크더라도 최선의 경우에는 어떤 경로 하나에서만 도착하기만 하면 종료한다. 하지만 BFS는 동시에 여러 경로를 탐색해야 하기 때문에 프로그램 실행 시간이 오래 걸린다는 단점이 있다.

출처

https://adjh54.tistory.com/196

• 순열
  https://choo.oopy.io/651eb670-9136-43e8-ad8d-7cdd65225cc1