기초 수학

기초 수학

경우의 수

• 합의 법칙(공통 된 부분을 한번 제거해줘야함): n(A U B) = n(A) + n(B)  - n(A ∩ B)
• 곱의 법칙: n(A) * n(B)

약수

• 8의 약수는 1, 2, 4, 8 즉 자기 자신의 수를 1~8까지의 수로 나눴을 때 나머지가 발생하지 않는 수
• 재귀를 통해 구하는 방법

public static int gcd(int n, int m) {
    if (n % m == 0) {
    	return m;
    }
    
    return gcd(m, n % m);
}

최대 공약수

• 두 수의 약수 중 최대값으로 일치하는 수

최소 공배수

• 두 수의 배수 중에서 공통되는 가장 작은 값
• n(A) * n(B) / gcd(최대공약수) 와 동일함

팩토리얼

• 팩토리얼이란 서로 다른 n개를 나열하는 경우의 수를 의미합니다. 기호로는 n! 이렇게 쓰고 계산은 n부터 1씩 줄여나가면서 1이 될때까지의 모든 수를 곱합니다.
• 5! = 5 * 4 * 3 * 2 * 1 = 120

팩토리얼 공식

순열

• 순열이란 서로 다른 n개중에 r개를 선택하는 경우의 수를 의미합니다. (순서 상관 있음)
• 예시) 5명을 3줄로 세우는 방법
• 예시) 서로 다른 4명 중 반장, 부반장 뽑는 방법
• 5P3 = 5! / 2! = 5 * 4 * 3 * 2 * 1 / 2 * 1 = 5 * 4 * 3 = 60

순열 공식

// 5명을 3줄로 세우는 방법 (순서 O, 중복 X)
// 5P3
int n = 5;
int r = 3;
int result = 1;

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

혹은 Stream으로 구현

IntStream().range(2, 6).reduce((x, y) -> x * y);

 

중복 순열

• 중복 순열이란 중복 가능한 n개중에서 r개를 선택하는 경우의 수를 의미합니다. (순서 상관 있음)
• 예시) 서로 다른 4개의 수 중 2개를 뽑는 방법 (중복 허용)
• 예시) 후보 2명, 유권자 3명일 때 기명 투표 방법

중복 순열 공식

// 서로 다른 4개의 수 중 2개를 뽑는 방법 (순서 O, 중복 O)
// 4P2
int n = 4;
int r = 2;
int result = 1;

for (int i = 0; i < r; i++) {
	result *= n;
}

원 순열

• 원 순열은 원 모양의 테이블에 n개의 원소를 나열하는 하는 경우의 수입니다.
• 예시) 원 모양의 테이블에 3명을 앉히는 경우

원 순열 공식

// 원 모양의 테이블에 3명을 앉히는 경우
// 3P3
int n = 3;
int result = 1;

for (int i = 1; i < n; i++) {
	result *= i;
}

 

조합

• 조합은 순열의 경우의 수에서 중복되는 부분을 제외시킨 경우의 수를 구하는 것 입니다.
• A B C D E 5가지의 경우에서 2가지의 조합을 뽑는다면 A B와 B A의 경우 한 가지의 조합으로 보기 때문에 그 경우를 모두 배제해주면 5C2 = 5P2 / 2! = 5 * 4 / 2 = 10이 됩니다.

조합 공식

중복조합

• 후보 A, B가 있고 유권자 3명이 있을 때 중복 조합을 뽑는 방법은
  A A A, A A B, A B B, B B B 총 4가지의 경우가 존재합니다.
• (3 + 2 - 1)! / 3! * 1! = 4! / 3! = 4

중복 조합 공식

로그

• a가 b가 되기 위해서 제곱해야 하는 수
• 예시)

로그