조합 (Combination)

재귀, 순열, 순열과 조합의 차이는 정리했었는데 조합에 대해 정리한 글이 없다는 것을 지금 알게되어 늦게나마 정리를 해본다..🌱

조합 (Combination)

조합 (Combination) ?

👉 서로 다른 n개의 원소 중 r개를 순서 없이 골라낸 것

 

 

조합의 수식

조합의 수식

재귀함수 적용 가능

nCr은 n개의 원소 중에 r개를 선택한다는 의미이며, 이는 n-1개의 원소 중 r-1개를 선택한 경우의 수와 n-1개의 원소 중 r개를 선택하는 경우의 수를 합친 것과 같음

즉, nCr = n-1Cr-1 + n-1Cr 이므로 재귀함수를 적용할 수 있음

 

재귀함수를 모른다면 밑의 링크를 참고해보자.

재귀 함수 👉 https://ichijeochi.tistory.com/11

재귀 (Recursive)

 

n개의 원소 중 0개를 선택하는 경우

조합 수식에서 nC0은 n개 중 0개를 선택한다는 의미로, 한 개의 원소도 선택하지 않는 경우는 1가지 이므로 답은 1

n개의 원소 중 n개를 선택하는 경우

조합 수식에서 nCn은 n개 중 n개 모두를 선택한다는 의미로, 모두 선택하는 경우는 1가지이므로 답은 1

 

💡 Tip

nCr에서 경우의 수는 r이 n의 절반 즉, 2/n에 가까울수록 큼

 

 

조합으로 풀 수 있는지 판단하기

ex) n = 30, r = 15 (1 <= r <= n)

30C15는 155117520 즉, 1억 5천개 이상의 경우의 수가 나옴. 이 경우에는 탐색의 시간이 너무 오래걸리게 되어 조합이 아닌 다른 풀이 방법으로 풀어야 함

 

 

조합을 생성하는 방법

1️⃣ 반복문을 이용한 조합 생성 알고리즘 (pseudocode)
ex) n = { 1, 2, 3, 4, 5 }이고 r = 3일 때의 조합 즉, 5개의 원소 중 3개를 뽑는 경우의 수

 for i from 1 to 5  // 첫번째로 뽑는 수
     for j from i+1 to 5  // 두번째로 뽑는 수
        for k from j+1 to 5  // 세번째로 뽑는 수
             print i, j, k
        end for
    end for
end for

슈도코드를 이해하기 위해 밑의 그림을 참고해보자.

1️⃣ i가 1일 때, i+1인 2부터 5까지의 값이 j에 들어갈 수 있으며, i가 2일 때는 j+1인 3부터 5까지의 값이 k에 들어갈 수

    있음

2️⃣ i가 2일 때, i+1인 3부터 5까지의 값이 j에 들어갈 수 있으며, i가 3일 때는 j+1인 4부터 5까지의 값이 k에 들어갈 수

    있음

    👉 j나 k에 1이 나오는 경우는 위의 1️⃣에서 뽑은 경우들과 중복되어 이를 방지하기 위해 i+1부터 반복문 진행

    👉 또한, j에 5가 나오는 경우는 k가 j+1인 6부터 시작해야 하지만 배열에 없는 원소이므로 j에는 5가 들어갈 수 없음

3️⃣ i가 3일 때, i+1인 4부터 5까지의 값이 j에 들어갈 수 있으며, i가 4일 때는 j+1인 5가 k에 들어갈 수 있음

     👉 j가 5인 경우는 k가 j+1인 6부터 시작해야 하지만 배열에 없는 원소이므로 j에는 5가 들어갈 수 없음

반복문을 이용한 조합 생성 알고리즘 설명

👉 중첩 반복문의 개수는 nCr에서 r만큼 중첩

 

2️⃣ 재귀 호출을 이용한 조합 생성 알고리즘 (pseudocode)

nCr 👉 n개의 원소 중 r개 원소를 갖는 조합 생성
input[] : n 개의 원소를 가지고 있는 배열
numbers[] : r개의 크기의 배열, 조합이 저장될 배열

comb(cnt, start)  // cnt : 현재까지 뽑은 조합 원소 개수, start: 조합을 시도하는 원소의 시작 인덱스
    if cnt == r  // 내가 뽑고 싶은 개수 r만큼 모두 뽑으면 return
        조합 생성 완료
    else
        for i from start to n-1  // 반복이 되는 과정에서 중복 상황과 같은 수가 선택이 되는 경우가 걸러짐
            numbers[cnt] ← input[i];
            comb(cnt+1, i+1);
        end for
end comb()