4/6 일일정리 알고리즘(순열/조합,GCD/LCM, 멱집합)

순열과 조합

순열(Permutation)

순열은 서로 다른 n개의 원소를 가지는 어떤 집합에서 중복 없이 순서 상관 '있게' r개이 원소를 선택하거나 나열하는것이다. n개의 원소로 이루어진 집합에서 r개의 원소로 이루어진 부분집합을 만드는 것과 비슷하다.

출처 : 코드스테이츠

Javascript 순열 코드 예시

가위바위보 게임을 할 때 한 사람이 낼수있는 모든 경우의 수를 구하는 함수

function rockPaperScissors (n=3) {	// 가위바위보 몇 번 할지 입력받음
  let arr = ['rock','paper','scissors']
  let result = [];	// 리턴할 배열
  let newArr = [];	// 각각의 경우의 수
  const func = (num) => {
    if(num >= n) { 	// 횟수가 되면 반환할 배열에 push
      result.push([...newArr]);
      return;
    }
    for(let i=0; i<arr.length; i++){ 
      newArr[num] = arr[i];	// num번째에 낼 요소 입력
      func(num+1);	// 횟수1 늘리고 재귀호출
    }
  }
  func(0);
  return result;
};

이 코드에서는 중복을 신경쓰지 않았는데, 중복을 허용하지 않는 경우에는 새로운 배열을 하나 만들어서 해당 요소를 썻는지를 기록하면서 재귀 함수를 사용해야 한다.

 

조합

조합은 서로 다른 n개의 원소를 가지는 집합에서 중복 없이, 순서 '상관없이' r개의 원소를 선택하는것이다. 

순열과 다른점은 순서 상관없이 원소를 선택하기 때문에 순열로 구한 부분집합들 중에서 같은 원소를 가지고 순서만 다른 부분집합들을 제거해줘야 한다.

출처 : 코드스테이츠

 

Javascript 조합 코드 예시

주어진 배열에서 서로다른 숫자 3개를 더한 값이 소수인 값이 몇개인지 확인하는 함수

function boringBlackjack(cards) {
  const isPrime = (n) => {
    if(n===2) return true;
    if(n % 2 ===0) return false;
    for(let i=3; i<=Math.sqrt(n); i+=2){
      if(n % i === 0) return false;
    }
    return true;
  }
  let arr =[];
  for(let i=0; i<cards.length-2; i++){
    for(let j=i+1; j<cards.length-1; j++){
      for(let k=j+1; k<cards.length; k++){
        let sum = cards[i]+cards[j] + cards[k];
        arr.push(sum);
      }
    }
  }
  let result =0;
  for(let el of arr){
    if(isPrime(el)) result++
  }
  return result;
}

중복된 요소를 선택하면 안되기 때문에 반복문을 돌릴때 j = i+1, k=j+1를 시작점으로 설정해준다.

 

 

GCD/ LCM

GCD(Greatest Common Divisor), 최대 공약수는 두 수 이상의 수로 나누어 떨어지는 여러 공약수 중 최대인 수를 말한다.

LCM(Lowest Common Multiple), 최소 공배수는 두 수 이상의 여러 공배수중 최소인 수를 말한다.

알고리즘에서 GCD나 LCM을 구해야 하는 경우 주로 유클리드 호제법을 사용한다.

 

유클리드 호제법

2개의 자연수 a와 b가 있을 때, a를 b로 나눈 나머지를 r이라 하면 a와 b의 최대공약수는 b와 r의 최대공약수와 같다는 이론이다. 이러한 성질에 따라 b를 r로 나눈 나머지 r’를 구하고, 다시 r을 r’로 나누는 과정을 반복해, 나머지가 0이 되었을 때 나누는 수가 a와 b의 최대공약수임을 알 수 있게 된다.

 

javascript 코드 예시

const gcd = (a,b) => {
    if( b ===0) return a;
    return gcd(b,a%b);
  }

 최대공약수의 경우 유클리드 호제법을 재귀함수를 이용하여 구현하면 간단하게 구할 수 있다.

최소공배수 같은 경우 주어진 두수 a,b 를 곱해서 최대 공약수로 나누어 주면 구할 수 있다.

const lcd = (a,b) => {
	return (a*b) / gcd(a,b);
}

 

멱집합(Power Set)

어떤 집합이 있을 때 이 집합의 모든 부분집합을 멱집합(Power Set)이라고 한다.

예를 들어 {1,2,3}이라는 집합이 있을 때 이 집합의 멱집합은

{{},{1},{2},{3},{1,2},{1,3},{2,3},{1,2,3}}

이렇게 8가지가 있다. 요소의 개수가 n개인 집합의 멱집합은 총 2^n개 이다.

 

javascript로 구하는 멱집합 예시

재귀함수를 활용하여 부분집합을 전부 찾을 수 있다.

 

* 코플릿 9번문제 '집밥이 그리워' 문제에서는 재귀가 아니라 반복문을 활용해보았다.

 '집밥이 그리워' 문제는 문자열을 요소로 가지는 배열이 주어질 때 멱집합을 구하고, 알파벳순으로 정렬하는 문제였다.

function missHouseMeal(sideDishes) {
  let result = [];
  let n = sideDishes.length;
  let max = 2**n-1;
  for(let i=0; i<=max;i++){
    let newArr = []
    let bi = String(i.toString(2));	// 이진법으로바꾸기
    while(bi.length<n) bi = '0' +bi;	// 이진법의 형식 맞추기( 예를들면 2는 000010 이런식으로 자리수 맞추기)
    let biArr = bi.split('').reverse();
    for(let j=0; j<biArr.length;j++){
      if(biArr[j] === '1') newArr.push(sideDishes[j]);
    }
    newArr.sort()
    result.push(newArr);
  }
  result.sort();
  return result;
}

멱집합은 각각의 요소가 들어갈지 안들어갈지 2진법으로 나타낼 수 있다. 1이면 현재 만들고 있는 부분집합에 요소를 넣고, 0이면 넣지 않는 식으로 할 수 있는데, 이것을 0부터 멱집합의 총 개수-1까지 반복문으로 나타내면 입력된 집합의 부분집합을 모두 구할 수 있다.