조합(combination)

조합론에서 조합은 서로 다른 n개의 원소를 가지는 어떤 집합에서 순서에 상관없이 r개의 원소를 선택하는 것이며, 이는 n개의 원소로 이루어진 집합에서 r개의 원소로 이루어진 부분집합을 만드는 것 혹은 찾는 것과 같다.(위키백과)

조합의 개수 공식: 위키백과_{수식이 잘 들어가지 않아서 링크로 대체..}

조합의 경우의 수 계산은 위 식과 같으며, 이항 계수라고 한다. 먼저 n개의 정수 중에 k개를 고르는 경우를 코드로 구현해 보자

  
import java.util.Arrays;

public class Comb {
    static int[] visit; // 인덱스 방문처리를 위한 배열
    static int[] arr; // 고를 배열
    static int n; // 배열의 길이

    public static void main(String[] args) {
        arr = new int[]{1, 2, 3, 4, 5};
        n = arr.length;

        visit = new int[arr.length]; // static으로 선언된 visit을 초기화
        comb(3, 0); // 조합 시작
    }

    private static void comb(int pick, int depth) { // 고를 개수, 재귀로 들어간 깊이
        if (pick == 0) { // 더 이상 고를 수 없는 경우
            System.out.println(Arrays.toString(visit));
            return;
        }
        if (depth == n) return; // 깊이는 0부터 n-1까지이므로 n이면 탈출
        visit[depth] = 1; // 현재 보는 인덱스를 방문처리
        comb(pick - 1, depth + 1); // 고를 개수 하나 줄이면서 재귀
        visit[depth] = 0; // 현재 인덱스에서 다 골랐으면 초기 상태로 돌아가기
        comb(pick, depth + 1); // 다시 고를 개수 , 깊이 +1로 재귀
    }
}

재귀로 구현한 조합이다. comb()함수는 고를 개수 pick과 몇번 재귀를 도는지 확인할 depth가 입력으로 주어진다.

pick: 3 depth: 0으로 comb 함수를 호출
visit[0] = 1 방문처리 visit=[1,0,0,0,0] pick: 2 depth: 1 comb 호출
visit[1] = 1 방문처리 visit=[1,1,0,0,0] pick: 1 depth: 2 comb 호출
visit[2] = 1 방문처리 visit=[1,1,1,0,0] pick: 0 depth: 3 comb 호출
pick: 0조건으로 visit 출력 후 반환 (pick과 depth는 3번 상태)
visit[2] = 0 초기화 visit=[1,1,0,0,0] pick: 1 depth: 3 comb 호출
visit[3] = 1 방문처리 visit=[1,1,0,1,0] pick: 0 depth: 4 comb 호출
pick: 0조건으로 visit 출력 후 반환 (pick과 depth는 6번 상태)
visit[3] = 0 초기화 visit=[1,1,0,0,0] pick: 1 depth: 4 comb 호출
visit[4] = 1 방문처리 visit=[1,1,0,0,1] pick: 0 depth: 5 comb 호출
pick: 0조건으로 visit 출력 후 반환 (pick과 depth는 9번 상태)
visit[4] = 0 초기화 visit=[1,1,0,0,0] pick: 1 depth: 5 comb 호출
depth == n(5) 로 탈출조건 만족, 반환
visit[1] = 0 초기화 visit=[1,0,0,0,0] pick: 2 depth: 2 comb호출
반복

위 코드를 따라가 보았다. 디버깅 도구를 사용해 한 라인씩 실행시켜보았다.

visit 배열에 방문하면서 고른 인덱스를 1로 만들어 주고 모두 고르면 pick==0의 조건에서 생성된 하나의 조합에 대해 원하는 동작을 구현하면 된다.

위 코드는 pick이 3인 경우의 동작만을 실행하지만, 반복문을 사용해 개수별로 원하는 조합을 만들어 낼 수 있다.

조금 더 간단한 조합 구현하기

위 코드에서는 visit 배열을 사용해서 단순히 인덱스가 선택되었는지 확인할 수 있는 코드였다. 이번에는 주어진 배열에서 값을 직접 조합하여 출력하는 방식으로 구현해 볼 것이다.

  
import java.util.Arrays;
import java.util.Scanner;

public class Combination {
    static int N, R, totalCnt;
    static int[] numbers, input;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        N = sc.nextInt();
        R = sc.nextInt();

        input = new int[N];
        numbers = new int[R];

        for (int i = 0; i < N; i++) {
            input[i] = sc.nextInt();
        }
        comb(0, 0); // start : 뽑은 개수

    }

    // cnt+1 번째 해당하는 조합에 포함될 수 뽑기
    static void comb(int cnt, int start) {
				// cnt: 직전까지 뽑은 조합에 포함된 수의 개수,
				// start: 시도할 수의 시작 위치
        if (cnt == R) {
            totalCnt++;
            System.out.println(Arrays.toString(numbers));
            return;
        }

        // 가능한 모든 수에 대해 시도 (input 배열의 가능한 수 시도)
        // start 부터 처리시 중복 수 추출 방지 및 순서가 다른 조합 추출 방지
        for (int i = start; i < N; i++) { // 선택지
            // start 위치부터 처리했으므로 중복 체크 필요 없다
            // 양쪽에서 선택되지 않았다면 수를 사용
            numbers[cnt] = input[i];
            // 다음 수 뽑으러 가기
            comb(cnt + 1, i + 1);
        }
    }
}

