[알고리즘] 알고리즘 풀이에 필요한 수학 개념

somin·2021년 8월 24일

algorithm 코드스테이츠

algorithm

목록 보기

2/2

Algorithm with Math

1. GCD/LCM(최대공약수, 최소공배수)

최대 공약수(GCD. Greatest Common Divisor) : 둘 이상의 공약수 중에서 최대인 수
*유클리드호제법 사용
최소 공배수(LCM. Least Common Multiple ): 둘 이상의 공배수 중에서 최소인 수

1) 최대공약수

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

24와 12의 최대공약수는 12, 하지만 위 문제에선 12를 제외한 최대 공약수인 6
*직사각형의 모든 변에, 최소 하나 이상의 조명이 설치되어야 하기 때문
가로 : 6 간격으로 조명 설치 => 24/6 X 2
세로 : 6 간격으로 조명 설치 => 12/6 X 2

(1) GCD를 구하는 함수

function GCD(a, b) { 
  // 단, a가 b보다 커야함
  let R
  // R이 0이 될 때까지
  while (a % b !== 0)  {
    R = a % b
    a = b
    b = R
  }
  return b
}

(2) 재귀를 이용해 GCD를 구하는 함수

function GCD (a, b) {
  if(a % b === 0) {
    return b 
  }
  
  return GCD(b, a % b) 
}

(3) 한줄로 작성한 코드

const GCD = (a, b) => a % b === 0 ? b : GCD(b, a % b);

2) 최소공배수

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

60, 75, 90의 최소공배수는 900
A : 900분 동안 135개 (900/60 = 15 => 15 X 9)
B : 900분 동안 180개 (900/75 = 12 => 12 X 15)
C : 900분 동안 250개 (900/90 = 10 => 10 X 25)

(1) GCD를 이용해 LCM 구하기

let LCM = a*b/GCD

(2) LCM을 구하는 함수

function LCM (a, b) {
  return a * b / GCD(a, b)
}

(3) 한줄로 작성한 코드

// 한줄로 작성한 코드
const LCM = (a, b) => a * b / GCD(a, b)

2. 순열/조합

1) 순열

한 자리 숫자가 적힌 종잇조각이 흩어져 있습니다. 흩어진 종잇조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다. 종이에 기록된 모든 숫자가 배열로 주어진다면, 이 종잇조각으로 만들 수 있는 소수는 몇 개인가요?

순열 : n개 중에서 일부만을 선택해 순서를 지키며 나열하는 것으로 나열하는 순서가 다르면 서로 다른 경우로 파악
Permutation의 약자 P로 표현
일반식 : nPr = n! / (n - r)!

2) 조합

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

조합 : 순열과 달리 순서를 고려하지 않음
Combination의 약자 C로 표현
일반식 : nCr = n! / (r! * (n - r)!)

3. 멱집합

멱집합 : 집합의 모든 부분집합
모든 부분집합을 나열하는 방법 : 가장 앞 원소(혹은 임의의 집합 원소)가 있는지, 없는지에 따라 단계를 나누는 기준을 결정
집합의 요소가 n개일 때 모든 부분집합의 개수는 2n개
멱집합을 구하는 방법은 순환 구조를 띠는 데, 순환구조는 임의의 원소를 제외하면서 집합을 작은 단위로 줄여나가는 방법
*문제를 작은 단위로 줄여나가는 재귀를 응용할 수 있음