알고리즘 - 완전 검색

✔ 완전 검색(Exhaustive Search)

• 모든 경우의 수를 나열하여 확인하는 기법
  • Brute-force, Generate-and-Test 기법이라 불림.
  • 모든 경우의 수 테스트 후 최종 결과 도출.
    • 경우의 수가 많으면 오래 걸림.
  • 단순한 알고리즘으로 빠른 시간에 설계 가능.

1. 순열

• 순열(Permutation) : 서로 다른 n개의 원소 중 r개를 순서있이 골라낸 것.
  • $nPr = n \times (n-1) \times ... \times (n-r+1) (n >= r)$
  • 순서가 다르다면 다른 경우. (ex) 1, 2 와 2, 1은 다른 경우!!
  • 팩토리얼(Factorial) : $nPn = n!$

// 재귀를 통한 순열 : 1 ~ 3에서 3개를 선택하는 순열을 구하는 재귀.
int numbers[] = new int[3];
boolean isSelected[] = new boolean[4];

// 중복 미포함
void permutation(int cnt){
	if (cnt == 3)
  		순열 생성 완료
	else{
    	for (int i = 1; i <= 3; i++){
        	if (isSelcted[i] != true){
            	numbers[cnt] = i;
                isSelected[i] = true;
                permutation(cnt+1)
                isSelected[i] = false;
            }
        }
	}
}

// 중복 포함
vodi permutation2(int cnt){
	if (cnt == 3)
 		순열 생성 완료
    else
    	for(int i = 1; i <= 3; i++){
        	numbers[cnt] = i;
            permutation(cnt+1);
        }
}

• 중복 순열 : 서로 다른 것들 중 몇 개를 뽑아 나열하는 것. + 중복 가능.
  • 서로 다른 n개 중 r개를 택하는 순열(중복 가능) : $nπr = n * n * ... * n = n^r$

2. 조합

• 조합(Combination) : 서로 다른 n개의 원소 중 r개를 순서 없이 골라낸 것.
  • $nCr = {n! / {(n-r)!r!}} (n >= r)$
  • $nCr =$ n-1 $C$r-1 + n-1$C$r

// 재귀를 통한 조합
int input[] = new int[n];
int numbers[] = new int[r];

// 중복 미포함
combination(cnt, start){
	if (cnt == r){
    	조합 생성 완료
    }else{
    	for(int i = start; i < n; i++){
        	numbers[cnt] = input[i];
            combination(cnt+1, i+1);
        }
    }
}

// 중복 포함
combination2(cnt, start){
	if (cnt == r){
    	조합 생성 완료
    }else{
    	for(int i = start; i < n; i++){
        	numbers[cnt] = input[i];
            combination2(cnt+1, i);
        }
    }
}

3. 부분 집합

• 부분 집합(Power Set) : 집합에 포함된 원소들을 선택하는 것.
  • 다수의 중요 알고리즘들이 원소들의 그룹에서 최적의 부분 집합을 찾는 것.
    • (ex) 배낭 짐싸기(knapsack)
  • 부분 집합의 수 : 원소 n개 -> 공집합 포함 $2^n$개.
    • 원소의 수가 증가하면 부분 집합의 수는 지수적 으로 증가

◾재귀를 통한 부분 집합

• 재귀를 통한 부분 집합 : 각 원소의 포함/비포함의 형태로 재귀적 구현.
  • 반복으로도 생성할 수 있지만, 선택하는 원소의 수만큼 중첩 반복문 작성이 필수.
  • 중첩 반복문은 복잡해지기 쉬우므로 재귀를 통해 작성하는 것이 대부분.

// 재귀를 통한 부분 집합
int input[];	// 숫자 배열
boolean isSelected[];	//부분 집합에 포함/비포함 여부

generateSubSet(int cnt){
	if(cnt == N)
    	부분집합 완성
    else{
    	// 해당 수 포함하고 부분 집합 생성
    	isSelected[cnt] = true
        generateSubSet(cnt+1)
        // 해당 수 포함하지 않고 부분 집합 생성
        isSelected[cnt] = false
        generateSubSet(cnt+1)
    }
}

◾사전적 순서(Lexicographical Order) 부분 집합

• 바이너리 카운팅(Binary COunting)을 통한 사전적 순서 부분 집합
  • 원소 수에 해당하는 N개의 비트열 이용.
  • n번째 비트값이 1이면 n번째 원소가 포함되었음을 의미.

✅ 조건 판단: And(&)
✅ 비트 누적: Or(|)
✅ 특정 위치 비트를 선택: Shift(1<<i)

• 3개의 원소에 대한 부분 집합 예시

  10진수	이진수	{A, B, C}
  0	000	{}
  1	001	{A}
  2	010	{B}
  3	011	{B, A}
  4	100	{C}
  5	101	{C, A}
  6	110	{C, B}
  7	111	{C, B, A}

// 바이너리 카운팅을 통한 부분 집합 생성
int arr[] = {1, 2, 3}
int n = arr.length;

for(int i = 0; i < (1 << n); i++){
	for(int j = 0; j < n; j++){
    	if((i & (1 << j)) != 0){
        	System.out.println(arr[j] + " ");
        }
    }
    System.out.println();
}