KTY repository

Math

•
  • Algorithm
 •
  • algorithm
  • codestates
  • math

가장 어려운 수학적 사고능력

1. 순열과 조합

  • 순열: 요소 n개중에 m개를 선택해 순서에 상관있게 뽑는 경우의 수
  • 조합: 순서에 상관없이 요소 n개중에 m개를 뽑는 경우의 수
  • !팩토리얼: n!은 n에서부터 1씩 감소하여 1까지의 모든 정수의 곱이다.(n보다 작거나 같은 모든 양의 정수의 곱) 0!, 1! -> 1

1.1. 순열

permutation, 서로다른 n기의 원소를 가지는 어떤 집합에서 중복없이 순서에 상관있게 r개의 원소를 선택하거나 혹은 나열하는 것이며, 조합과 마찬가지로 n개의 원소로 이루어진 집합에서 r개의 원소로 이루어진 부분집합을 만드는 것이다.

순열은 조합과 달리 순서도 따져서 부분집합을 만든다.

nPr = n(n-1)(n-2)(n-3) … (n-r+1) = n! / (n-r)!

  • P: permutation
  • n: 원소의 총개수
  • r: 뽑는 개수
  • R <= N

1.2. 조합

combination, 서로 다른 n개의 원소를 가지는 어떤 집합에서 중복없이 순서에 상관없게 r개의 원소를 선택하는것이다. n개의 원소로 이루어진 집합에서 r개의 원소로 이루어진 부분집합을 만드는것과 같다.

조합은 순서에 상관없이 원소를 선택해 부분집합을 만드는 것이다.

nCr = n(n-1)(n-2)(n-3) … {n-(r-1)} / r(r-1)(r-2)(r-3) … 321 = n! / r!(n-r)! = nPr / r!

  • C: combination
  • n: 원소의 총 개수
  • r: 뽑는 개수
  • R <= N

2. GCD와 LCM

최대공약수와 최소공배수

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

2.1. GCD

최대공약수, greatest common divisor, 두수 이상의 여러 공약수중 최대인 수

2.1.1. 공약수

common divisor, 두수이상의 여러 수중 공통된 약수

divisor: 약수, 어떤 수를 나누어 떨어지게 하는 수

2.2. LCM

최소공배수, lowest common multiple, 두수이상의 여러 공배수중 최소인 수

2.2.1. 공배수

common multiple, 두수이상의 여러수중 공통도니 배수

multiple: 하나의 수에 정수를 곱한 수, 그 수에 의해 나누어 떨어지는 수

2.3. 수식

12 = two * 이 * 삼 19 = 이 * 삼 * three 이 * 삼 * three * two = 36

2.3.1. 유클리드의 호제법

가장 작은 수들의 곱으로 나타내며 구하는법, 최대공약수와 최소공배수를 구하는 모든 문제에 적용해보고 시작할 수 있다. 최대공약수와 관련이 깊은 공식이다.

2개의 자연수 a와 b가 있을 때, a를 b로 나눈 나머지를 r, a와 b의 최대공약수는 b와 r의 최대공약수와 같다.

b를 r로 나눈 너머지 r다시를 구하고, 다시 r을 r다시로 나누는 과정을 반복해, 나머지가 0이 되었을 때 나누는 수가 a와 b의 최대공약수이다.

2개의 자연수 a,b (절대로 a > b)
a / b = q + r
  b / r = q + r다시
      ... r / r다시 = q + 0
  • q: quotient, 몫
  • r: rest, 나머지

a와 b를 나누었을 시 q와 r이나온다. b를 r로 나눈다. q와 나머지 r다시 나오면 r을 r다시와 나누다보면 몫 q, 나머지 r이 0이 되는 상황이 도출된다. r다시가 최대공약수이다.

2개의 자연수 a,b (단, a > b)
a / b = q + r               81 / 15 = 5 + 6
  b / r = q + r다시            15 / 6 = 2 + 3
    ...r / r다시 = q + 0         6 / 3 = 2 + 0

3. 멱집합

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

원소가 있는지 없는지 2가지 경우를 고려한다. 집합의 요소가 n개일때 모든 부분집합의 개수는 2n이다.

멱집합을 구하는 방법은 순환구조를 가진다. 임의의 원소를 제외하면서 집합을 작은 단위로 줄여나간다. 문제를 작은 단위로 줄여나가는 재귀를 응용가능하다.

4. 추가참고

Regexr

참조

codestates