[알고리즘] 재귀-조합(Combination)

💡 조합(Combination)

순열이란 서로 다른 n개 중 r개를 뽑아 그룹을 만드는 가짓수를 말한다. nCr로 표시한다. 사실 순열은 itertools를 이용하면 쉽게 구현할 수 있다. (아래 링크 참고)

[알고리즘] 재귀-순열(Permutation), 백트래킹(Backtracking)

1. 일반 조합

# 4개의 원소 중에 3개를 중복, 순서 없이 뽑는 경우의 수

# 1. 매개변수 1개만 사용
arr=['a','b','c','d']
path=['']*3

def abc(level):
    if level==3:
        print(*path)
        return

    for i in range(4):
        #1 path[level-1] -> 그전 단계에서 타고 들어온 곳
        #2 arr[i] -> 앞으로 들어갈 가지
        #3 그전 들어온 가지 < 앞으로 들어갈 가지  (True)
        if level > 0 and path[level-1] >= arr[i]: continue
        path[level]=arr[i]
        abc(level+1)

abc(0)

# 2. 매개변수 2개 사용 
arr=['a','b','c','d']
path=['']*3

def abc(level,start):
    if level==3:
        print(*path)
        return

    for i in range(start,4):
        path[level]=arr[i]
        abc(level+1,i+1)

abc(0,0)  #level start

출력
a b c
a b d
a c d
b c d

1. 중복 조합

# 4개의 원소 중에 3개를 순서 없이 뽑는 경우의 수 (중복 가능)
arr=['a','b','c','d']
path=['']*3

def abc(level,start):
    if level==3:
        print(*path)
        return

    for i in range(start,4):
        path[level]=arr[i]
        abc(level+1,i) # aad -> abb로 넘어가는 로직 이해를 확실히 하자!(조합)

abc(0,0)  #level start

• 조합을 활용한 문제💡
  • 백준 N과 M (3)
  • 백준 암호 만들기