경우의 수 찾기
Factorial
- 일반적으로
n!(Factorial)은n개의 요소에 대한 모든 경우의 수와 같다.
ex)5! === 5 * 4 * 3 * 2 * 1 - 이때, n개 중 일부의 경우의 수를 찾는 것을
순열. - N개 중에서 일부를 그룹으로 지정하고 해당 그룹의 경우의 수를 찾는 것을
조합이라고 한다.
순열
- 단어의 뜻 그대로 순서를 지키면서 나열한다는 뜻이다.
- 순열은 일반식에서
Permutation의 약어인P로 표현한다. - 순열의 일반식으로
nPr = n! / (n - r)!로 표현 할 수 있다.
→n은 요소의 총 갯수,r은 선택한 갯수를 뜻 한다. - 만약 5개중에서 3개를 고르는 경우의 수를 구하는 경우,
n = 5,r = 3이 된다. - 즉,
5P3은5! / (5 - 3)!=5! / 2!=120 / 2=60이 된다.
조합
- n개중 무작위로 선택된 r개의 경우의 수를 구하는 것.
- 조합은 일반식에서
Combination의 약어인C로 표현한다. - 조합은 일반식으로
nCr = n! / (r! * (n - r)!)로 표현 할 수 있다.
→n은 요소의 총 갯수,r은 그룹의 갯수를 뜻 한다. - 5개중에서 3개가 그룹 일때의 경우의 수를 구하는 경우,
n = 5,r = 3이 된다. - 즉,
5C3은5! / (3! * (5 - 3)!)=5! / (3! * 2!)=120 / 6 * 2=120 / 12=10이 된다.
LCM, GCD
LCM(Least Common Multiple, 최소공배수)
- n개의 수에서 공통으로 가지는 배수 중 가장 작은 수를 나타낸다.
→ 수포자라 일부러 정리할 필요가 있다.. - 예를 들어, 아래와 같은 문제가 있는 경우에
LCM(최소공배수)를 활용 할 수 있다.
어떤 시간인
t에 물건을n개 만들어내는 기계들이 있다.
이 기계들이 동시에 물건을 만들어내는 타이밍에 공장의 가동이 종료된다.
이 때, 만들어진 물건의 갯수는 몇개인가?
- 여기서 중요한 점은 동시에 물건을 만들어 내는 타이밍에 가동이 종료된다는 것이므로, 이들의
t의 최소 공배수를 찾아 각 기계들의n을 그최소공배수/ t만큼 곱하여 더해주면 된다.
GCD(Greatest Common Divisor, 최대공약수)
- n개의 수에서 공통으로 가지는 약수 중 가장 큰 수를 나타낸다.
- 아래의 경우,
GCD(최대공약수)를 활용 할 수 있다.
가로가
x, 세로가y인 어떤 직사각형의 공간에 일정한 간격으로 조명을 최소 갯수로 설치할 때, 몇개의 조명이 필요한가?
- 이 문제에서 각
x,y의 길이를 가진 변에 일정하게 조명을 설치하기 위해서는 서로 동일하게 나눠지는 길이를 구해야한다.
→ 각 변에서 일정하게, 동일하게 나눌 수 있는 거리를 구하는 것이라고 볼 수 있다. - 만약
x,y가 각각 14, 28의 직사각형이라면, 최대공약수는 14가 되고, 가로에는 1개, 세로에는 2개를 두는 것으로 총 6개로 일정한 간격에 조명을 설치 할 수 있게된다.
→(x / 최대공약수 + y / 최대공약수) * 2
유클리드 호제법
- 최대 공약수를 구하는 알고리즘
- 두 수가 상대방을 나누어 생기는 나머지를 이용하여 최대 공약수를 구한다.
- 어떤 두 수를 각각
A,B라고 하고 나눈 나머지를C라고 할때,
B를C로 다시 나눠 나머지를 구하고,B에서C를 나눈 나머지로 다시C를 나누고, 그 나머지로C를 나누고... - 아무튼 이런 방식으로, 최종적으로 나머지가 0이 되면 해당 나머지였던 수는 최대공약수가 된다.
// 100과 15의 최대공약수 구하기
100 % 15 === 10
15 % 10 === 5
10 % 5 === 0
// 둘의 최대공약수는 5가 된다.코드로 표현하기
- 유클리드 호제법에 의한 두 수의 최대공약수를 찾는 함수는 아래와 같이 작성 할 수 있다.
// 반복문 사용하기
const gcd = (a, b) => {
let c = 0;
while(b !== 0){
c = a % b
a = b
b = c
}
return a
}
// 재귀 사용하기
const gcd = (a, b) => {
if(b === 0) return a
else return gcd(b / a % b)
}
// 삼항연산자로 표현하기
const gcd = (a, b) => b ? gcd(b / a % b) : a→ A, B 값을 계속 스왑해준다고 생각하면 된다.
- 만약 최소공배수를 구하고 싶은 경우 A와 B의 곱을 최대공약수로 나누면 된다.
→LCM = A * B / GCD(A, B)
+
- 문제를 보고 어떤 수학적 개념을 사용할 수 있는지에 대해 떠올리는 것이 문제를 수월하게 푸는데 도움이 된다.
- 예시로, 이전에 만난 문제중 경우의 수를 구하는 것이 있었는데 카운트를 1씩 올려서 답을 구해야한다 라고 생각했지만, 팩토리얼로 해결하는 방식의 문제가 있었음.