cnt는 만들어진 조합에 포함된 수의 개수이고, start는 어느 숫자부터 시작할 것인지 정한다. 조합은 이미 봤던 수에 대해서는 추가할 필요가 없기 때문에 반복문의 i는 start부터 시작한다.

조합에 포함된 개수가 뽑고 싶은 개수를 만족 하는 경우 원하는 동작을 하게 한다. 5개의 수에서 3개를 고르는 조합이 생성되는 순서를 확인해 보자

처음 comb(cnt=0, start=0)으로 시작
[for] i=0 N까지 numbers[0] = input[0] 배열의 첫 번째 원소를 선택 [1, 0, 0]
comb(cnt=1, start=1) 으로 재귀
[for] i=1 N까지 numbers[1] = input[1] 배열의 두 번째 원소 선택 [ 1, 2, 0]
comb(cnt=2, start=2) 으로 재귀
[for] i=2 N까지 numbers[2] = input[2] 배열의 세 번째 원소 선택 [1, 2, 3]
comb(cnt=3, start=3) 으로 재귀
cnt = R(3) 조건 만족, 원하는 동작 이후 반환
6번 [for]로 돌아가 i=3이 되고, numbers[2] = input[3] 배열의 네 번째 원소 선택 [1, 2, 4]
comb(cnt=3, start=4) 으로 재귀
8과 동일하게 cnt=R(3) 조건 만족, 원하는 동작 이후 반환
위 과정을 반복

이항계수 문제 예시

문제에서 요구하는 것이 조합의 개수인 경우 이항계수를 사용해 쉽게 구할 수 있다. DP와 이항계수로 풀 수 있는 다리놓기 문제를 풀 것이다.

다리놓기

문제 보러가기: 1010 다리 놓기

간단하게 문제를 설명하면, 강의 서쪽과 동쪽을 연결할 다리를 놓아야 하는데, 서쪽 사이트는 동쪽 사이트보다 작다. 서쪽을 n, 동쪽을 r로 생각하고, $_nC_r$을 구하면 된다.

첫 시도에서 팩토리얼 함수를 구현해 구하려 했지만, 시간초과가 발생했다. 이 문제는 이항계수를 사용해 해결하였다.

  
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    static int n, m;
    static long[][] dp;

    public static void main(String[] args) throws IOException {

        int testcase = Integer.parseInt(br.readLine());
        for (int t = 0; t < testcase; t++) {
            int[] array = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
            n = array[0];
            m = array[1];
            dp = new long[m + 1][m + 1];
            // dp[i][j] = iCj 이항 계수 공식 = dp[i][j] = dp[i-1][j-1] + dp[i-1][j]
            // dp[i][i] = 전체 중에 전체를 꺼내는 경우 = 1
            // dp[i][0] = 아예 안꺼내는 경우 = 1
            for (int i = 0; i < m; i++) {
                dp[i][i] = 1;
                dp[i][0] = 1;
            }
            dp[1][1] = 1;

            for (int i = 2; i < m + 1; i++) {
                dp[i][1] = i;
                for (int j = 1; j < n + 1; j++) {
                    dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
                }
            }
            System.out.println(dp[m][n]);
        }
        for (int i = 0; i < dp.length; i++) {
            for (int j = 0; j < dp[0].length; j++) {
                System.out.print(dp[i][j] + " ");
            }
            System.out.println();
        }
    }
}

DP 테이블을 생성한 다음 이항 계수 공식을 사용하여 해결한다. [i, i]와 [i, 0], [1, 1]의 경우는 한 가지 방법만 존재하므로, 1로 만들어 준 후 나머지 테이블에 대해 공식을 적용해 준다.

모든 테이블에 수식을 적용한 후 문제에서 주어진 n, r 좌표 값에 해당하는 테이블 값이 만들 수 있는 조합의 수이다.

순열

순열은 순서가 부여된 임의의 집합을 다른 순서로 뒤섞는 연산이다. (위키백과)

\[P(n,k)=n(n-1)\cdots (n-k+1)\]

위 공식은 n개의 원소에서 k개의 원소를 골라 배열하는 방법의 수를 계산하는 식이다. 원하는 개수의 순열을 구하는 코드를 구현해 보자.

  
import java.util.Arrays;

public class Prem2 {
    static int n, r, totalCount;
    static int[] numbers, input;
    static boolean[] isSelected;

