TIL 48: [자료구조/알고리즘] 코딩 테스트 준비

알고리즘 무제와 코딩 테스트에 자주 등장하고 필요한 주요 개념들을 학습했습니다. 크게 순열/조합, 멱집합, GCD/LCM(최대공약수, 최소공배수), 멱집합에 대해 개념을 간단히 정리하고, 문제를 풀면서 개념을 적용해보았습니다.

큰 틀은 동일한 상태에서 일부의 범위나 표현만 다르게 해줘도 중복순열, 순열, 조합 등을 표현할 수 있었습니다. 예를 들어, 배열에서 5개를 선택하는 경우 하나의 수를 선택하고, 남은 배열에서 4개를 선택해야 합니다. 이후 또 하나의 수를 선택하고,남은 배열에서 3개를 선택해야 합니다. 이러한 과정은 재귀과정으로 잘게 나눌 수 있어 큰 틀은 동일하게 됩니다.

그래서 오늘은 중복순열, 순열, 조합의 템플릿을 간단하게 정리해보려고 합니다!

 

중복순열

//#1
function permutation(rounds, result) {
  if (rounds === 0) {
  	output.push(result); 
  	return;
  }
  for (let i=0; i<game.length;i++) {
  	const nowPlay = game[i]
  	permutation(rounds-1, result.concat(nowPlay)); 
  }
}


//#2
function permutation(arr, selectNum) {
  const result = [];
  if (selectNum === 1) return arr.map((v) => [v]);

  arr.forEach((v, idx, arr) => {
    const fixed = v;
    const restArr = arr;
    const permutationArr = permutation(restArr, selectNum - 1);
    const combineFix = permutationArr.map((v) => [fixed, ...v]);
    result.push(...combineFix);
  });
  return result;
}

 

 

순열

// #1
function permutation(stuffArr, result, choiceNum) {
  if (choiceNum === 0) {
    output.push(result);
    return;
  }
  for (let i = 0; i < stuffArr.length; i++) {
  	let gredient = stuffArr[i];
  	let sauce = stuffArr.slice();
  	sauce.splice(i,1);
  	permutation(sauce, result.concat(gredient), choiceNum-1)
  }
}


//#2
function permutation(arr, selectNum) {
  let result = [];
  if (selectNum === 1) return arr.map((v) => [v]);

  arr.forEach((v, idx, arr) => {
    const fixer = v;
    const restArr = arr.filter((_, index) => index !== idx);
    const permuationArr = permutation(restArr, selectNum - 1);
    const combineFixer = permuationArr.map((v) => [fixer, ...v]);
    result.push(...combineFixer);
  });
  return result;
}

 

 

조합

//#1
function combination(cards, result, num) {
  if(num === 0) {
    output.push(result);
    return;
    }
  for (let i=0; i < cards.length; i++) {
    let card = cards[i];
    let rest = cards.slice(i+1);
    combination(rest, result.concat(card), num-1)
  }
}

//#2
function combination(arr, selectNum) {
  const result = [];
  if (selectNum === 1) return arr.map((v) => [v]);
  arr.forEach((v, idx, arr) => {
    const fixed = v;
    const restArr = arr.slice(idx + 1);
    const combinationArr = combination(restArr, selectNum - 1);
    const combineFix = combinationArr.map((v) => [fixed, ...v]);
    result.push(...combineFix);
  });
  return result;
}

 

 

유클리드 호제법

유클리드 호제법은 두 수의 최대공약수를 구하는 알고리즘입니다.

여기서 호제법이랑 두 수가 서로 상대방 수를 나누어서 원하는 수를 얻는 알고리즘을 말합니다.

호제법 증명은 https://www.youtube.com/watch?v=TxdljAFjTNw 이 영상을 참고하시면 될듯 합니다!

 

 

const getGCD = function (M, N) {
  if (M % N === 0) {
    gcd = N;
    return;
  }
  else {
    getGCD(N, M % N);
  }
}