기초수학 정리

1. 최대공약수와 최소공배수

1) 최대공약수 (Greatest Common Denominator)

[약수]

해당 수를 나누었을때 나머지가 없는 수.

\[\begin{aligned} 8~&-> 1, 2, 4, 8\\ 12~ &-> 1, 2, 3, 4, 6, 12 \end{aligned}\]

*약수 중 가장 큰 수는 해당 수를 2로 나눈 값이기 때문에 for문을 돌 때는 끝까지 다 돌 필요 없음

[공약수]

두 수의 공통된 약수.

\[8과~~12의~~공약수~~-> 1, 2, 4\]

[최대공약수]

공약수 중 가장 큰 수.

\[8과~~12의~최대공약수~~->~ 4\]

*for문을 돌아도 되나, 유클리드 호제법을 사용한 재귀함수로 구할수 있음

2) 최소공배수 (Lowest Common Multiple)

[배수]

해당 수를 2, 3, 4… 순차적으로 배한 수.

\[\begin{aligned} 8 ~&-> 8, 16, 24, ...\\ 12~ &-> 12, 24, 36, ... \end{aligned}\]

*약수 중 가장 큰 수는 해당 수를 2로 나눈 값이기 때문에 for문을 돌 때는 끝까지 다 돌 필요 없음

[공배수]

두 수의 공통된 배수.

\[8과~~ 12의~~ 공배수 ~~-> 24, 48, ...\]

[최소공배수]

공배수 중 가장 작은 수. \(8과~~ 12의~~ 최소공배수 ~~-> 24\\24 ~= ~8~ X~ 12~ /~ 4\)

*최소공배수 = 수1 X 수2 / 최대공약수

---

2. 순열

1) 팩토리얼 (Factorial)

1부터 n까지를 곱한 수 \(n! = n(n-1)(n-2)...1~~(n은 자연수)\)

for(int i = n; i >= 1; i--) {
	result *= i;
}

2) 순열 (Permutation)

서로 다른 n개 중 r 개를 선택하여 나열하는 경우의 수 (순서O, 중복X) \(nPr = n! / (n-r)! = n(n-1)(n-2)...(n-r+1) ~~(단, 0<r<=n)\)

for(int i = n; i >= n - r + 1; i--) {
    result *= i;
}

2-1) 중복순열

서로 다른 n개 중 r 개를 선택하는 경우의 수 (순열과 같지만, 중복이 있는 경우)

\[n^r\]

for(int i = 1; i <= r; i++) {
	result *= n;
}
// Math 함수 활용
result = Math.pow(n, r);

2-2) 원 순열

원으로 나열하는 경우의 수 \(n! / n = (n-1)!\)

for(int i = n-1; i>=1; i--) {
    result *= i;
}

---

3. 조합

1) 조합 (Combination)

서로 다른 n개 중 r 개를 선택하는 경우의 수 (순서 X, 중복 X) \(nCr = n! / (n-r)! r! = nPr/r!\) *순서가 없는 것이 순열과 다른점이라 순서를 없애주기 위해 분모에 r!

1-1) 중복 조합

서로 다른 n개 중 r 개를 선택하는 경우의 수 (순서 X, 중복 O) \(nHr = n+r-1Cr = (n+r-1)!/(n-1)!r!\)

---

4. 지수와 로그

1) 제곱과 지수

[n제곱]

같은 수를 n번 곱함

[제곱근]

루트. a를 제곱하여 b가 되면, a는 b의 제곱근.

[지수]

\[a^x =>~ ~a: 밑,~~ x: 지수\]

2) 로그

지수의 반대. \(log_{a}b => a가~~b가~~되기~~위해~~제곱해야~~하는~~수\)

---

마지막 수정일시: 2022-08-25 15:17