재귀함수를 이용해 중복순열 구하기

✏️ 목표

1부터 N까지 번호가 적힌 구슬이 있는데, 이 중 중복을 허락하여 M번을 뽑아 일렬로 나열하는 방법을 모두 출력한 후 마지막에는 방법의 수를 출력해 보자.

(이때 출력 순서는 사전순으로 오름차순으로 출력해야 한다.)

 

 

 

❓ 중복순열

서로 다른 n개의 수에서 중복을 허락하여 r개를 선택하여 일렬로 나열하는 경우의 수이다. 따라서 같은 수를 여러 번 뽑아도 되는 것이다.

 

<ex>

1부터 3까지 번호가 적힌 구슬 중에서 중복을 허락하여 2개를 뽑아 일렬로 나열하는 방법의 모든 경우의 수는 다음과 같다. (사전순으로)

(1, 1), (1, 2), (1, 3), (2, 1), (2, 2), (2, 3), (3, 1), (3, 2), (3, 3)

총 9개의 경우의 수가 나온다.

 

 

 

💡 해결하기

이번에는 이전 시간까지 계속 배웠던 두 갈래로 뻗는 트리가 아닌 n 갈래로 뻗는 트리를 이용하여 문제를 해결해야 한다. 

위에서 확인한 예시를 가지고 트리를 그려 보겠다.

 

 

주어진 구슬의 번호의 수만큼 간선(n개, 위 예시에서는 3개)이 존재하는 것을 볼 수 있다.

같은 숫자를 뽑아 일렬로 나열하는 것이 가능한 중복순열이기 때문에 이미 한 숫자를 뽑았어도 그와 똑같은 숫자를 뽑는 것이 가능하고, 숫자 구성이 같더라도 나열하는 순서가 다르면 다른 것이므로 모든 노드에서 간선이 3개이다.

트리의 레벨은 곧 현재 뽑혀서 나열된 숫자의 개수와 같다.

구슬의 번호를 1번부터 n번까지 차례로 거치며 전위순회 방식으로 진행하면 사전 순으로 출력이 가능하다.

 

정리하자면 다음과 같은 방식으로 코드를 작성하면 된다.

➡️ 종료 조건은 트리의 레벨이 m이 되었을 때이다. 즉, 현재까지 뽑힌 숫자가 m개인 경우에 현재 실행 중인 함수가 종료되어야 한다. 이를 함수에 인자 L로 넣어 주어 재귀 함수 호출 시마다 1씩 증가시켜주면 된다.

➡️ 간선이 n개로 뻗어 나가야 하기 때문에 반복문(for문)을 돌려야 한다. 범위는 1부터 n까지의 숫자로, 중복순열을 기록할 리스트(pick)를 따로 만들어 pick[L]의 자리에 반복문에서의 현재 숫자를 기록한다.

기록 후 재귀 함수 호출을 하는 것이다.

 

 

 

💻 Python으로 코드 작성하기

 

# L : 트리의 레벨 (현재 뽑아서 나열한 구슬 수)
def repeated_permutation(L):
    # cnt를 전역변수 선언 해주기 (함수 밖에 있는 cnt의 값을 변화시키기 위해)
    global cnt
    # 뽑혀서 나열되어 있는 현재 구슬 수가 m과 같을 경우
    if L == m:
        # 구슬 번호 출력하기
        for num in pick:
            print(num, end=' ')
        print()
        # 순열 개수 1 증가
        cnt += 1
    else:
        # 구슬의 번호만큼 반복
        for i in range(1, n + 1):
            # 현재 순서인 L번째로 뽑히는 구슬로 i번 구슬 기록
            pick[L] = i
            # L + 1번째로 뽑힐 구슬을 위해 재귀 호출
            repeated_permutation(L + 1)

# n : 구슬의 번호 (1부터 n까지), m : 뽑아야 하는 구슬 수
n, m = map(int, input().split())
# 숫자를 뽑아서 나열하기 위한 리스트, 초깃값은 모두 0, 길이는 m
pick = [0] * m     
# 가능한 순열의 개수
cnt = 0    

repeated_permutation(0)
print(cnt)

 

위 코드를 위에서 살펴본 예시를 입력으로 넣어 실행시키면 다음과 같은 과정을 거치게 되어 사전순으로 출력 가능하다.

 

 

 

 

📌 참고 강의

파이썬 알고리즘 문제풀이 입문(코딩테스트 대비) 대시보드 - 인프런 | 강의 (inflearn.com)

파이썬 알고리즘 문제풀이 입문(코딩테스트 대비) - 인프런 | 강의