2021-02-10

조합(Combination)

조합(Combination)도 재귀적으로 구현하는 게 가장 편하다. 다음처럼 접근해보자.
written by

Introduction

이번에는 조합(Combination)을 구하는 방법에 대해서 알아보자. 우선 조합의 개수를 구하는 수식을 보자.

  • nCr = nPr/r!

이 수식이 의미하는 바는 무엇인가?

5개의 당구공이 있는데 3개를 골라내야 한다면 다음과 같이 골라낼 수 있을 것이다.

  • 남은 5개의 당구공에서 한 개를 골라내는 5가지 선택지가 있다.
  • 남은 4개의 당구공에서 한 개를 골라내는 4가지 선택지가 있다.
  • 남은 3개의 당구공에서 한 개를 골라내는 3가지 선택지가 있다.

여기까지는 순열의 개수이다. 하지만 골라낸 개수에 따라서 중복되는 개수가 생긴다. 당구공 3개를 골랐을 때 중복되는 개수는 다음과 같은 과정으로 구할 수 있다.

  • 남은 3개의 당구공 중에 하나를 고르는 경우의 수는 3가지이다.
  • 남은 2개의 당구공 중에 하나를 고르는 경우의 수는 2가지이다.
  • 남은 1개의 당구공 중에 하나를 고르는 경우의 수는 1가지이다.

순열(nPr)에서 중복되는 개수(r!)만큼으로 나누면 조합(nCr)을 구할 수 있는 것이다.

Algorithm

조합(Combination)도 재귀적으로 구현하는 게 가장 편하다. 다음처럼 접근해보자.

  • 당구공을 고르고 남은 개수를 줄이고 남은 당구공에서 남은 개수만큼 선택한다.
  • 혹은 당구공을 고르지 않고 남은 개수를 줄이지 않고 남은 당구공에서 선택한다.

만약 특정 개수에 대한 조합만 구하고 싶다면 재귀 함수를 특정 개수의 깊이만큼만 호출하고 종료하면 된다. 순열과 조합은 비슷한 방식으로 구해지기 때문에 코드도 비슷할 수밖에 없다.

Kotlin Scratch Code

// depth == 선택할 수 있는 당구공의 개수.
fun combination(balls: List<Int>, index: Int = 0, depth: Int = balls.size, combination: String = "") {
    if (index == balls.size) {
        if (depth == 0) println(combination.toList())
    } else {
        combination(balls, index + 1, depth - 1, combination + balls[index])
        combination(balls, index + 1, depth, combination)
    }
}

// [1, 2, 3]이라는 3개의 당구공 중에서 2개의 당구공으로 구할 수 있는 모든 조합을 출력한다.
combination(listOf(1, 2, 3), depth = 2)

Result

[1, 2]
[1, 3]
[2, 3]
2021 © Cinntiq's Studio