TIL: 2022-12-12

⚙️ 오늘 배운 언어

수학 알고리즘

 

🗝 키워드

순열, 중복순열, 조합, gcd, lcm, 멱집합

 

🗣 스스로에게 설명

순열

n개에서 r개를 순서를 생각하며 뽑는 경우의 수

☃️ 경우의 수 자체를 리턴하고 싶다면 공식을 이용하면 됨

☃️ 경우의 수에 포함되는 부분집합들을 전부 보고 싶다면 이렇게 짜면 된다.

 

1. 중복순열 - 중복이 포함된 경우

// 배열(arr)과 뽑는 수(num)가 들어오면 조합을 리턴하는 함수

function getPermutation(arr, num) {
  let result = [];

  // 조합을 만드는 보조함수
  function aux(count, subset) {
    if (count === 0) {
      result.push(subset);
      return;
    }

    for (let i = 0; i < arr.length; i++) {
      let current = arr[i];

      aux(count - 1, subset.concat(current));
    }
  }

  aux(num, []);
  return result;
}

// 배열에서 3개씩 뽑는 모든 중복순열을 리턴한다
console.log(getPermutation([1, 2, 3, 4], 3));

중복순열 결과

2. 일반순열 - 중복이 포함되지 않은 경우

// 배열(arr)과 뽑는 수(num)가 들어오면 조합을 리턴하는 함수

function getPermutation2(arr, num) {
  let result = [];

  // 조합을 만드는 보조함수
  function aux(arr2, count, subset) {
    if (count === 0) {
      result.push(subset);
      return;
    }

    for (let i = 0; i < arr2.length; i++) {
      let current = arr2[i];
      let slicedArr = arr2.slice(); // 배열 얕은 복사
      slicedArr.splice(i, 1); // current는 제외하고 재귀 호출
      aux(slicedArr, count - 1, subset.concat(current));
    }
  }

  aux(arr, num, []);
  return result;
}

// 배열에서 3개씩 뽑는 모든 순열을 리턴한다
console.log(getPermutation2([1, 2, 3, 4], 3));

순열 결과

 

조합

n개에서 r개를 순서를 생각하지 않고 뽑는 경우의 수

순열에서는 [1, 2, 4], [2, 1, 4], [4, 2, 1]을 전부 다르게 취급한다. (순서가 중요하기 때문)

하지만 조합에서는 순서를 생각하지 않기 때문에 [1, 2, 4], [2, 1, 4], [4, 2, 1]을 전부 같게 생각한다.

 

조합은 반복문으로밖에 구현을 안 해봐서 다른 블로그를 참고했다.

순열 코드에서 살짝 바꾸면 쓸 수 있을 것 같은데 이상하게 안 돼서 좀 더 연구해봐야할 것 같음...

const getCombination = function (arr, selectNumber) {
  const results = [];
  if (selectNumber === 1) return arr.map((value) => [value]); 

  arr.forEach((fixed, index, origin) => {
    const rest = origin.slice(index + 1); // slice로 현재 인덱스는 제외하고
    const combinations = getCombination(rest, selectNumber - 1); // 그 다음부터 조합을 붙인다
    const attached = combinations.map((combination) => [fixed, ...combination]); 
    results.push(...attached); 
  });

  return results; 
};

// 배열에서 3개씩 뽑는 모든 조합을 리턴한다
console.log(getCombination([1, 2, 3, 4], 3));
// [ [ 1, 2, 3 ], [ 1, 2, 4 ], [ 1, 3, 4 ], [ 2, 3, 4 ] ]

JavaScript로 순열과 조합 알고리즘 구현하기

 

유클리드 호제법을 이용한 최대공약수 알고리즘 (gcd)

function gcd(a, b) {
  while (b !== 0) {
    let r = a % b;
    a = b;
    b = r;
  }
  return a;
}

// 재귀 이용
function gcd_rec(a, b) {
  if (a % b === 0) return b;
  return gcd(b, a % b);
}

gcd를 이용하여 최소공배수를 리턴하는 알고리즘도 만들 수 있다.

// 최소공배수
function lcm(a, b) {
  return a * (b / gcd(a, b));
}

 

멱집합

어떤 한 집합이 있을 때 그 집합의 모든 부분집합을 멱집합이라고 한다.

function powerSet (arr) {
	const result = [];

	function recursion (subset, start) {
		result.push(subset);

		for(let i = start; i < arr.length; i++){
			recursion(subset.concat(arr[i]), i+1);
		}
	}

	recursion([], 0);

	return result;
}

// 빈 배열 포함
console.log(powerSet(['a', 'b', 'c']);

멱집합 출력 결과

 

❓ 막히는 or 막혔던 부분

순열 코드 안의 재귀 코드를 이해하는 것이 어려웠다. 

 

🔍 공부가 더 필요한 부분

배운 개념을 응용하여 더 다양한 문제를 풀어보며 감 익히기!