TIL : Algorithm (2)

알고리즘 테스트를 풀어낼 때 어떤 방법으로 풀어낼지에 대해 생각해보려면 수학적 사고는 필수적이다. 그래서 알고리즘 문제에 자주 등장하는 주요 개념들에 대해 다루려고 한다.

---

1. 최대공약수(GCD) & 최소공배수(LCM)

· 약수 : 어떤 수를 나누어 떨어지게 하는 0이 아닌 수

· 배수 : 어떤 수를 1배, 2배, 3배, ···한 수

· 공약수 : 어떤 수의 공통된 약수

· 공배수 : 어떤 수의 공통된 배수

· 최대공약수(GCD : Greatest Common Divisior) : 둘 이상의 공약수 중에서 최대인 수

· 최소공배수(LCM : Least Common Multiple) : 둘 이상의 공배수 중에서 최소인 수

 

=> 보통 크기가 줄어들거나 개수가 줄어드는 경우는 최대공약수를, 크기가 늘어나거나 시간이 늘어날 때는 최소공배수를 사용한다!

---

2. 순열 & 조합

· 팩토리얼(!) : 서로 다른 n개를 나열하는 경우의 수

· 순열(Permutation) : 서로 다른 n개 중에서 r개를 골라 순서를 고려해 나열한 경우의 수

 

 

· 조합(Combination) : 서로 다른 n개 중에서 r개를 골라 순서를 고려하지 않고 나열한 경우의 수

 

---

3. 멱집합 : 어떤 집합의 모든 부분집합

· 멱집합의 원소의 개수 = 2^n

· 멱집합 구하기 : 임의의 원소를 제외하면서 집합을 작은 단위로 줄여나가는 방법 => 재귀의 응용!!

ex) 집합 A = {0, 1}일 때, 멱집합은 {}, {0}, {1}, {0, 1}이고, 원소의 개수는 2^2 = 4이다.