완전탐색, 순열

---

완전 탐색(검색) 이란 모든 경우의 수를 테스트한 후, 최종 해법을 도출하는 것이다.

brute-force 혹은 generate-and-test 기법이라고도 불리운다.

---

특징

 

• 모든 경우의 수를 테스트한 후, 최종 해법을 도출한다.
• 상대적으로 빠른시간에 알고리즘을 설계 할 수 있다.
• 일반적으로 경우의 수가 상대적으로 작을 때 유용
• 모든 경우의 수를 생성하고 테스트하기 때문에 수행 속도는 느리지만, 해답을 찾아내지 못할 확률 이 작다.

---

완전 탐색 (순열)

 

• 서로 다른 것들 중 몇개를 뽑아서 한 줄로 나열하는 것
• 서로 다른 n개 중 r개를 택하는 순열은 아래와 같인 표현한다.
  • nPr
• 그리고 nPr은 다음과 같은 식이 성립한다
  • nPr = n * (n-1)+(n-2) * … *(n-r+1)

 

{1, 2, 3}을 포함하는 모든 순열을 생성

=> 재귀, 백트랙킹을 이용한 완전탐색

 

< 예시 코드 >

public class PermutationExample {

    public static void main(String[] args) {
        int[] array = {1, 2, 3};
        generatePermutations(array, 0, array.length - 1);
    }

    // 순열을 생성하는 재귀 함수
    public static void generatePermutations(int[] array, int start, int end) {
        if (start == end) {
            // 배열의 끝에 도달하면 순열 출력
            printArray(array);
        } else {
            for (int i = start; i <= end; i++) {
                // 현재 요소와 다음 요소를 교환
                swap(array, start, i);
                
                // 다음 요소로 이동하여 재귀 호출
                generatePermutations(array, start + 1, end);
                
                // 원래 상태로 돌려놓음 (백트래킹)
                swap(array, start, i);
            }
        }
    }

    // 배열 요소를 출력하는 유틸리티 메서드
    public static void printArray(int[] array) {
        for (int num : array) {
            System.out.print(num + " ");
        }
        System.out.println();
    }

    // 배열에서 두 요소의 위치를 바꾸는 메서드
    public static void swap(int[] array, int i, int j) {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }
}

 

< 출력값 >

1 2 3 
1 3 2 
2 1 3 
2 3 1 
3 2 1 
3 1 2

 

generatePermutations() 메서드 호출 과정

 

※ 첫번째 호출 - start = 0; end = 2

• i = 0 일때
  • swap( {1, 2 , 3} , 0, 0)을 통해 배열은 {1, 2, 3} 반환
  • generatePermutations( {1, 2, 3} , 1, 2)  재귀 호출
• i = 1 일떄
  • swap( {1, 2 , 3} , 0, 1)을 통해 배열은 {2, 1, 3} 반환
  • generatePermutations( {2, 1, 3} , 1, 2)  재귀 호출
• i = 2 일떄
  • swap( {1, 2 , 3} , 0, 3)을 통해 배열은 {3, 2, 1} 반환
  • generatePermutations( {3, 2, 1} , 1, 2)  재귀 호출

 

※ 두번째 호출 - start = 1, end = 2

• i = 1 일떄
  • swap( {2, 1 , 3} , 1, 1)을 통해 배열은 {2, 1, 3} 반환
  • generatePermutations( {2, 1, 3} , 2, 2)  재귀 호출
• i = 2 일떄
  • swap( {2, 1 , 3} , 1, 2)을 통해 배열은 {2, 3, 1} 반환
  • generatePermutations( {2, 3, 1} , 2, 2)  재귀 호출

 

※ 세번째 호출 - start = 2, end = 2

• i = 2 일떄
  • swap( {2, 3 , 1} , 2, 2)을 통해 배열은 {2, 3, 1} 반환
  • 순열 출력 2 3 1

 

위의 과정 반복하여 모든 순열 생성