[모각코 / 240112] 알고리즘 문제 풀이 (코드트리 - 백트래킹)

 

 

안녕하세요. 모각코 2일차입니다. 

 

 

 

오늘도 코드트리를 활용하여 알고리즘 문제를 풀었습니다. 

 

 

코드트리 - k개 중에 1개를 n번 선택하기

https://www.codetree.ai/missions/2/problems/n-permutations-of-k-with-repetition/introduction

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

 

 

이 문제는 중복 순열에 관한 문제입니다. 

 

 

입력 양식

2 2

 

 

 

출력 양식

1 1
1 2
2 1
2 2

 

 

 

 

풀이 방법입니다. 

사실 저는 알고리즘을 파이썬으로 풀고 있고, 이런 문제는 파이썬 모듈 중 itertools를 활용하여 풀 수 있는데요.

from itertools import product

k, n = map(int, input().split())  # 입력 양식

li = [i for i in range(1, k+1)]  # 1분터 k까지의 리스트

for i in product(li, repeat=n):  # 중복 n번 반복
    a = list(i)
    for m in a:
        print(m, end=' ')
    print()

 

 

백트래킹인만큼 재귀를 사용해서 풀어야합니다. 

k, n = map(int, input().split())  # 입력 양식
selected_nums = []

# 선택된 원소의 출력
def print_permutation():
    for num in selected_nums:
        print(num, end = " ")
    print()


def find_permutations(cnt):
    if cnt == n:  # n개를 고르면 리스트 출력
        print_permutation()
        return
       
    for i in range(1, k + 1):  # 1부터 k까지의 숫자가 뽑혔을 경우 탐색
        selected_nums.append(i)
        find_permutations(cnt + 1)
        selected_nums.pop()


find_permutations(0)