수열추측하기

왼쪽 방식은 틀리고 오른쪽 방식은 맞다.

최적화 o

위 문제를 모든 순열을 구한다음 순열 배열마다 값을 더해서 입력값과 비교하는 로직이라면 시간초과임.

다음과 같이 조합수를 이용해서 풀어야 더 빠르다.

function solution(n, f) {
  
  // 조합수 로직
  const combi = [];
  function getCombinationNumber(n, r) {
    //3C2
    if (n === r || r === 0) {
      return 1;
    }
    if (r === 1) {
      return n;
    }
    return getCombinationNumber(n - 1, r - 1) + getCombinationNumber(n - 1, r);
  }

  for (let check = 0; check < n; check++) {
    combi.push(getCombinationNumber(n - 1, check));
  }
  
  
  
  // 순열을 구해서 조합수를 곱하는 로직
  const per = [];
  function getPerArray(visited, current) {
    if (current.length === n) {
      // 순열 * 조합수 값이 f와 일치한다면 정답이므로 per배열에 넣어준다.
      if (
        f ===
        combi.map((i, index) => current[index] * i).reduce((a, b) => a + b)
      ) {
        per.push(current);
      }
      return;
    }
    for (let check = 0; check < n; check++) {
      if (!visited.includes(check)) {
        getPerArray([...visited, check], [...current, check + 1]);
      }
    }
  }
  getPerArray([], []);
  return per;
}

최적화 x

const arr = [...new Array(n)].map((_, idx) => idx + 1);
  const pers = [];
  const answer = [];
  function getPaskal(arr) {
    function DFS(a) {
      if (a.length === 1) {
        if (a[0] === f) {
          answer.push(arr);
        }
        return;
      }
      const propArr = [];
      for (let check = 0; check < a.length - 1; check++) {
        propArr.push(a[check] + a[check + 1]);
      }
      DFS(propArr);
    }
    DFS(arr);
  }
  function getPer(visited, cur) {
    if (cur.length === n) {
      pers.push(cur);
      return;
    }
    for (let check = 0; check < n; check++) {
      if (!visited.includes(check))
        getPer([...visited, check], [...cur, arr[check]]);
    }
  }
  getPer([], []);
  pers.forEach((per) => {
    getPaskal(per);
  });

수들의조합

function solution(n, k, arr, m) {
  let answer = 0;
  function DFS(current, start) {
    if (current.length === k) {
      if (current.reduce((a, b) => a + b) % 6 === 0) {
        answer++;
      }
      return;
    }
    for (let check = start; check < arr.length; check++) {
      DFS([...current, arr[check]], check + 1);
    }
  }
  DFS([], 0);
  return answer;
}

조합구하기

function solution(n, m) {
  let comb = [];
  function DFS(cur, current) {
    if (current.length === m) {
      comb.push(current);
      return;
    }
    for (let check = cur; check <= n; check++) {
      DFS(check + 1, [...current, check]);
    }
  }
  DFS(1, []);
  console.log(comb);
}

기억해둘 사실

나만의 조합

const getCombinations = function (arr, selectNumber) {
  const results = [];
  if (selectNumber === 1) return arr.map((value) => [value]); // 1개씩 택할 때, 바로 모든 배열의 원소 return

  arr.forEach((fixed, index, origin) => {
    const rest = origin.slice(index + 1); // 해당하는 fixed를 제외한 나머지 뒤
    const combinations = getCombinations(rest, selectNumber - 1); // 나머지에 대해서 조합을 구한다.
    const attached = combinations.map((combination) => [fixed, ...combination]); //  돌아온 조합에 떼 놓은(fixed) 값 붙이기
    results.push(...attached); // 배열 spread syntax 로 모두다 push
  });

  return results; // 결과 담긴 results return
};

나만의 순열

const getPermutations = function (arr, selectedNumber) {
  const results = [];
  if (selectNumber === 1) return arr.map((value) => [value]);
  arr.forEach((fixed, index, orgin) => {
    const rest = [...orgin.slice(0, index), ...origin.slice(index + 1)];
    const permutations = getPermutations(rest, selectedNumber - 1);
    const attached = permutations.map((permutation) => [fixed, ...permutation]);
    results.push(...attached);
  });
  return results;
};

나만의 조합수 구하기

function solution(n, r) {
  // object에 이미 계산한 값을 저장한다.

  let object = {};
  function DFS(n, r) {
    // 메모이제이션이다. 이미 구한 조합이면 바로 리턴
    if (object[`${n}${r}`]) return object[`${n}${r}`];
    if (r === 1) return n;
    if (n === r) {
      return 1;
    }
    return (object[`${n}${r}`] = DFS(n - 1, r - 1) + DFS(n - 1, r));
  }
  return DFS(n, r);
}

백트래킹

DFS와 유사하지만, 다르다.
백트래킹의 주요개념은 유망하지 않은 자식은 탐색하지 않는다는것임

내일 너비우선탐색하고 백트래킹 정복해야겠다.
[4-queens]