『Do it! 알고리즘 코딩 테스트 with JAVA 강의』를 듣고 정리한 글입니다.

순열과 조합 (Combination)

조합은 그 자체로 코딩 테스트에 자주 출제되는 주제이며, 동적 계획법을 이해하는데 기초가 된다.

• 조합은 $_nC_r$으로 표현하며, n개의 숫자에서 r개를 뽑는 경우의 수를 뜻한다.
• 순열은 $_nP_r$로 표현하며, n개의 숫자 중 r개를 뽑아 순서를 고려해 나열할 경우의 수를 말한다.
• 순열과 조합의 차이는 순서의 고려 유무이다.
  • 조합에서는 1, 2, 3과 3, 2, 1을 같은 경우로 판단한다.
  • 순열에서는 1, 2, 3과 3, 2, 1을 다른 경우로 판단한다.

핵심 이론

순열

• 순열의 수학적 공식은 다음과 같다.

• 예를 들어, 5개 중 3개를 순서대로 선택하는 경우의 수는 다음과 같다.
  • 첫 번째 선택은 5개를 선택할 수 있고, 두 번째 선택은 4개를 선택할 수 있고, 세 번째 선택은 3개를 선택할 수 있다.
  • 따라서 경우의 수는 $5*4*3=60$가지가 된다.

조합

• 조합의 수학적 공식은 다음과 같다.
  • $r!$은 순서가 다른 경우의 수를 제거하는 역할을 한다.

• 예를 들어, 5개 중 2개를 선택하는 경우의 수를 구한다고 가정하자.
  • 경우의 수는 $5*4/2=10$가지가 된다.

조합의 점화식

알고리즘에서 조합을 구현할 때는 수학 공식을 코드화하는 것이 아니라, 점화식을 사용해 표현한다.

조합의 점화식은 다음 3가지 단계로 세울 수 있다.

1. 특정 문제를 가정하기

   • 예를 들어, 5개의 데이터에서 3개를 선택하는 조합의 경우의 수를 푸는 문제로 가정한다.

2. 모든 부분 문제가 해결된 상황이라고 가정하고 지금 문제 생각하기

   • 먼저 5개의 데이터 중 4개를 이미 선택이 완료된 데이터라고 가정하고, 마지막 데이터의 선택 여부에 따른 경우의 수를 계산한다.
   • 다음 2가지 경우의 수를 합치면 데이터 5개 중 3개를 선택하는 경우의 수가 나온다. 1) 마지막 데이터를 포함해 총 3개의 데이터를 선택하려면, 이미 선택이 완료되었다고 가정한 4개의 데이터에서 2개를 선택해야 한다. 2) 마지막 데이터를 포함하지 않고 총 3개의 데이터를 선택하려면, 이미 선택이 완료되었다고 가정한 4개의 데이터에서 3개를 선택해야 한다.
     
   $_5C_3\ =\ _4C_3\ +\ _4C_2$

   // 5개 중 3개를 선택하는 경우의 수 점화식
   D[5][3] = D[4][3]+D[4][2]

3. 특정 문제를 해결한 내용을 바탕으로 일반 점화식 도출하기

   • 이렇게 일반화된 점화식을 이용하면 조합과 관련된 모든 경우의 수를 쉽게 구할 수 있다.

   D[i][j] = D[i-1][j]+D[i-1][j-1]

이항계수 구하기 (백준 11050)

❓ 자연수 N과 정수 K가 주어졌을 때 이항 계수 $\binom{N}{K}$를 구하는 프로그램을 작성하시오.

문제 풀이

private static void answer() throws IOException {
    Scanner sc = new Scanner(System.in);
    int N = sc.nextInt();
    int K = sc.nextInt();
    int D[][] = new int[N+1][N+1];

    // 초기화
    for (int i = 0; i <= N; i++) {
        D[i][i] = 1;
        D[i][0] = 1;
        D[i][1] = i;
    }

    // 점화식으로 배열 완성하기
    for (int i = 2; i <= N; i++) {
        for (int j = 1; j < i; j++) {
            D[i][j] = D[i-1][j] + D[i-1][j-1];
        }
    }

    System.out.println(D[N][K]);
}

Reference

[지금 무료] Do it! 알고리즘 코딩테스트 with JAVA 강의 - 인프런