중복조합(重複組合, 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이 된다.   





저작자표시

1
2
3
4
const int num = 10;         // 변수 num을 상수화
const int* ptr1 = &val1;     // 포인터 ptr1을 이용해서 val1의 값을 변경할 수 없음
int* const ptr2 = &val2;     // 포인터 ptr2가 상수화 됨, ptr2의 값을 변경할 수 없음
const int* const ptr3 = &val3;    // 포인터 ptr3가 상수화 되었으며, ptr3를 이용해서 val3의 값을 변경할 수 없음
cs


1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <stdio.h>
 
int val1 = 10;
int val2 = 20;
int main()
{
    const int* ptr1 = &val1;
    int* const ptr2 = &val2;
 
//    (*ptr1) = 20;    // 포인터 ptr1을 이용해서 val1의 값을 변경할 수 없음
    (*ptr2) = 30;
//    ptr2 = &val1;    // ptr2가 가리키는 주소를 변경할 수 없음, 즉 ptr2의 값을 변경할 수 없음
    printf("%d\n", val2);
}
cs


저작자표시
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
// Heap 정렬(내림차순)
 
#include <stdio.h>
#define N 100
 
int n;
int data[N + 1];
int heap[N + 1];
 
void input()
{
    int i;
    scanf("%d", &n);
    for (i = 0; i<n; i++)
        scanf("%d", &data[i]);        // n개의 데이터 입력
}
 
void process()
{
    int i, x;
    int heap_cnt = 1;
 
    for (i = 0; i < n; i++)
    {
        heap[heap_cnt] = data[i];
        x = heap_cnt;
 
        while (x > 1)
        {
            if (heap[x / 2] > heap[x])    // 부모가 자식보다 클 때
            {
                int temp = heap[x / 2];
                heap[x / 2] = heap[x];
                heap[x] = temp;
                x = x / 2;            // 포지션을 부모 자리로 변경
            }
            else break;
        }
        heap_cnt++;
    }
 
    printf("Heap Tree : ");
    for (i = 1; i <= n; i++)
        printf("% d", heap[i]);
    printf("\n");
 
    printf("Output : ");
    for (i = 0; i<n; i++)
    {
        printf("%d ", heap[1]);        // 첫 번째 데이터
        heap_cnt--;                    // 제일 마지막 보다 한 칸 뒤의 위치를 가리키므로 -1
        heap[1] = heap[heap_cnt];    // 제일 첫 번째 칸에다 제일 마지막 자식을 저장
        heap[heap_cnt] = 0;            // 마지막 칸을 비움
        x = 1;                        // 위치는 1
        while (x * 2 < heap_cnt)        // 제일 마지막 자식 까지
        {
            if (heap[x] <= heap[2 * x] && (heap[x] <= heap[2 * x + 1] || x * 2 + 1 >= heap_cnt))        // 부모가 자식보다 작다면
                break;
            else if (heap[x * 2] <= heap[x] && (heap[x * 2] <= heap[x * 2 + 1] || x * 2 + 1 >= heap_cnt))                        // 왼쪽 자식이 제일 작을 때
            {
                int temp = heap[x];
                heap[x] = heap[x * 2];
                heap[x * 2] = temp;                // 제일 작은 자식을 부모자리로 교환
                x = x * 2;
            }
            else // 오른쪽 자식이 제일 작을 때
            {
                int temp = heap[x];
                heap[x] = heap[x * 2 + 1];
                heap[x * 2 + 1] = temp;
                x = x * 2 + 1;
            }
        }
 
    }
    printf("\n");
 
}
 
 
int main()
{
    input();
    process();
}
cs


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
#include <stdio.h>
#define N 10
 
int heap[N + 1];
int sz = 1;
 
void push(int x)
{
    int i = sz++;
 
    while (i > 1)
    {
        // 부모 노드
        int p = i / 2;
 
        // 값의 역전 체크, 없으면 break
        if (heap[p] <= x) break;
 
        heap[i] = heap[p];
        i = p;
    }
    heap[i] = x;
}
 
int pop()
{
    // 최소 값
    int ret = heap[1];
 
    // 루트로 가져오는 값
    int x = heap[--sz];
 
    // 루트보다 작을 동안 값을 체크
    int i = 1;
    while (i * 2 < sz)
    {
        // 자식들을 비교
        int a = i * 2; 
        int b = i * 2 + 1;
        if (b < sz && heap[b] < heap[a]) a = b;
 
        // 더 이상 역전이 없다면 break
        if (heap[a] >= x) break;
 
        // 자식의 값을 저장
        heap[i] = heap[a];
        i = a;
    }
    heap[i] = x;
 
    return ret;
}
cs


저작자표시

+ Recent posts

티스토리툴바