경우의 수

조합론과 경우의 수 

 

조합론(Combinatorics) - 프로그래밍에서 많이 쓰임

• 물건들을 여러 가지 형태로 그룹 짓는 방법을 연구하는 학문
• 예) 16비트 숫자로 표현 가능한 갯수, 알고리즘 복잡도 계산

 

경우의 수

• 어떤 시도(trail)를 통해 일어날 수 있는 사건(events)의 가짓 수
• 경우의 수 세기 : 몇 개인지 세는 기법
• 대표적인 두 가지 방법 - 곱의 법칙, 합의 법칙
  • 곱의 법칙
    • 다음과 같은 절차가 있다고 가정해보자.
    • 이 절차는 2개의 일(tasks)로 나눠 수행할 수 있다.
    • 첫 번째 일을 할 수 있는 방법은 n₁개
    • 두 번째 일을 할 수 있는 방법은 n₂개
    • 두 번째 일은 첫 번째 일이 끝나야 할 수 있다.
    • 총 가짓 수는 n₁ x n₂
    • 일의 수가 늘어나도 동일하다 n₁ x n₂ x n₃ x ...
    • 다중 for문이 이런 예시
      
      
  • 합의 법칙
    • 첫 번째 일을 할 수 있는 방법은 n1개
    • 두 번째 일을 할 수 있는 방법은 n2개
    • 두 번째 일은 첫 번째 일은 연결해서 일어날 수 없음, 즉 첫 번째 일 아니면 두 번째 일만 일어남
    • 가짓 수는 n1 + n2개
    • for문 여러개
      
      

 

포함 - 배제 원리

• 일 1과 일 2의 경우의 수를 셀 때 중복되는 부분이 있다면 합의 규칙을 그대로 사용할 수 없다.
• 이럴 경우 일 1과 일 2의 경우의 수를 더한 뒤 중복된 만큼 수를 빼야 함.
• 트리를 이용 해서 풀어 줄 수 있다. 

 

순열과 조합

• 둘 다 n개의 물체 중에 r개를 뽑을 때 경우의 수를 의미한다.
• 유일한 차이는 순서를 따지는 순열 / 안 따지는 조합으로 나뉜다.
• 순열과 조합 모두 중복 봅기를 허용하는 경우도 있다.

 

순열(permutation) : 순서를 따짐

• 프로그래밍의 배열과 같음 
• 123 과 132는 다르다.
• 만약 빨간 펜 4개와 노랑 펜 2개가 있는데, 펜을 무작위로 뽑는 순서를 찾아야 한다면
• 처음에는 6개 중 1개를 뽑는다 / 6
• 두번째는 5개 중 1개를 뽑는다 / 5
• 즉 6 * 5 => 30개 => factorial 6! 이 된다.
• 아래와 같은 공식이 된다.
  
  



중복 순열 

• 예를 들어 8자리 패스워드에 각 자리에 올 수 있는 알파벳 대소문자의 문제를 구한다면?
• n의 r제곱이다.
• 알파벳 대소문자 52개. 패스워드는 총 8개 => 52⁸

 

조합(combination) : 순서를 안 따짐

• 수학에서 집합과 같음
• 123 과 132는 같다.
• 똑같이 빨간펜 4개, 노랑펜 2개에서 중복된 것을 제거해야 한다.
• 순서가 없다는 것은 집합을 의미하기 때문에 펜 2개를 나열 할 수 있는 경우의 수는 2!
• 즉, r개를 선택 했다면 p(r, r)로 나눈다.
• 아래와 같은 공식이 된다.
  
  

• 즉, 순열은 간단히 곱해 나가는게 빠르고, 조합은 보통 공식을 사용하는게 더 빠르다.

---

[수학] 순열, 조합 공식 총정리