[CS] Algorithm with Math Day-73

cptkuk91·2022년 3월 2일
1

CS

목록 보기
119/139

Algorithm with Math

It is important to have a strategy in order to understand and solve problems.

It is necessary to understand the greatest common divisor, least common multiple, permutation, combination, and power set.

permutations and combinations

Selecting and listing only a subset of n is called a permutation.

Permutations must be listed in order.

formula: nPr = n! / (n-r)!

Caution: 0! and 1! is 1


In combinations, groups are more important than order.

The order of [A,B,C] and [A,C,B] is different, but the combination treats it as one case.

formula: nCr = n! / (r! * (n - r)!)

GCD and LCM

  • measure: A number that divides a number
  • multiple: A number that can be obtained by multiplying any number
  • common factor: common factor of two or more numbers
  • common multiple: common multiple of two or more numbers
  • GCD(Greatest Common Divisor): greatest number of two or more common factors
  • LCM(Least Common Multiple): Minimum of two or more common multiples

LCM

ex) LCM(60, 75, 90) is 900

GCD

ex) GCD(12, 24) is 12

power set

ex) {1,2,3} power set
{}, {1}, {2}, {3}, {1,2}, {1,3}, ... {2,3}, {1,2,3}

All subsets of the set are called power sets.

profile
메일은 매일 확인하고 있습니다. 궁금하신 부분이나 틀린 부분에 대한 지적사항이 있으시다면 언제든 편하게 연락 부탁드려요 :)

0개의 댓글