[코드트리 챌린지] 1주차 - 백트래킹

1주차 실력진단

첫 실력진단은 백트래킹 문제에서 막혀서 550점을 맞았습니다... 평소 약하다고 생각하였던 부분도 있었고, 이제 삼성 공채가 시작되기에 기업별 커리큘럼 - 삼성전자 탭에 있는 백트래킹으로 학습을 하였습니다!

 

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

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

 

파이썬에서는 항상 itertools의 combination 또는 permutation을 통해서 순열과 조합을 구해주었기에 더욱 백트래킹을 활용한 문제 풀이에서 약했다고 판단하였고 해당 개념과 문제를 풀며 skill을 익힐 수 있었습니다!

 

백트래킹

• 백트래킹의 핵심은 현재 원소를 선택하여 조합을 구성한 뒤 return을 한다면,
• pop 또는 visited[False]를 통하여 직전의 원소를 선택하지 않은 상태로 돌려주어야 된다는 점이에요.
• 개념과 설명이 잘 나와있으니 위의 링크를 참고하면 더 좋을 것 같습니다. 
• 저의 풀이 뿐만 아니라 잘 정리된 해설이 있어서 이해하기 훨씬 수월했습니다!

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


# 선택된 원소들을 출력해줍니다.
def print_permutation():
    for num in selected_nums:
        print(num, end = " ")
    print()


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


find_permutations(0)

 

이렇게 학습을 하고 나니 저번주 4번 문제에서 막혔지만 이번엔 7문제를 풀며 320점의 점수 상승을 이룰 수 있었어요 :)

다음 주에는 이번주에 약했던 투 포인터와 다른 유형들을 학습하면서 실력을 키워보겠습니다~~