[알고리즘] Algorithm Math

수학적 사고를 통해 컴퓨팅 사고를 할 수 있어야 함

 

순열 Permutation

순열 식

n개의 요소 중 r개를 순서에 상관 있게 뽑는 경우의 수

중복을 허용하지 않기 때문에 r <= n을 만족해야 함

 

조합 Combination

조합 식

 

n개의 요소 중 r개를 뽑는 경우의 수(순서에 상관 없는 부분집합)

중복을 허용하지 않기 때문에 r <= n을 만족해야 함

 

n! 팩토리얼 factorial

n에서부터 1까지 모든 정수의 곱

 

순열과 조합 알고리즘은 

반복문으로 작성시 선택할 개수만큼 반복문을 중첩해야하기 때문에 n개를 선택해야하는 경우 대응이 어려움

-> 재귀를 사용하여 풀이하는 경우가 많음

순서를 고려하여 카드 3장을 선택하는 경우의 수(순열)

function permutationLoop(lookup) {
  let result = [];

  for (let i = 0; i < lookup.length; i++) {
    for (let j = 0; j < lookup.length; j++) {
      for (let k = 0; k < lookup.length; k++) {
        if(i === j || j === k || k === i) continue;
        result.push([lookup[i], lookup[j], lookup[k]]) // 중복 요소 제거
      }
    }
  }

  return result;
}

 

순서에 상관없이 카드를 3장 선택하는 경우의 수(조합)

function combinationLoop(lookup) {
  let result = [];

  // 한 번 조합한 요소는 다시 조합하지 않음
  for (let i = 0; i < lookup.length; i++) {
    for (let j = i + 1; j < lookup.length; j++) {
      for (let k = j + 1; k < lookup.length; k++) {
        result.push([lookup[i], lookup[j], lookup[k]]);
      }
    }
  }
  return result;
}

 

 

 

최대공약수(GCD. Greatest Common Divisor)

공약수 중 최대인 수

- 공약수: 둘 이상의 수의 공통된 약수

- 약수: 어떤 수를 나누어 떨어지게 하는 수

 

유클리드 호제법

최대공약수를 구하는 식

 

2개의 자연수 a, b가 있을 때

a를 b로 나눈 나머지를 r이라하면

a와 b의 최대공약수는 b와 r의 최대공약수와 같다는 이론

-> 나머지가 0이 되었을 때 나눈 수가 a와 b의 최대공약수

// 유클리드 호제법(최대공약수 구하기)
function gcd(a, b){
  while(b !== 0){
    let r = a % b;
    a = b;
    b = r;
  }
  return a;
}

// 유클리드 호제법을 이용해 최소공배수 구하기
function lcm(a, b){
  return a * (b / gcd(a, b));
}

 

최소공배수(LCM. Lowest Common Multiple)

공배수 중 최소인 수

- 공배수: 둘 이상의 수의 공통된 배수

- 배수: 하나의 수에 정수를 곱한 수

 

배수는 무수히 많기 때문에 최대공배수는 구할 수 없음

 

최소공배수 = 최대공약수 * a/최대공약수 * b/최대공약수 = a * b / 최대공약수

 

 

멱집합

어떤 집합의 모든 부분집합

요소가 있는지 없는지 두 가지 경우를 고려하기 때문에 부분집합의 수는 2^n(요소 개수)

- 멱집합을 구하는 방법은 순환구조를 띰 

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

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

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

  return result;
}

 

 

 

 

23.02.08

코스 S4U11 알고리즘 수학