    // nPr : 1부터 n까지의 수 중 n개를 모두 뽑아 순서적으로 나열한 것
    public static void main(String[] args) {
        n = 3;
        r = 3;
        totalCount = 0;
        input = new int[n];
        numbers = new int[r];
        isSelected = new boolean[n];
        for (int i = 0; i < n; i++) {
            input[i] = i;
        }
        perm(0);
    }

    private static void perm(int cnt) { // cnt+1 번째 해당하는 수를 뽑기
        if (cnt == r) {
            totalCount++;
            System.out.println(Arrays.toString(numbers));
            return;
        }
        // 가능한 모든 수에 대해 시도
        for (int i = 0; i < n; i++) {
            // 시도하는 수가 선택되었는지 판단
            if (isSelected[i]) continue;
            // 선택되지 않았다면 수를 사용
            numbers[cnt] = input[i];
            isSelected[i] = true;
            // 다음 수 뽑으러 가기
            perm(cnt + 1);
            // 사용했던 수에 대해 선택을 되돌려 놓기
            isSelected[i] = false;
        }
    }
}

numbers라는 빈 배열에 주어진 배열의 값들을 하나씩 탐색하면서 순열을 만들어 낸다. cnt를 새로 생성할 배열의 인덱스로 사용한다. visit 배열에 방문 여부를 확인하면서 새로운 배열을 만들어 간다.

조합과 유사하게 재귀를 돌면서 방문한 인덱스 값을 새 배열에 넣어두고 고를 개수 r개를 만족하게 되면 원하는 동작을 구현하면 된다.

부분 집합 구현하기

부분집합은 주어진 배열에서 고를 수 있는 모든 경우의 상태를 만들어 내는 것이다. 아무것도 뽑지 않는 경우부터 모든 배열을 뽑는 경우까지를 만들어 낸다.

  
import java.util.Arrays;
import java.util.Scanner;

public class Subset {

    static int N, totalCnt;
    static int[] input;
    static boolean[] isSelected;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        N = sc.nextInt();

        totalCnt = 0;
        input = new int[N];
        isSelected = new boolean[N];

        for (int i = 0; i < N; i++) {
            input[i] = sc.nextInt();
        }

        subset(0);

    }

    static void subset(int index) {
				// index : 부분집합에 고려할 대상
        if (index == N) {
						// 더 이상 고려할 원소가 없다면 부분 집합의 구성이 완성
            for (int i = 0; i < N; i++) {
                System.out.print(isSelected[i] ? "o" + " " : "x" + " ");
            }
            System.out.println();
            return;
        }

        // 원소 선택
        isSelected[index] = true;
        subset(index + 1);
        // 원소 미선택
        isSelected[index] = false;
        subset(index + 1);
    }
}

부분집합이 생성되는 과정을 알아본다

subset(index=0)으로 시작
isSelected[0] = true 첫 인덱스 선택 subset(index=1) 로 재귀
isSelected[1] = true 두 번째 인덱스 선택 subset(index=2) 로 재귀
isSelected[2] = true 세 번째 인덱스 선택 subset(index=3) 로 재귀
index가 5가 될 때(모든 수 선택)까지 진행
index == N 인 경우 하나의 부분집합 완성, 원하는 동작 후 반환
isSelected[4] = false 다섯 번째 인덱스 초기화 subset(index=5) 로 재귀 (원소 미선택)
index == N으로 원하는 동작 후 반환 [true, true, true, true, false]
isSelected[3] = false 네 번째 인덱스 초기화 subset(index=4) 로 재귀 (원소 미선택)
isSelected[4] = true 다섯 번째 인덱스 선택 subset(index=5) 로 재귀 (원소 선택)
index == N으로 원하는 동작 후 반환 [true, true, true, false, true]
isSelected[4] = false 다섯 번째 인덱스 초기화 subset(index=5) 로 재귀 (원소 미선택)
index == N으로 원하는 동작 후 반환 [true, true, true, false, false]
모든 원소를 선택하지 않을 때까지 반복

위 코드를 눈으로 보기만 하면 직관적으로 다가오지 않아 디버깅 도구를 사용해 한 줄씩 실행해 보며 따라가 보았다.

index가 N을 만족하는 경우 하나의 부분 집합이 생성된 것이고, 동작이 끝나고 반환하게 되면 원소 미선택 부분이 실행되고, 이 부분에서 index가 N을 만족하면 다시 원소 미선택 실행, index가 N을 만족하지 않으면 원소 선택 부분이 실행된다.

재귀는 순열이나 조합에서도 꾸준히 나오지만 조건을 만족한 후 반환되고 어느 단계로 돌아가는지 확인 하는 것이 매우 중요하다고 생각한다.

조합과 순열을 자바로 구현해 보자

조합(combination)

조금 더 간단한 조합 구현하기

이항계수 문제 예시

다리놓기

순열

부분 집합 구현하기

Further Reading

그래프 자료구조 정리 (프림, 크루스칼, 다익스트라)

병합 정렬, 삽입 정렬 (Python Algorithm interview 17장)

이진 탐색 (Python Algorithm interview 18장)