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

💡 순열(Permutation)

순열이란 서로 다른 n개 중 r개를 골라 순서를 고려해 나열하는 가짓수를 말한다. nPr로 표시한다. 사실 순열은 itertools를 이용하면 쉽게 구현할 수 있다. 하지만 재귀로 직접 구현하는 방법을 알아보고자 한다. (itertools를 사용하여 구현하는 방법은 포스팅 마지막에 남기겠다.)

1. 중복 순열

# 중복 순열
# 주사위를 N번 던졌을 때 모든 경로 출력

dice = [1,2,3,4,5,6] # br
N = int(input())
path = [0]*N

def abc(level):
    if level == N: # N까지 뽑았으면 스탑
        print(*path, end = '\n')
        return
    for i in range(6): # 주사위 숫자 종류
        path[level] = dice[i]
        abc(level+1)
abc(0)

1. 일반 순열(중복 제외)

# A,B,C,D중에서 금,은,동메달 받을 사람 뽑는 경우의수

arr = ['A','B','C','D'] # br
path = [0]*3
used = [0]*4 # br의 개수 만큼 만들기, 중복 방지위해 만듦

def abc(level):
    if level == 3:
        print(*path)
        return 
    for i in range(4):
        if used[i] == 0: # 중복 방지
            path[level]=arr[i]
            used[i] = 1
            abc(level+1)
            used[i] = 0 # 재귀 탈출하면 돌려줌
abc(0)

# 배열 하나로 순열 만드는 법
p = list('ABCDE')

def perm(n, k): # n: 선택된 원소의 개수, k: 총 원소의 개수
    if n == k: # 배치가 다 되었을  때 print
        print(p)
        return
    for i in range(n, k): # index n앞의 숫자들을 이미 배치된 숫자, 그러므로 index n뒤의 숫자들과 자리를 바꿔가며 배치해야 함
        p[n], p[i] = p[i], p[n]
        perm(n+1, k)
        p[n], p[i] = p[i], p[n] # 원상복구

perm(0, 5)

💡 백트래킹(Backtracking)

완전 탐색 알고리즘에서 불필요한 분기(Branch) 를 가지치기(Pruning) 하는 것이다. 정답을 도출하기 전 탐색 과정 중에 정답이 될 수 없는 조건에 해당된다면 제외하여 효율을 높일 수 있다.

순열을 구하는 과정에서도 정답에 특정 조건이 붙어 모든 경우의 수를 구하는 경우가 아닐 때 백트래킹(Backtracking)을 이용해 효율을 높일 수 있다.

1. ABCD 중에 C로 시작하는 경우 제외, 3개를 중복 가능하게 뽑기

candidates=['A','B','C','D']
path=['']*3

def abc(level):
    if level==1 and path[level-1]=='C': return # 진입 후에 제외

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

    for i in range(4):
        #if level==0 and candidates[i]=='C': continue # 진입 전에 제외
        path[level]=candidates[i]
        abc(level+1)

abc(0)

1. ABCD 중에 B는 모든 경우에서 제외, 3개를 중복 가능하게 뽑기

candidates=['A','B','C','D']
path=['']*3

def abc(level):
    #if level > 0 and path[level-1]=='B': return # B 진입 후에 제외
    if level == 3:
        print(*path)
        return
    for i in range(4):
        if i==1: continue # B 진입 전에 제외
        path[level]=candidates[i]
        abc(level+1)

abc(0)

1. ABCD 중에 연속해서 2장의 카드가 나오면 제외, 3개를 중복 가능하게 뽑기

candidates=['A','B','C','D']
path=['']*3

def abc(level):
    # if level > 1 and path[level-1] == path[level-2]: return # 진입 후에 제외
    if level==3:
        print(*path)
        return
    for i in range(4):
        if level > 0 and (path[level-1] == candidates[i]):continue # 진입 전에 제외
        path[level]=candidates[i]
        abc(level+1)

abc(0)

🎈 itertools를 이용하여 순열, 조합 구현하기

itertools를 이용하여 순열과 조합을 구현하면, 직접 구현한 것보다 시간이 10배 정도 덜 걸린다.

1. 순열

    import itertools
    
    arr = ['A', 'B', 'C']
    result = itertools.permutations(arr, 2) # 반복 가능한 객체, r = 뽑는 개수
    print(list(result))
    
    # [('A', 'B'), ('A', 'C'), ('B', 'A'), ('B', 'C'), ('C', 'A'), ('C', 'B')]

2. 중복 순열

    from itertools import product
    
    arr = ['A', 'B', 'C']
    result = product(arr, arr, [1, 2]) # 반복 가능한 객체, 반복 가능한 객체, ..
    print(list(result))
    
    # [('A', 'A', 1), ('A', 'A', 2), ('A', 'B', 1), ('A', 'B', 2), ('A', 'C', 1), ('A', 'C', 2), ('B', 'A', 1), ('B', 'A', 2), ('B', 'B', 1), ('B', 'B', 2), ('B', 'C', 1), ('B', 'C', 2), ('C', 'A', 1), ('C', 'A', 2), ('C', 'B', 1), ('C', 'B', 2), ('C', 'C', 1), ('C', 'C', 2)]

    from itertools import product
    
    result = product([1,2,3], repeat=2) # 반복 가능한 객체, repeat=n (n번 반복)
    print(list(result))
    
    # [(1, 1), (1, 2), (1, 3), (2, 1), (2, 2), (2, 3), (3, 1), (3, 2), (3, 3)]

3. 조합

    import itertools
    
    arr = ['A', 'B', 'C']
    result = itertools.combinations(arr, 2) # 반복 가능한 객체, r = 뽑는 개수
    print(list(result))
    
    # [('A', 'B'), ('A', 'C'), ('B', 'C')]

4. 중복 조합

    from itertools import combinations_with_replacement
    
    arr = ['A', 'B', 'C', 'D']
    result = combinations_with_replacement(arr, 2) # 반복 가능한 객체, r = 뽑는 개수
    print(list(result))
    
    # [('A', 'A'), ('A', 'B'), ('A', 'C'), ('A', 'D'), ('B', 'B'), ('B', 'C'), ('B', 'D'), ('C', 'C'), ('C', 'D'), ('D', 'D')]