11. Algorithms - Advanced Brute Force

Brute-Force Algorithms이란, 

완전 탐색 알고리즘으로 모든 경우를 시도해봄으로써 답을 구한는 알고리즘이다. 

완전 탐색을 하기에 간단한 경우는 모든 경우를 얼마나 돌아야 하는지 알고 있을 때이다.

 

1. 예를 들어, 

N개의 숫자 중에서 최소값을 구하라 는 문제가 있고, N가 N개의 숫자가 입력으로 주어진다면

mini = arr[0]
for(let i=0; i<arr.length; i++){
	if(mini > arr[i]){
    	mini = arr[i];
    }
}

로 단순히 하나하나 모든 숫자를 비교할 수 있을 것이다. 

그러나 이런 경우가 아닌 문제가 까다로운 것이다. 

 

2. 예를 들어, 

N개의 알파벳 중에서 r개를 나열할 수 있는 경우를 모두 출력하시오

와 같은 문제라면, r이 달라짐에 따라서 반복문을 써야 하는 횟수도 r 번으로 달라진다. 

이처럼 r(변하는 값) 중 for문이 필요한 Brute-Force 문제인 경우 => 재귀호출을 이용해야 한다. 

 

재귀호출을 사용해서 이 예시를 풀어보면

let n, r;
let result = []
let check = []

function getResult(x){
	//getResult(x): x번째 for문을 실행시키게 하는 함수
    
    //기저조건: r번째 for문을 돌렸다면 이제 다 돌렸다는 거니까 끝. 출력
    if(x>=r){ 
    	console.log(result);
    }
    //아니면 재귀 호출
    else{
    	for(let i=0; i<n; i++){
        	if(check[i] === false){//i 아직 안넣었으니 쓰고
            	result[x] = i; // 넣어주고
                check[i] = true; // 넣어줬다고 표시
                
                getRessult(x+1); // 재귀호출
                
                result[x] = 0; // 초기화
                check[i] = false; //초기화
            }
         }
     }
 }          

 

더 나아가 BackTracking은 

 ‘유망한 노드들만 검사하고, 유먕하지 않다면 부모 노드로 돌아가 탐색을 계속한다’이다. 

 

예시1) 순열 구하기

문제

서로 다른 n개의 원소들 중에서 r개만을 뽑아 일렬로 나열하는 것을 순열이라 한다. 예를 들어, 3개의 원소 a, b, c 중에서 2개만을 뽑아 나열하면 ab, ac, ba, bc, ca, cb 의 6가지 경우가 있다. n과 r이 주어질 때, n개의 소문자 중에서 r개만을 뽑아 나열하는 모든 경우를 출력하는 프로그램을 작성하시오. 단, a부터 시작하여 연속으로 n개의 알파벳을 갖고 있다고 하자.

​

입력

첫 번째 줄에 n과 r이 주어진다. ( 1 ≤ n ≤ 10, 0 ≤ r ≤ min(n, 7) )

​

출력

각 줄에 n개의 소문자 중에서 r개만을 뽑아 나열하는 경우를 사전순으로 나열한 결과를 출력한다.

#include <stdio.h>

int n, r;
int check[20];
char arr[20];

void getResult(int inx){
  if(int inx >= r)
    printf("%s\n", arr);

  else{
    for(int i=0; i<n; i++){
      if(check[i] == 0){
        arr[inx] = i+'a';
        check[i] = 1;
        getResult(inx+1);
        check[i] = 0;
      }
    }
  }

}

int main() {

  //Please Enter Your Code Here
  scanf("%d %d", &n, &r);
  getResult(0);

  return 0;
}

예시2) Tobin(이진패턴)

문제

두 정수 n, k를 입력받아 k개의 1을 가진 n자리 이진 패턴을 출력하는 프로그램을 작성하세요.

​

입력

두 정수 n,k가 입력으로 주어진다. ( 0< n <= 30, 0 <= k < 8 , n>=k )

​

출력

결과를 내림차순으로 출력한다.

​

문제 풀이 idea

1. 함수의 역할을 말로 정확하게 정의한다. => getResult(num, len): num개의 1을 가지 len 자리수에 이진패턴을 만들기 위해 0, 1 을 넣을지 결정하고, 넣어야하면 넣고, 정답이면 출력하고, 아니면 버리는 함수
2. 기저조건(탈출구)에서 함수가 제대로 동작함을 보인다.  => 기저조건을 정할 때, 여기서 중요한 것은 '굳이 계속 진행해 봤자 정답이 안 나올게 뻔한 곳으로는 가지 않는 것'이다. 그래서

    1) 만약 len이 n과 같거나(크면), 

          1-1) num이 k개이면 정답 -> 출력

          1-2) num이 k개가 아니면 -> 길이가 다 되었는데도 1의 개수가 충족이 안 되었으므로 정답이 아님 -> 버려

    2) len이 n보다 작을 때

          2-1) num이 k개이면 그 뒤는 어짜피 다 0이면 되니까 재귀호출 그만하고 그 뒤는 0으로 다 채운 뒤 -> 출력

          2-2) num이 k개가 아니면 -> 이때는 k보다 작을 때이므로 그제서야 재귀호출을 더 진행해봐야 한다. -> 3번

3. 함수가 그보다 작은 input에서 제대로 동작한다고 가정하고 함수를 완성한다. => 내림차순이니까, result[len]에 1 먼저 넣고, num++, len++ 해서 다음 재귀호출, result[len]에 0넣고 len++해서 다음 재귀호출

#include <stdio.h>
int n, k;
int arr[40];

void Tobin(int len, int one){
  if(len>=n){
    if(one == k){
      for(int i=0; i<n; i++){
        printf("%d", arr[i]);
      }printf("\n");
    }
    else
      return;
  }
  else{//len<n
    if(one >= k){
      for(int i=0; i<n; i++){
        printf("%d", arr[i]);
      }printf("\n");
    }
    else{//one<n
      arr[len]=1;
      Tobin(len+1, one+1);
      arr[len]=0;
      Tobin(len+1, one);
    }
  }
}

int main() {

  //Please Enter Your Code Here
  scanf("%d %d", &n, &k);
  Tobin(0, 0);

  return 0;
}