[CS] Algorithm with Math Day-47

문제를 풀기 위한 3가지 개념

• GCD/LCM (최대공약수, 최소공배수)
  (greatest common divisor/ least common multiple)
• 순열/조합
• 멱집합

Algorithm with Math (순열/조합)

순열

• 순열: 순서를 지키며 나열하는 것
  ex) 5장의 카드에서 3장을 뽑으면서 나열할 때 5p3

• 5장에서 3장을 선택하는 모든 순열의 수
  5p3 = (5 x 4 x 3 x 2 x 1) / (2 x 1) = 60

• 일반식 5p3 = 5! / (5 - 3)!

• 0! && 1! === 1

조합

• 조합: 순서를 생각하지 않고, 하나의 그룹

• 예를들면... [a,b,c], [a,c,b]를 같은 친구로 취급 기타 [b,c,a]도 같은 조합이다!

• 중복된 부분을 제거해주자..

• 5장에서 3장을 무작위로 선택하는 조합의 경우의 수
  5c3 = 5! / (3! 2! 1!) = 10

문제: 소수 찾기

• 소수는 1과 자기 자신으로만 나누어지는 수..

• 1은 소수가 아니니까 1을 제외하고 2부터 실행

• 숫자 2는 자신을 제외한 2의 배수를 제거한다.

• 3을 제외한 3의 배수를 제거한다.

• 4는 2에 의해 삭제됐다.

• 5를 제외한 5의 배수를 삭제한다.

let solution = (n) => {
    let arr = [];
    for(let i = 1; i <= n; i++){
    	arr.push(i);
    }
    for(let i = 1; i * i < n; i++){
    	if(arr[i]){
            let num = arr[i];
            for(let j = num * num; j <= n; j += num){
            	arr[j-1] = 0;
            }
         }
     }
     let result = arr.filter((number) => number);
     result.shift();
     return result.length;
 };

문제: 일곱 난쟁이

왕비를 피해 일곱 난쟁이와 함께 평화롭게 생활하고 있던 백설 공주에게 위기가 찾아왔습니다. 하루일과를 마치고 돌아온 "일곱" 난쟁이가 "아홉" 명이었던 겁니다. 아홉 명의 난쟁이는 모두 자신이 "백설 공주와 일곱 난쟁이"의 주인공이라고 주장했습니다. (뛰어난 수학적 직관력을 가지고 있던) 백설 공주는 일곱 난쟁이의 키의 합이 100임을 기억해 냈습니다. 아홉 난쟁이 각각의 키가 주어질 때, 원래 백설 공주와 평화롭게 생활하던 일곱 난쟁이를 찾는 방법은 무엇인가요?

function solution(arr) {
    let result = arr; // result에다가 얕은 복사
    let sum = arr.reduce((a, b) => a + b, 0);
    for(let i = 0; i < 8; i++){
    	for(let j = i+1; j < 9; j++){
        	if((sum - (arr[i]+arr[j])) === 100){
                  arr.splice(j, 1); // 뒤에서부터 하나씩 지우기
                  arr.splice(i, 1);
            }
        }
    }
    return result;
}

Algorithm with Math (GCD/LCM)

• 약수: 어떤 수를 나누어떨어지게 하는 수
• 배수: 어떤 수의 1,2,3, ...n 배하여 얻는 수
• 공약수: 둘 이상의 수의 공통인 약수
• 공배수: 둘 이상의 수의 공통인 배수
• 최대 공약수: GCD(Greatest Common Divisor): 둘 이상의 공약수 중에서 최대인 수
• 최소 공배수: LCM(Least Common Multiple): 둘 이상의 공배수 중에서 최소인 수

문제: Mask (최소 공배수 - LCM)

방역용 마스크를 제작/판매하는 Mask States 사는 이례적인 전염성 독감 예방을 위해 기존 가격을 유지하며 약속된 물량의 방역용 마스크를 제공하고 있습니다. 이 회사는 사장을 포함하여 A, B, C 세 명뿐이고, 이들 모두 마스크를 제작합니다. 각각의 제작 속도는 다음과 같습니다.
A는 55분마다 9개를, B는 70분마다 15개를, C는 85분마다 25개의 방역용 마스크를 만들 수 있습니다. 이 회사의 사람들은 05:00 시부터 동시에 마스크를 만들기 시작하여 각 55분, 70분, 85분 동안 연속으로 마스크를 제작한 후, 5분씩 휴식을 취합니다. 이들 세 명이 처음으로 동시에 쉬는 시점이 퇴근 시간이라면, 이날 하루에 제작한 마스크는 모두 몇 개인가요? (휴식시간과 퇴근시간이 겹치는 경우, 휴식을 취한 뒤 퇴근합니다.)

• 최소 공배수를 생각했다면, 쉽고 빠르게 문제를 해결할 수 있습니다.

작업 시간, 쉬는 시간 5분을 더해 A,B,C는 각 60분, 75분, 90분마다 마스크를 생산합니다. 따라서 쉬고 난 직후 처음으로 같을 시점을 구할 때는 공배수와 최소 공배수의 개념을 알고 문제에 접근해야 합니다.

결과적으로 LCM(60, 75, 90)은 900입니다.
따라서 A는 900 / 60 = 15번 작업하고, 15번 * 9개 해서 135개의 마스크를 생산합니다.

B는 180개, C는 250개의 마스크를 만들기 때문에 하루 제작한 마스크는 135개 + 180개 + 250개 = 565개가 됩니다.

ex) 최소 공약수와 최소 공배수 구하기 문제

function solution (n, m) {
	let result = [];
    let greatest = (a, b) => {
    	if(b === 0) {
        	return a;
        }
        return greatest (b, a%b);
    }
    let least = (a, b) => (a * b) / greatest(a, b);
    return [greatest(n, m), least(n, m)]
}

문제: 조명 설치 (최대 공약수)

코드스테이츠 라운지에 있는 가로 24cm, 세로 12cm인 직사각형 모양 조형물의 가장자리에 조명을 설치하려고 합니다. 네 모퉁이에는 조명을 반드시 설치해야하고, 나머지 조명은 일정한 간격으로 설치하려고 할 때, 필요한 최소한의 조명 개수는 몇 개일까요? 이때, 꼭지점을 제외한 직사각형의 모든 변에는 최소 하나 이상의 조명이 반드시 설치되어야 합니다. (단, 설치한 조명의 간격은 정수로 이루어진 cm 단위입니다.)

최대 공약수를 떠올리면 빠르게 문제를 해결할 수 있습니다.

GCD(12, 24)는 12입니다. 따라서 (12/12 + 24/12) x 2 = 3 x 2 = 6개입니다.

문제에서는 꼭지점을 제외한 직사각형의 모든 변에, 최소 하나 이상의 조명이 설치되어야 하므로 12를 제외한 최대 공약수로 문제를 해결해야 합니다.

(12/6 + 24/6) x 2 = 6 x 2 = 12개입니다.

Algorithm with Math - 멱집합

집합 {1,2,3} 의 모든 부분집합은 {}, {1}, {2}, {3}, ... {1,2,3} 으로 나열할 수 있고 부분집합의 총 개수는 8개입니다.

이 모든 부분집합을 통틀어 멱집합이라고 합니다.

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