저작자표시

중복조합(重複組合, combination with repetition)은 서로 다른 n개의 원소에서 중복을 허락하여 k개를 뽑는 경우의 수이다. 


기호로는 nHk로 표기하며, 그 값은 nHk = n+k-1Ck 이다.


예를 들어, 세개의 문자 A,B,C에서 중복을 허용하여 5개를 뽑는 경우의 수는 3H5 = 7C5 = 21이므로 21가지가 된다.


공식을 유도하자면, 중복조합 nHk는 k개의 원소들을 중복을 허용하여 순서에 상관없이 나열하는 것으로 볼 수 있다.


따라서 k개의 빈칸에 중복을 허용하여 n개의 원소(n개 종류의 원소)를 넣는 개수를 구하는 문제로 생각할 수 있다.


이 떄, n가지의 원소를 순서에 상관없이 나열해야 하므로, n - 1개의 칸막이를 두고 나열하는 것으로 생각할 수 있다.


예를 들어, A,B,C 세개의 문자에서 중복을 허용하여 5개를 뽑는 경우의 수를 생각해보자.


1.  A A A A A / /

2.  A A A A / B

3.  A A A / B B /

4.  A A / B B B /

5.  A / B B B B /

6.  B B B B B / /

7.  / B B B B / C

8.  / B B B / C C 

9.  / B B / C C C

10. / B / C C C C 

11. / / C C C C C

12. A A A A / / C

13. A A A / / C C

14. A A / / C C C 

15. A / / C C C C

16. A / B / C C C

17. A / B B / C C

18. A / B B B / C

19. A A / B / C C

20. A A A / B / C

21. A A / B B / C


이런식으로 총 k + n - 1 개의 칸에서 n - 1개의 칸막이를 배치하는 경우의 수로 생각할 수 있다.

따라서 nHk = n+k-1Cn-1 = n+k-1Ck가 된다. 따라서 위의 예는 n = 3이고, k = 5 이므로 3H5 = 3+5-1C5 = 7C5 = 7C2 = 21이 된다.   





저작자표시

크루스칼 알고리즘은 최소신장트리(Minimum Spanning Tree)를 구하는 알고리즘이다.



최소신장트리는 위의 그림과 같이 어떤 그래프가 있을 때, 각 노드들을 최소 비용으로, 트리 구조로 연결한 것을 말한다. 트리는 (노드의 수 - 1)개의 간선을 갖고, 싸이클이 생기지 않는 구조를 갖는다.


크루스칼 알고리즘의 순서는 다음과 같다.


1. 간선(Edge)을 비용이 적은 순서대로 정렬한다.

2. 정렬된 간선을 순서대로 추가하는데, 이 때 싸이클이 생기지 않도록 하는 간선만 추가한다.

3. 이를 간선의 수가 노드의 수 - 1 개가 될 때까지 반복한다.


어떤 간선을 추가했을 때 싸이클이 생기는지의 여부는 Disjoint sets(분리집합, 상호배타적집합)을 이용한다. Disjoint sets를 표현하기 위한 자료구조로 disjoint-set data structure를 이용한다. (union–find data structure, merge–find set 라고도 불린다.)


 



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
#include <stdio.h>
#include <malloc.h>
 
#define N 100
 
int distance[N][N];
int n;
int p[N];
int rank[N];
int sum;
 
typedef struct Edge
{
    int x, y, k;
}Edge;
 
Edge edge[N * N];
int cnt;
 
int FindSet(int x)
{
    if (p[x] == x) return x;
    else p[x] = FindSet(p[x]);
}
 
void CreateSet()
{
    for (int i = 0; i < N; i++)
    {
        p[i] = i;
        rank[i] = 0;
    }
}
 
void MergeSet(int x, int y)
{
    x = FindSet(x);
    y = FindSet(y);
 
    if (rank[x] > rank[y])
    {
        p[y] = x;
    }
    else
    {
        p[x] = y;
        if (rank[x] == rank[y]) rank[y]++;
    }
 
}
 
void Merge(Edge *arr, int left, int mid, int right)
{
    int l_idx = left;
    int r_idx = mid + 1;
    int idx = left;
    Edge *temp = (Edge *)malloc(sizeof(Edge) * (right + 1));
 
    while (l_idx <= mid && r_idx <= right)
    {
        if (arr[l_idx].k > arr[r_idx].k) temp[idx++] = arr[r_idx++];
        else temp[idx++] = arr[l_idx++];
    }
 
    while (l_idx <= mid) temp[idx++] = arr[l_idx++];
    while (r_idx <= right) temp[idx++] = arr[r_idx++];
 
    for (int i = left; i <= right; i++) arr[i] = temp[i];
    free(temp);
}
 
void MergeSort(Edge *arr, int left, int right)
{
    if (left < right)
    {
        int mid = (left + right) / 2;
        MergeSort(arr, left, mid);
        MergeSort(arr, mid + 1, right);
        Merge(arr, left, mid, right);
    }
}
 
int main()
{
    int i, j;
 
    //freopen("input.txt", "r", stdin);
 
    scanf("%d", &n);
    for (i = 0; i < n; i++)
        for (j = 0; j < n; j++)
            scanf("%d", &distance[i][j]);
    
    for (i = 0; i < n; i++)
    {
        for (j = 0; j < n; j++)
        {
            if (j > i)
            {
                edge[cnt].x = i;
                edge[cnt].y = j;
                edge[cnt++].k = distance[i][j];
            }
        }
    }
 
    MergeSort(edge, 0, cnt);
    CreateSet();
 
    i = j = 0;
    
    while (i < n - 1)
    {
        int u = FindSet(edge[j].x);
        int v = FindSet(edge[j].y);
 
        // 싸이클이 안생길 떼
        if (u != v)
        {
            MergeSet(u, v);
            sum += edge[j].k;
            i++;
        }
        j++;
    }
    printf("%d\n", sum);
 
    return 0;
}
cs


저작자표시

+ Recent posts

티스토리툴바