[Toy] 1 - 5

1. orderOfPresentation

한 사람이 주어진 round의 가위바위보를 할 때, 가능한 모든 경우의 수를 2차원 배열로 나타내는 함수 구현
(단, 'rock', 'paper', 'scissors' 순의 중요도를 가지는 '가중치 적용 정렬'을 따른다.)           

const rockPaperScissors = function (rounds) {
  rounds = rounds || 3;
  const list = ['rock', 'paper', 'scissors'];
  const result = [];
  
  const callback = function (roundsToGo, playedSoFar) {
    if (roundsToGo === 0) {
      result.push(playedSoFar);
      return;
    }
    
    for (let i = 0; i < list.length; i++) {
      let el = list[i];
      callback(roundsToGo - 1, playedSoFar.concat(el)); // rounds 줄여가며 result 채우기
    }
  };

  callback(rounds, []); // 처음에 roundsToGo = rounds, playedSoFar = [] 설정
  return result;
};

---

2. fibonacci

재귀함수를 이용해 피보나치 함수 구현 (반복문 사용 X)

// O(2^N)
function fibonacci (n) {
  if (n <= 1) return n;
  return fibonacci(n - 2) + fibonacci(n - 1);
}

// O(N)
// 이미 해결한 문제의 정답은 따로 기록해둔다.
function fibonacci(n) {
  const memo = [0, 1];
  const aux = (n) => {
    if (memo[n] !== undefined) return memo[n];
    memo[n] = aux(n - 2) + aux(n - 1);
    return memo[n];
  }
  return aux(n);
}

---

3. isSubsetOf => 디버깅☆

두 개의 배열(base, sample)을 입력받아 sample이 base의 부분집합인지 여부를 리턴

// O(M * N)
const isSubsetOf = function (base, sample) {
  return sample.every((item) => base.includes(item));
}

// 각 배열 정렬 : O(N * logN), O(M * logM)
// N >= M이므로 O(N * logN)
const isSubsetOf = function (base, sample) {
  base.sort((a, b) => a - b);
  sample.sort((a, b) => a - b);
  
  const findItemInSoretedArr = (item, arr, from) => {
    for (let i = from; i < arr.length; i++) {
      if (item === arr[i]) return i;
      else if (item < arr[i] return -1;
    } return -1;
  };
 
  let baseIdx = 0;
  for (let i = 0; i < sample.length; i++) {
    baseIdx = findItemInSortedArr(sample[i], base, baseIdx);
    if (baseIdx === -1) return false;
  }
  return true;
}

---

4. bubbleSort (버블 정렬)

정수를 요소로 갖는 배열을 입력받아 오름차순으로 정렬하여 리턴

const swap = function (idx1, idx2, arr) {
  // 두 변수를 바꾸는 방법
  
  // 1) 임시 변수를 활용한 방법
  let temp = arr[idx1];
  arr[idx1] = arr[idx2];
  arr[idx2] = temp;

  // 2) Destructuring assignment를 활용한 방법
  // arr이 reference type이라 가능
  // [arr[idx1], arr[idx2]] = [arr[idx2], arr[idx1]];

  // 3) XOR 연산을 활용한 방법
  // arr이 reference type이라 가능
  // arr[idx1] ^= arr[idx2];
  // arr[idx2] ^= arr[idx1];
  // arr[idx1] ^= arr[idx2];
};

let bubbleSort = function (arr) {
  let N = arr.length;

  for (let i = 0; i < N; i++) {
    let swaps = 0; // 어떤 요소도 swap되지 않은 경우 배열은 정렬된 상태

    for (let j = 0; j < N - 1 - i; j++) {
      // 매 반복마다 i번째로 큰 수가 마지막에서 i번째 위치하게 된다.
      // 이미 정렬된 요소는 고려할 필요가 없으므로 N - 1 - i까지만 비교한다.
      if (arr[j] > arr[j + 1]) { 
        swaps++;
        swap(j, j + 1, arr);
      }
    }

    if (swaps === 0) {
      break;
    }
  }

  return arr;
};

---

5. tiling => 피보나치

// O(N)
let tiling = function (n) {
  const memo = [0, 1, 2];
  
  const aux = (size) => {
    if (memo[size] !== undefined) return memo[size];
    // 이미 구한 수인지
    if (size <= 2) return memo[n];
    memo[size] = aux(size - 2) + aux(size - 1);
    return memo[size];
  }
  return aux(n);  
}