[알고리즘] 경우의 수

1. 곱의 법칙 (Multiplication Rule)

• 정의: 두 개 이상의 사건이 순서대로 발생할 때, 각 사건이 일어날 수 있는 경우의 수를 곱한 값이 전체 경우의 수가 됩니다.
• 수식:
  만약 사건1이 일어날 수 있는 경우의 수가 N가지이고, 사건2가 일어날 수 있는 경우의 수가 M가지라면, 두 사건이 연속해서 발생하는 경우의 수는
  N × M 가지입니다.

예시: 음식과 음료 선택

• 음식 선택: 삼겹살, 소고기, 치킨 (총 3가지)
• 음료 선택: 콜라, 오렌지주스 (총 2가지)

전체 경우의 수 = 3 × 2 = 6가지

• 삼겹살 + 콜라
• 삼겹살 + 오렌지주스
• 소고기 + 콜라
• 소고기 + 오렌지주스
• 치킨 + 콜라
• 치킨 + 오렌지주스

 

2. 곱의 법칙 확장 (Extension of Multiplication Rule)

위 예시에서는 두 가지 사건만 고려했지만, 곱의 법칙은 여러 개의 사건으로 확장할 수 있습니다. 각 사건이 독립적일 때, 각 사건의 경우의 수를 모두 곱하면 전체 경우의 수를 구할 수 있습니다.

예시: 상의, 하의, 양말 조합

• 상의: 빨강, 주황, 노랑 (3가지)
• 하의: 청바지, 녹색바지 (2가지)
• 양말: 검은색, 흰색 (2가지)

전체 경우의 수 = 3 × 2 × 2 = 12가지
모든 경우를 나열하면 다음과 같습니다.

• 빨강 상의 + 청바지 + 검은 양말
• 빨강 상의 + 청바지 + 흰 양말
• 빨강 상의 + 녹색바지 + 검은 양말
• 빨강 상의 + 녹색바지 + 흰 양말
• 주황 상의 + 청바지 + 검은 양말
• 주황 상의 + 청바지 + 흰 양말
• ... (나머지 6가지 생략)

 

3. n개의 대상을 나열하는 방법 (n!)

n개의 서로 다른 대상을 나열하는 경우의 수는 n!(팩토리얼)로 표현됩니다.

팩토리얼 정의

• n! = n × (n - 1) × (n - 2) × ... × 3 × 2 × 1
• 예시: 4개의 대상 {A, B, C, D}를 나열하는 방법
  4! = 4 × 3 × 2 × 1 = 24 가지

경우 나열:

• A-B-C-D
• A-B-D-C
• A-C-B-D
• ... (총 24가지)

팩토리얼은 n이 커질수록 빠르게 값이 증가합니다. 예를 들어, 10! = 3,628,800입니다.

 

4. n개 중에서 r개를 나열하는 방법 (순열, Permutation)

• 정의: n개의 서로 다른 대상 중에서 r개를 선택하여 순서에 맞게 나열하는 경우의 수를 순열이라고 합니다.
• 수식:
  P(n, r) = n! / (n - r)!

예시: 5명 중에서 3명을 뽑아 순서대로 나열

• {A, B, C, D, E} 중에서 3명을 선택해 순서를 고려하여 나열
  P(5, 3) = 5! / (5 - 3)! = (5 × 4 × 3) = 60 가지

경우 나열:

• A-B-C
• A-B-D
• A-B-E
• B-A-C
• ... (총 60가지)

 

5. n개에서 r개를 선택하는 방법 (조합, Combination)

• 정의: n개의 서로 다른 대상 중 r개를 선택하는 경우의 수를 조합(Combination)이라고 하며, 선택한 대상의 순서는 고려하지 않습니다.
• 수식:
  C(n, r) = n! / [r! × (n - r)!]

예시: 5명 중에서 3명을 뽑는 방법

• {A, B, C, D, E} 중에서 3명을 뽑는 경우
  C(5, 3) = 5! / [3! × (5 - 3)!] = (5 × 4 × 3) / (3 × 2 × 1) = 10 가지

경우 나열 (순서는 상관없음):

• A-B-C
• A-B-D
• A-B-E
• A-C-D
• A-C-E
• ... (총 10가지)

 

6. 순열과 조합의 차이

• 순열 (Permutation): 순서를 고려하여 나열 (예: A-B와 B-A는 다른 경우로 취급)
• 조합 (Combination): 순서를 고려하지 않고 선택 (예: A-B와 B-A는 같은 경우로 취급)

 

7. 응용: 중복 순열과 중복 조합

• 중복 순열: 같은 대상을 여러 번 선택하여 순서를 고려해 나열하는 경우.
  • 수식: n^r
  • 예시: 3가지 색 중에서 2개를 순서 있게 나열하는 경우 = 3^2 = 9가지
• 중복 조합: 같은 대상을 여러 번 선택하지만 순서를 고려하지 않는 경우.
  • 수식: C(n + r - 1, r)
  • 예시: 2개의 음료를 중복을 허용하여 선택 (콜라, 콜라도 가능) = C(3, 2)

 

8. 결론

곱의 법칙, 순열, 조합 등은 경우의 수를 계산하는 기본적인 방법으로, 다양한 문제에서 활용됩니다. 조합은 순서를 고려하지 않는 반면, 순열은 순서를 고려한다는 점이 가장 큰 차이입니다. 이러한 개념은 확률, 통계, 알고리즘 등 여러 분야에서 매우 유용하게 사용됩니다