전체 집합의 원소 갯수가 14인데
모든 원소끼리 1대1로 비교해야 한다
그런데 프로그램을 이용해
한번에 7개의 원소를 갖는 부분집합을 만들어 비교할 수 있다.
그렇다면 모든 경우를 비교 하는데
필요한 최소 시행횟수의 부분집합 조합은 어떻게 되는가?
ex)만약 한번에 2개씩만 비교할 수 있다면
전체 집합에서 91번의 비교를 시행해야
모든 경우를 비교가능하다
하지만 7개를 한번에 비교할 수 있으므로
전체 집합이 {1~14}라 칠 때
{1,2,3,4,5,6,7}의 부분집합을 만든 경우
1:2
1:3
1:4
1:5
1:6
1:7
2:3
2:4
2:5
2:6
2:7
3:4
3:5
3:6
3:7
4:5
4:6
4:7
5:6
5:7
6:7
처럼 한번에 총 21번의 비교가 가능하다
이때 {1~14} 전체 집합 모든 원소들 끼리 비교할때
최소한의 시행으로 모든 경우를 비교할때 필요한 조합이란 뜻
일단 문제를 가장 간단한 형태로 기술할 필요가 있음 Si : i번째 시행에서 잡힌 원소 7개의 집합. A : 1 부터 14까지 집합 P(X) : 집합 X를 2개씩 묶어서 만든 집합. Union P(Si) >= P(A). 이런 Si 의 개수를 최소화 한다는 건데.
상식적으로 P(Si) 구조를 P(A) 와 비교하는 건 어려움. 원래 분할 문제는 쉬운 문제가 아님. 그래서 최소 시행 횟수를 찾기 보다는 적당히 구현가능한 알고리즘을 만드는게 중요함.
일단 먼저 1부터 14까지 집합을 1, 2, 3, ... , 14 까지 대응한 후. 이를 2의 거듭제곱이 될 때까지 늘려봄. (빈 공간) 1, 2, 3, ..., 14, 15(), 16()
그 후 홀수와 짝수를 분할. S1: 1, 3, 5, 7, 9, 11, 13, 15() S2: 2, 4, 6, 8, 10, 12, 14, 16()
이제 이걸 다시 번호를 메김. S1: 1, 2, 3, 4, 5, 6, 7, 15() S2: 8, 9, 10, 11, 12, 13, 14, 16() 이걸 홀수와 짝수로 분할하면 S3: 1, 3, 5, 7, 9, 11, 13, 15() S4: 2, 4, 6, 8, 10, 12, 14, 16() 이런 식으로 계속 시도해서 되는지 안되는지 예제로 판단하는게 중요
즉. 번호를 다시 메기면 S1: 1, 3, 5, 7, 9, 11, 13 S2: 2, 4, 6, 8, 10, 12, 14 S3: 1, 5, 9, 13, 4, 8, 12 S4: 3, 7, 11, 2, 6, 10, 14 이렇게 되는데... 근데 여기서부터 알고리즘을 확장하기 힘드니. 적당히 처리해야 할듯.
생각보다 디게 어려운 문제였네