[코드트리/INTERMEDIATE LOW] Backtracking K개 중 하나를 N번 선택하기 Python

🔥 이론

☑️ 순열 : 서로 다른 n개의 원소에서 r개를 중복없이 순서에 상관있게 선택하는 것

☑️ 조합 : 서로 다른 n개에서 순서와 상관없이 r개를 고르는 것

 

✔️ 중복 순열

- from itertools import product

from itertools import product

for i in product([1, 2, 3], 'ab'):
	print(i, end=" ")

# (1, 'a') (1, 'b') (2, 'a') (2, 'b') (3, 'a') (3, 'b') 

for i in product([1, 2, 3], repeat=2):
	print(i, end=" ")

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

 

✔️ 중복 조합

- from itertools import combinations_with_replacement

from itertools import combinations_with_replacement

for i in combinations_with_replacement([1, 2, 3, 4], 2):
	print(i, end=" ")

# (1, 1) (1, 2) (1, 3) (1, 4) (2, 2) (2, 3) (2, 4) (3, 3) (3, 4) (4, 4)

 

이처럼 Python의 경우 itertools 패키지를 통해 순열과 조합을 쉽게 구현할 수 있음

이번엔 이 순열 패키지 사용과 직접 구현 두 가지 코드로 풀어보기로 함

 

 

🔥 문제링크

https://www.codetree.ai/missions/2/problems/n-permutations-of-k-with-repetition?utm_source=clipboard&utm_medium=text 

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

🔥 문제

 

🔥 코드

(1) 순열 패키지 사용

from itertools import product

nums = []
k, n = map(int, input().split())

for i in range(1, k+1):
    nums.append(i)

for i in product(nums, repeat=n):
    for j in i:
        print(j, end=" ")
    print()

(2) 직접 구현

def arr_print():
    for i in nums:
        print(i, end=" ")
    print()

def perm(idx):
    if idx == n+1:
        arr_print()
        return
    
    for i in range(1, k+1):
        nums.append(i)
        perm(idx+1)
        nums.pop()



nums = []
k, n = map(int, input().split())
perm(1)

 

 

🔥 풀이