재귀 알고리즘 응용

플랫폼: 프로그래머스
강의명: 어서와! 자료구조와 알고리즘은 처음이지?
강사명: 이시윤

---

조합의 수

서로 다른 n개의 원소 중 r개를 택하는 방법
nCr = $n! \over r!(n-r)!$

1) math 활용

from math import factorial as f


def combi(m: int, n: int) -> int:
    return f(m) // ((f(m-n)) * f(n))


res = combi(5, 2)
print(res)

2) 간접적 재귀 알고리즘

"""
서로 다른 n개의 원소 중 r개를 택하는 경우의 수
"""


def get_factorial_by(N: int) -> int:
    if N <= 1:
        return N
    return N * get_factorial_by(N-1)


def get_nCr(n: int, r: int) -> int:
    return get_factorial_by(n) // (get_factorial_by(n-r) * get_factorial_by(r))


res = get_nCr(5, 2)
print(res)

3) 직접적 재귀 알고리즘

def combi(m: int, n: int) -> int:
    if m == n:
        return 1
    elif m <= 0:
        return 1
    else:
        return combi(m-1, n) + combi(m-1, n-1)


res = combi(5, 3)
print(res)