[알고리즘] 조합(Combination)

조합(Combination)이란?

조합은 주어진 집합에서 특정 개수의 원소를 선택하는 방법을 의미한다. 순서에 상관없이 선택된 원소들로 구성된 집합을 조합이라고 한다. 예를 들어, 집합 {A, B, C, D, E}에서 3개의 원소를 선택하는 경우, 가능한 조합은 {A, B, C}, {A, B, D}, {A, B, E}, {A, C, D}, {A, C, E}, {A, D, E}, {B, C, D}, {B, C, E}, {B, D, E}, {C, D, E}이다.

쉽게 말해 순서가 바뀌어도 연산(혹은 값)이 동일하고 선택해야 하는 개수가 고정되어 있으면(위의 예시로 들자면 개수는 3으로 고정되어 있다.) 조합을 고려해 볼 수 있겠다.

 

 

시간 복잡도

조합 생성의 시간 복잡도는 O(C(C, R) 또는 O(N! / (R! * (N - R)!))이다. 이는 전체 원소 N개에서 R개의 원소를 선택하는 조합의 개수를 나타낸다. 따라서, 조합의 개수는 원소의 개수와 선택할 개수에 따라 결정된다.

 

 

재귀 호출을 활용한 조합 생성

재귀 호출(Recursive Call)은 함수가 자기 자신을 호출하여 문제를 해결하는 방법이다. 조합 생성에서 재귀 호출은 문제를 하위 문제로 나누어 해결하는 데 매우 유용하다. 재귀를 사용하면 복잡한 조합 생성 문제를 더 간단하게 해결할 수 있다.

재귀를 사용한 조합 생성의 기본 원리는 다음과 같다.

1. 기본 상태 확인 : 선택한 원소의 개수가 원하는 개수 R과 같아지면 현재 조합을 출력한다.
2. 재귀 호출 : 각 원소를 선택하거나 선택하지 않고, 재귀적으로 다음 원소에 대해 조합을 생성한다.

 

코드를 통한 이해

import java.util.Arrays;

public class Test03_조합 {
    static int N = 5, R = 3; // N: 전체 원소 개수, R: 선택할 원소 개수
    static String[] cards = {"A", "B", "C", "D", "E"}; // 원소
    static boolean[] select = new boolean[N]; // 각 원소의 선택 여부

    public static void main(String[] args) {
        comb(0, 0); // 조합 생성 시작
    }

    static void comb(int idx, int cnt) {
        if (cnt == R) { // 기본 상태: R개 원소가 선택된 경우
            System.out.println(Arrays.toString(select)); // 현재 조합을 출력
            return;
        }

        if (idx == N) return; // 인덱스가 범위를 넘어선 경우 종료

        select[idx] = true; // 현재 원소를 선택
        comb(idx + 1, cnt + 1); // 다음 원소로 이동, 선택된 원소 개수 증가
        select[idx] = false; // 현재 원소를 선택하지 않음
        comb(idx + 1, cnt); // 다음 원소로 이동, 선택된 원소 개수 유지
    }
}

• 첫 번째 호출 : comb(0, 0)이 호출되면, idx는 0으로 초기화되고, 현재 원소를 포함하거나 포함하지 않는 두 가지 경우를 고려한다.
• 중첩 호출 : comb(idx + 1, cnt + 1)이 호출되면 idx가 증가하고, 선택된 원소의 개수도 1 증가한다. 이 경우는 현재 원소를 선택한 경우이다.
• 기본 상태 도달 : cnt가 R에 도달하면, 원하는 개수의 원소가 선택되었으므로 현재 조합을 출력한다.
• 원소 제외 : comb(idx + 1, cnt)이 호출되면 idx가 증가하지만 선택된 원소의 개수는 유지된다. 이 경우는 현재 원소를 선택하지 않은 경우이다.

 

결론

재귀 호출을 활용한 조합 생성은 각 원소에 대해 선택 여부를 결정하는 간단하고 직관적인 방법이다. 재귀를 통해 모든 가능한 조합을 탐색할 수 있으며, 이 방식은 알고리즘의 이해를 돕고 구현을 용이하게 한다. 하지만 시간 복잡도가 O(C(N, R))로 커질 수 있으므로, 큰 N 또는 R에 대해서는 성능을 고려한 최적화를 고려해 볼 필요가 있다.

 

 

비슷한 유형의 알고리즘들도 같이 정리해 보았다.

2024.07.30 - [ALGORITHM/알고리즘 이론] - [알고리즘] 순열(Permutation)

[알고리즘] 순열(Permutation)

2024.07.30 - [ALGORITHM/알고리즘 이론] - [알고리즘] 부분집합(Subset)

[알고리즘] 부분집합(Subset)