[CS] Algorithm with Math Day-73

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.