Algo | 조합 기초

 

조합은 수를 세는 것에 관한 수학

 

기초적인 셈

곱의 법칙

 집합 A의 원소가 |A|개, 집합 B의 원소가 |B|개일때 , A와 B에서 하나씩 뽑아서 조합하는 경우의 수가 |A|X|B|

 

합의 법칙

 집합 A의 원소가 |A|개, B의 원소가 |B|개일때, A또는 B에서 하나를 뽑는 경우의 수는 |A|+|B|

 

합집합의 원소의 개수 

  두 집합이 겹치는 부분이 있는 경우에 하나를 뽑는 경우의 수는 |AUB| = |A|+|B|-|A∩B|

  집합 세 개의 합집합 원소의 갯수를 구할때는 |AUBUC| = |A|+|B|+|C|-|A∩B|-|B∩C|-|A∩C|+|A∩B∩C|

 

중복해서 세를 것은 조합론에서 골치 아픈 부분

다른 방법으로는 bijection을구 구하는 방법, 한 집합의 원소와 다른 집합의 원소 사이에 일대일 대응이 되는 경우, 한 집 합의 원소 개수를 세면 자동으로 달느 집합의 원소의 갯수를 셀 수 있음

 

기본적인 조합론

순열 (Permutation)

모든 항목이 정확하게 한번씩만 등장하는 경우 n개의 항목을 배열하는 방법

세개의 항목을 배열하며 3!=6 으로 123, 132, 213, 231, 312, 321 이지만 n=10이면 10! = 3,628,800 이기에 완전 검색에 한계에 다다른다.

 

부분집합

n개의 가능한 항목 중에서 임의의 원소를 뽑아낸 것을 부분 집합 (subset)이라고 한다.

 n개의 원소가 있으면 부분 집합의 개수는 2^n개가 된다. 항목이 세 개 있으면 2^3=8로 각각 1, 2, 3, 12, 13, 23, 123, 공집합이 된다. 공집합도 부분집합임에 주의하자. n=20이면 2^20 = 1,048,576이므로 완전 검색에 한계에 다다른다

 

문자열

중복을 허용하여 항목을 늘어놓는 것을 문자열(string, 중복 순열)이라고 한다.

n개의 항목중에 r개의 항모을 중복하여 뽑는다면 m^n개의 서로 다른 시퀀스를 만들 수 있다.

123을 가지고 길이가 3인 문자열을 만들면 27개의 문자열을 만들 수 있으며, 111, 112, 113, 121, 122, 123, 131, 132, 133, 211, 212, 213, 221, 222, 223, 231, 232, 233, 311, 312, 321, 322, 331, 333이다.

 

길이가 n인 이진 문자열(2개의 항목으로 만드는 문자열) n개의 원소를 가진 집합의 부분집합 갯수와 같다.

(왜 그럴까???)

 

 

참고 : Programming Challenges : 알고리즘 트레이닝 북