오늘

• Tower Of Hanoi 함수 추가
• combination recursion 구현
• 러닝 자바스크립트(이선 브라운) 읽기
• 프로그래머스 알고리즘

지금

Tower of Hanoi를 처음 작성했을 때, 게임을 완료할 수 있는 가장 적은 시행 횟수를 출력하는 함수를 만들었다.
오늘은 매 시행 횟수마다 어디에 있는 블럭을 어디로 옮겨야 하는지 보여주는 코드로 변경하여 git에 업데이트 하였다.

const timesOfTOF = (n) => { // number of Disks : n
  return n === 1 ? 1 : timesOfTOF(n-1)*2 + 1
}

const movesOfTOF = n => {
    function moves(n, from, to) {
      const towers = [1,2,3];
      const left = towers.filter(el => el !== from && el !== to);
      return n === 1 ? 
        [[from, to]] : 
      moves(n-1, from, left)
        .concat(moves(1, from, to))
        .concat(moves(n-1, left, to));
    }
    return moves(n,1,3)
};

아무래도 좌표 이동에 대해 표시해 주려면 현재 위치와 다음 위치에 대한 정보가 필요해 moves라는 함수를 만들어서 안에서의 움직임을 출력하도록 조정 하였다.

combination recursion에 대해 생각 해보고 작성해 보았다.

const factorial = n => {
  return n === 0 ? 1 : n*factorial(n-1);
};

const permutation = (n, r) => {
  return factorial(n) / factorial(n-r)
};

const combination = (n, r) => {
  return  permutation(n,r) / factorial(r)
}

기본적인 combination의 구성은 위와 같다.
만약 combination을 재귀 함수로 구현하게 되면,

const combinationRecursion = (n, r) => {
  return r === n ? 1 : combinationRecursion(n-1,r) * n / (n-r) 
};

조합은 nCr = n-1Cr * n / (n - r) 으로 현재의 콤비네이션은 n1이 하나 감소한 조합의 결과로도 나타낼 수 있다. n과 r이 같다면 두 1을 출력하도록 재귀를 탈출 할 수 있는 조건을 설정하여, n을 계속 감소하며 계산하도록 구현한다.

내일

• 러닝 자바스크립트
• 프로그래머스 알고리즘