[코드트리 조별과제] 백~트래킹 / K개 중 하나를 N번 선택하기

마지막 코드트리 조별과제입니다...

시험기간 마냥 막판 스퍼트해서ㅠ 문제는 못 풀지만 개념을 엄청 읽었음....

 

쉬운 거 내용이에요..

 

백트래킹은?! 재귀를 쓰는 것! 근데 진행하다가 아닌 경우에 빠른 return해서 전 단계로 퇴각하는 것!

 

재귀함수를 쓸 때는 종료조건이 중요하다! 끝나는 부분을 적절히 설정해줘야만 한다~!

그걸 또 명확히 하려면 재귀함수의 정의를 명확히 하는게 무엇보다 중요하다 (aka 함.정.명..ㅋㅋ)

문제) K개 중에 1개를 n번 뽑기

 

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

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

 

풀이(Python)

k,n=map(int,input().split())
arr=[1]*n
def plus1(x):
    if x<0:
        return False
    arr[x]+=1
    if arr[x]>k:
        arr[x]=1
        return plus1(x-1)
    return True

print(*arr)
for _ in range(k**n-1):
    if plus1(n-1):
        print(*arr)

 

배운점

1. 어떻게 구현하냐의 문제인듯..! 스스로 안 헷갈리는 방향으로 연습하자

2. 재귀적으로... 하는 방법도 있다...!

# 변수 선언 및 입력
k, n = tuple(map(int, input().split()))
selected_nums = []

def find_permutations(cnt):
    # n개를 모두 뽑은 경우 답을 출력해줍니다.
    if cnt == n:
        print(*seleected_nums)
        return
    
    # 1부터 k까지의 각 숫자가 뽑혔을 때의 경우를 탐색합니다.
    for i in range(1, k + 1):
        selected_nums.append(i)
        find_permutations(cnt + 1)
        selected_nums.pop()


find_permutations(0)

 

-> 나는 왠지 순열, 조합 선택하는 걸 좀 헷갈려하는데... 외울 때까지 익혀봐야 할듯하다