[코드트리 챌린지] 3주차 (9/20-9/25), 백트래킹

2주차 마무리에 했던 실력역량평가

이번주는 백트래킹에 대한 학습이 필요하다고 나온 저번주의 진단을 토대로 백트래킹을 공부해보려고한다!

최근 코테에서 dp와 백트래킹에 대한 문제들이 많이 나오는 경험을 했었고, 부족하다고 느낀 부분이었는데 이번에 또 어김없이 실력평가에서 정확한 진단을 받게 되었다.

 

백트래킹

이제 드디어 novice 단계를 지나 intermediate단계로 갔는데 처음부터 너무 막혔다.

백트래킹, 학부 수업때도 배워서 뭔 말인지는 알겠으나 막상 문제를 접했을때 사용하는 게 어려웠는데 한번 공부해보자! 마음먹고 첫 기본문제를 보게되었다.

코드트리의 장점은 아무래도 친절하고 자세한 개념설명이지 않을까 싶다.

순열, 조합을 제대로 아는 거 없이 단순히 파이썬 combination 내장함수 같은 걸 사용했었는데 백트래킹을 제대로 공부해볼 수 있는 계기가 돼서 너무 좋았다.

오늘 풀어본 문제는 아무래도 기본 문제!

왜냐! 백트래킹을 이해하는데 오래 걸려서 이 문제의 풀이를 스스로 생각해내기에 오래 걸렸기 때문이다.

 

풀었던 문제

# k개 중에 1개를 n번 뽑기

 

풀이 전략

이 문제는 이진수 구하는 문제를 생각하면된다.

코드트리도 이진수 구하는 문제를 풀면서 개념을 설명해주어서 더 이해가 잘 갔다.

이진수 문제를 위에 문제로 해석하면 k개중에 1개를 n번 뽑기 => 2개(0,1)중에 1개를 n번 선택하기가 되니까 이걸 먼저 생각해보자

그러면 자릿수마다 0,1 하나씩 넣어주면 되고, 자리마다 넣는 함수 이름을 choose_number()이라고 해보자

curr

세자리수(n=3)이면 choose_number(0)부터 choose_number(2)까지 돌면된다. 그러면 이 함수의 종료조건은 n일때가 되는 것이다.

 

이 메커니즘을 똑같이 2->k, 3->n으로 생각하면된다.

k, n = tuple(map(int, input().split()))

arr = []

def print_num():
    for elem in arr:
        print(elem, end=" ")
    print()

def choose_number(curr_num):
    if curr_num == n:
        print_num()
        return
    
    for i in range(1, k+1):
        arr.append(i)
        choose_number(curr_num+1)
        arr.pop()

choose_number(0)

choose_number 함수는 curr_num자리에 for문을 통해서 1부터 k까지의 숫자를 넣는 것이다.

 

이렇게 블로그로 다시 정리하면서 문제를 바라보니까 더 이해가 잘되고 있다!

백트래킹 이해가 어려웠어서 문제를 많이 못풀었는데 이해됐을때 빨리 풀어서 내 것으로 만들어야겠다!

빨리 풀고 나서의 다음주 실력진단평가 점수가 기대된당,,