조합은 수를 세는 것에 관한 수학
기초적인 셈
곱의 법칙
집합 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 : 알고리즘 트레이닝 북
'Prog&Algol' 카테고리의 다른 글
Algo | C++ | DFS and BFS (0) | 2022.03.30 |
---|---|
BJ | 2178 | BFS shorted path (0) | 2022.03.30 |
C++ | history of Class (0) | 2022.03.30 |
C++ | Namespace (0) | 2022.03.29 |
BJ | 9996 | connect server when missing Korea (0) | 2022.03.29 |