Advanced Brute-Force

1. Brute-Force Algorithms이란, 

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

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

예를 들어, 

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

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

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

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

2. Advanced Brute-Force Algorithms

예를 들어, 

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; //초기화
            }
         }
     }
 }          

이런식이 된다. 이 form을 잘 기억해두는게 좋다. 왜냐면 알고리즘 (Toy)문제 풀면서 이 알고리즘을 사용해야하는 경우가 매우 많았기 때문이다. 

r(변하는 값) 중 for문이 필요한 Brute-Force 문제인 경우 => 재귀호출을 이용해야 했던 Toy문제들

(문제 본문은 <더보기>를 클릭!)

 

1) rockPaperScissors 문제

결과는 다음세 판의 가위바위보를 할 동안 낼 수 있는 모든 경우의 수를 return하는 함수를 작성하세요. 

* [["rock", "rock", "rock"],

* ["rock", "rock", "paper"],

* ["rock", "rock", "scissors"],

* ["rock", "paper", "rock"],

* ...etc ...

* ]과 같을 것입니다.

 

* Advanced:

* 변수로 전달하는 판수에 맞는 정답을 return 하도록 작성한 함수를 바꿔 보세요.

* rockPaperScissors(5); // => [['rock', 'rock', 'rock', 'rock', 'rock'], etc...]

 세 판 정도면 엄청 헷갈리겠지만 3중 for문과 많은 if문으로 구현할 "수도"있을 거이다. 

그러나 num이 변하는 수라면? 어쩔ㄹ땐 5판이고 어쩔 땐 4판일때의 결과를 구해야한다면? for문으론 안된다. 

그런데 생각해보면 순열구하기와 같은ㄴ 문ㄴ제 안닌가? rock, paper, scissor가 그냥 숫자일 때 순열구하기 문제와 동일하다. 

즉, 이 문제도 Advanced Brute Force에서 예시로 든 큰 틀을 벗언나지 않고, 재귀호출과 적절한 초기화를 통해 구현할 수 있다. 

const rockPaperScissors = function (num) {
  // TODO: Your code here!

  let status = ['rock', 'paper', 'scissors']
  let allCases = []
  let arr = []

  if (num === undefined) {
    num = 3
  }
  function Recursive(currnum) {
    if (currnum >= num) {
      allCases.push(arr.slice())
    } else {
      for (let i = 0; i < status.length; i++) {
        arr.push(status[i])
        Recursive(currnum + 1)
        arr.pop(status[i])
      }
    }
    return
  }

  Recursive(0)

  return allCases
}

2) powerSet문제

/*

 * 주어진 문자열의 'power set'으로 이루어진 배열을 return하는 함수를 작성하세요.

 *

 * power set이란?

 * 비어있는 집합을 포함한 모든 부분집합(subset)의 모음.

 *

 * 예시 :

 *

 * powerSet("abc")

 * -> [ '' , 'a', 'b', 'c', 'ab', 'ac', 'bc', 'abc' ]

 *

 * 참고 :

 *  1. 모든 부분집합의 문자들은 알파벳 순서로 정렬되어야 합니다.

 *  2. 같은 문자로 이루어진 부분집합은 순서와 무관하게 하나로 인식합니다. ('ab'와 'ba'는 같습니다.)

 *

 * 예시 2 :

 *

 * powerSet("jump")

 * -> ["", "j", "ju", "jm", "jp", "jmu", "jmp", "jpu", "jmpu", "u", "m", "p", "mu", "mp", "pu", "mpu"]

 */

const powerSet = function(str) {
  // TODO: Your code here!
  let result = [''];
  let subset = '';
  let check = {};

  function makeSubset(){
    //기저조건: 문자열에 있는 알파벳 모두 다 넣었을 때
    if(subset.length >= str.length){
      return;
    }
    // 재귀
    for(let i=0; i<str.length; i++){
      if(!check[str[i]]||check[str[i]]===false){//1. 아직 subset에 안들어간 알파벳이면
        subset += str[i];//2. 넣고
        check[str[i]] = true;//3. 썼다고 표시해주고(중복으로 들어가면 안되니까)=> 같은 문자로 이루어진 부분집합은 순서와 무관하게 하나로 인식합니다. ('ab'와 'ba'는 같습니다.) 만족

        let sortSubset = subset.split('').sort().join(''); // => 모든 부분집합의 문자들은 알파벳 순서로 정렬되어야 합니다. 만족
        if(result.indexOf(sortSubset)=== -1){ //3은 jjum 와 같은 알파벳 중복을 막아 준 것이고 이 코드는 jmup와 jpum 같은 중복을 없애기 위한 것읻다. 
          result.push(sortSubset);
        }
        
        makeSubset();//4. 재귀 들어가서 그 뒤에 알파벳 덧붙이고

        subset = subset.slice(0, -1) //5-1. 재귀 빠져나오면 원래대로 제자리 //.slice가 immutable이기때문에 그냥 subset에 대입시켜서 원본을 바꿔줘야한다. 
        check[str[i]] = false; //5-2. 초기화
      }
    }
  }

  makeSubset();
  
  
  return result; 
};

3) telephoneWord 문제

/*

 * Each number key on a standard phone keypad has a set of Latin letters written on

 * it as well: http://en.wikipedia.org/wiki/File:Telephone-keypad2.svg

 *

 * Businesses often try to come up with clever ways to spell out their phone number

 * in advertisements to make it more memorable. But there are a lot of combinations!

 *

 * Write a function that takes up to four digits of a phone number, and

 * returns a list of all of the words that can be written on the phone with

 * that number. (You should return all permutations, not only English words.)

 *

 * Example:

 *   telephoneWords('2745');

 *   => ['APGJ',

 *        'APGK',

 *        'APGL',

 *        ..., // many many more of these

 *        'CSIL']

 *

 * Tips:

 *   - Phone numbers are strings! (A phone number can start with a zero.)

 *   - The digits 0 and 1 do not have letters associated with them, so they should be left as numbers.

 *   - Don't return every combination of those digits in any order, just the order given.

 *

 *  Extra credit: There's a list of English dictionary words at /usr/share/dict/words .

 *  Why not filter your results to only return words contained in that file?

 *

 */

var phoneDigitsToLetters = {
  0: '0',
  1: '1',
  2: 'ABC',
  3: 'DEF',
  4: 'GHI',
  5: 'JKL',
  6: 'MNO',
  7: 'PQRS',
  8: 'TUV',
  9: 'WXYZ',
}

var telephoneWords = function (digitString) {
  // TODO: return every combination that can be spelled on a phone with these digits
  let resultArray = []
  let result = ''

  function makeLetters(index) {
    if (index >= digitString.length) {
      resultArray.push(result)
      return
    }
    let currDigit = digitString[index]
    for (let j = 0; j < phoneDigitsToLetters[currDigit].length; j++) {
      result += phoneDigitsToLetters[currDigit][j]
      makeLetters(index + 1)
      result = result.slice(0, -1)
    }
  }

  makeLetters(0)
  return resultArray
}

이 Toy 문제들 다 "순열구하기"와 맥락이 같쥬!

 

3. BackTracking

더 나아가 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;
}

 

지금까지 다- 탐색하는데 필요한 3가지 알고리즘에 대해 정리해 보았다.

아래는 알고리즘 공부필기본이다.

 

꼭 백지코딩으로 복습해보자! (이것 모두 나 자신에게 하는 말 입니더..)