TIL-42, Algorithm with Math

알고리즘 문제, 코딩테스트에 자주 등장하는 기본적인 수학 개념을 학습해두자.

순열 / 조합

[A, B, C, D, E] 다섯장의 카드중 3장의 카드를 선택할 때.

순열

순서를 생각하며 3장을 선택하는 경우 (순열)

• 첫번째 카드를 선택하는 방법은 5가지.
• 첫번째 카드를 선택하고 두번째 카드를 선택하는 방법은 4가지.
• 두번째 카드를 선택하고 세번째 카드를 선택하는 방법은 3가지.

5 X 4 X 3 = 60가지의 방법이 있다.

이렇게 n개 중에서 일부만을 선택하여 나열하는 것을 순열 이라고 한다.

순열은 일반화 과정을 거쳐 Permutation의 약자 P로 표현한다.

순열은 순서를 고려하기 때문에, [A, B, D]와 [A, D, B]를 다른 경우로 간주한다.

순열 공식

5장에서 3장을 선택하는 모든 순열의 수

= 5! / (5-3)!

= (5 X 4 X 3 X 2 X 1) / (2 X 1)

= 120 / 2

= 60

또는, nPr

= n을 포함, 밑으로 r개의 숫자를 곱한다

= 5 X 4 X 3

= 60

조합

순서를 생각하지 않고 선택하는 경우 (조합)

3장을 하나의 그룹으로 선택한다. 아래와 같은 방법으로 경우의 수를 구한다.

• 순열로 구할 수 있는 경우의 수를 찾는다
• 순열로 구할 수 있는 경우에서 중복된 경우의 수를 나눈다.

조합은 순열과 달리 순서를 고려하지 않는다.

[A, B, C], [A, C, B], [B, A, C], [B, C, A], [C, A, B], [C, B, A]은 모두 A, B, C를 이용해

만들었고, 순열에서는 각각 순서가 다르기 때문에 다른 경우의 수로 간주하지만,

조합에서는 하나의 경우로 간주한다.

위으 여섯가지의 경우의 수는 3장의 카드를 순열로 뽑은것이며, 순열 공식에 적용한 결과

3! / (3-3)! = (3 X 2 X 1) / 1 = 6으로 나온 결과이다.

여기서 순서때문에 발생한 중복의 가짓수를, 중복된 6가지로 나누어 주면 조합의 모든 경우의 수를 얻을 수 있다.

조합은 일반화 과정을 거쳐 Combination의 약자 C로 표현한다.

조합 공식

5! / 3!(5 - 3)!

= (5 X 4 X 3 X 2 X 1) / ((3 X 2 X 1) X (2 X 1))

= 120 / 12

= 10

또는, nCr

= n을 포함, 밑으로 r개의 숫자를 곱한 뒤, r!로 나눠준다.

= (5 X 4 X 3 )/ (3 X 2)

= 60 / 6

= 10

GCD / LCM (최대 공약수, 최소 공배수)

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

멱집합

집합 {1, 2, 3}의 모든 집합

→ {}, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3} 총 8개.

어떤 집합의 모든 부분집합들을 통틀어 멱집합이라고 한다.

모든 부분집합을 나열하는 방법은 아래와 같이 몇 단계로 구분할 수 있다.

• Step A: 1을 제외한 {2, 3}의 부분집합을 나열합니다.
  • Step B: 2를 제외한 {3}의 부분집합을 나열합니다.
    • Step C: 3을 제외한 {}의 부분집합을 나열합니다. → {}
    • Step C: {}의 모든 부분집합에 {3}을 추가한 집합들을 나열합니다. → {3}
  • Step B: {3}의 모든 부분집합에 {2}를 추가한 집합들을 나열합니다.
    • Step C: {3}의 모든 부분집합에 {2}를 추가한 집합들을 나열하려면, {}의 모든 부분집합에 {2}를 추가한 집합들을 나열한 다음 {}의 모든 부분집합에 {2, 3}을 추가한 집합들을 나열합니다. → {2}, {2, 3}
• Step A: {2, 3}의 모든 부분집합에 {1}을 추가한 집합들을 나열합니다.
  • Step B: {2, 3}의 모든 부분집합에 {1}을 추가한 집합들을 나열하려면, {3}의 모든 부분집합에 {1}을 추가한 집합들을 나열한 다음 {3}의 모든 부분집합에 {1, 2}를 추가한 집합들을 나열합니다.
    • Step C: {3}의 모든 부분집합에 {1}을 추가한 집합을 나열하려면, {}의 모든 부분집합에 {1}을 추가한 집합들을 나열한 다음 {}의 모든 부분집합에 {1, 3}을 추가한 집합들을 나열합니다. → {1}, {1, 3}
    • Step C: {3}의 모든 부분집합에 {1, 2}를 추가한 집합을 나열하려면, {}의 모든 부분집합에 {1, 2}를 추가한 집합들을 나열한 다음 {}의 모든 부분집합에 {1, 2, 3}을 추가한 집합들을 나열합니다. → {1, 2}, {1, 2, 3}

원소의 개수가 n개일 때, 모든 부분집합의 개수는 2^n개이다.

( {1, 2, 3, 4} = 16개, {1, 2, 3} = 8개 )