[알고리즘 이론] 6. 완전탐색

완전탐색

• 모든 경우의 수를 시도하여 정답을 찾는 방법이다.
• 무식하게 푼다는 의미로 Brute Force 라고도 한다.
• 상대적으로 간단하지만 경우의 수가 많아지면 시간이 길어지는 단점이 있다.

1. 단순 Brute-Force

• 특별한 기법 없이 for문과 if문으로 모든 경우의 수를 체크하여 답을 구함
• 이 방법으로 풀 수 있는 문제는 많지 않음

2. 비트마스크

• 각 원소를 두 가지 상태로 분류할 수 있을 때 사용
  • 모든 경우의 수에서 각각의 원소가 포함되거나 포함되지 않는 경우
  • 포함되면 1, 포함되지 않으면 0으로 구분한다 -> 2진수
• EX) 원소 n개인 집합의 부분집합 구하기
• 자세한 건 아래 게시글
• https://hoozy.tistory.com/entry/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EC%9D%B4%EB%A1%A0-8-%EB%B9%84%ED%8A%B8%EB%A7%88%EC%8A%A4%ED%82%B9

3. 재귀함수

• 재귀는 자기 자신을 호출한다는 뜻이다. -> 자기 함수 안에서 자기 함수를 다시 호출하는 작업을 수행한다.
• 호출된 함수 스택에 저장, 호출 완료시 스택에서 삭제
• for, while 같은 반복 코드를 간결하게 짤 수 있음
• 주의사항
  1. 사이클이 발생하면 안된다. -> 재귀 탈출 조건이 없는 경우 재귀함수는 계속하여 자기 자신을 호출하는 무한루프에 갇히고 스택 오버플로우가 일어난다.
  2. 재귀 탈출 조건을 적어주거나 재귀 발생 횟수를 적어줘야 한다.

4. 순열

• 서로 다른 n개를 일렬로 나열하는 경우의 수 (순서 o)
  • n!
• 서로 다른 n개중 r개를 뽑아 일렬로 나열하는 경우의 수 (순서 o)
  • n!/(r-1)! = nPr
• 시간 복잡도: O(n!)
  • 시간복잡도가 높은 편이라 n이 한자리 수 일경우일 때 고려
• c++에서는 함수가 있지만, 자바에서는 직접 구현해야 한다.
• 코드

public class PermutationMain {

    // 순열 구하기
    public static void Permutation(String[] arr, int stat, int end) {
        if(start == end) {
            for(String s : arr) {
                System.out.print(s+" ");
            }
            System.out.println();
        }
        else {
            for(int i = start; i <= end; i++) {
                swap(arr, start, i);
                Permutation(arr, start+1, end);
                swap(arr, start, i);'
            }
        }
     }

     // 인덱스 원소 바꾸기
     public static void swap(String[] arr, int a, int b) {
         String temp = arr[a];
        arr[a] = arr[b];
        arr[b] = temp;
     }

     // EX) arr = ["A", "B", "C"] 순열 출력
     public static void main(String[] args) {
         String[] arr = {"A", "B", "C"};
        Permutation(arr, 0, arr.length - 1);
     }
}

// 출력
A B C
A C B
B A C
B C A
C A B
C B A

5. BFS / DFS

• 자세한 건 게시글 참조.
• https://hoozy.tistory.com/entry/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EC%9D%B4%EB%A1%A0-4-DFS-BFS

알고리즘 문제 추천

1. 사탕 게임 (실버 2)

• https://www.acmicpc.net/problem/3085

2. 1, 2, 3 더하기 (실버 3)

• https://www.acmicpc.net/problem/9095

3. 가르침 (골드 4)

• https://www.acmicpc.net/problem/1062

4. 호석이 두 마리 치킨 (골드 5)

• https://www.acmicpc.net/problem/21278

참고 자료

https://velog.io/@suk13574/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EC%99%84%EC%A0%84%ED%83%90%EC%83%89