Combination (조합)

조합의 개념

• 조합은 서로 다른 n개의 사물 중에서 r개를 순서에 상관없이 선택하는 경우의 수를 구하는 것을 말한다.
• 조합을 구하는 경우에는 nCr 또는 nCr-r로 표기한다
• 조합을 구하는 방법은 다음과 같다.
• nCr = n! / (r!(n-r)!): n개의 인덱스 중에서 r개를 순서에 상관 없이 선택하는 경우의 수를 계산한다.

구현(재귀)

n = 6
r = 3
arr: [int] = [1,2,3,4,5,6]
result: [int] = []

def combination(n: int, r: int, start: int):
    if len(result) == r:
        print(result)
        return

    for i in range(start,n):
        result.append(i)
        combination(n,r,i+1)
        result.pop()

combination(n,r,0)

구현(반복문)

• 코딩테스트를 볼 때 3개 이하일 경우에 중첩 반복문을 사용한다.
• IDE를 못 쓰거나 자동완성이 없는 경우 재귀를 물론 외우지만 실수할 수 있기 때문이다.

def combination_iterator(n: int, r: int):
    for i in range(n):
        for j in range(i+1, n):
            for k in range(j+1, n):
                print("i: {0}, j: {1}, k: {2}".format(i, j, k))

주의

• 알고리즘을 풀 때 주의해야하는 것이 있다.

• 조합은 서로 다른 n개의 사물 중에서 r개를 순서에 상관없이 선택하는 것이지만

• 알고리즘 문제를 풀 때는 서로다른 n개의 인덱스를 뽑는 것이다.

  arr: [int] = [a,a,a,b,f]

• 상기의 형태로 문제가 주어진다고 해도

• 인덱스만 다르다면 [a,a,b], [a,a,b]도 다를 수 있다.

중복조합

def combination(n: int, r: int, start: int):
    if len(result) == r:
        print(result)
        return

    for i in range(start,n):
        result.append(i)
        combination(n,r,i)
        result.pop()

• 중복조합을 만들려면 combination을 다시 호출하는 부분에서 인덱스를 증가시키지 않으면 된다.
• 재귀로 만드는 combination에서는 start에 +1을 더해주고 호출하는 것의 의미는 뽑은 것은 안 뽑는다는 의미를 갖는다.
• 따라서 +1을 안 하면 나 자신을 포함해서 다시 뽑기 때문에 중복조합을 만들 수 있다.