도르마무 도르마무?

지난주에 백트래킹 얘기를 했던것 같은데 왜 또 있지??
2주차 실력진단에서도 백트래킹 문제를 못 풀었기 때문이죠~ 😩

2주차 실력진단

이번주에는 개인적인 일이 많아서 사실 공부를 많이 못했고, 백트래킹도 쉽네~라고 생각하고 살짝 풀고 넘어갔다. 그랬더니 또트래킹이 나왔는데... 푸는 법을 다 까먹어서 ㅠㅠ 저 한문제만 못풀었다. 하...

2주차 백트래킹

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

푸는 방법은 다 똑같은데, choice 한 수를 저장하고 빼고 하는 방법이 헷갈렸다.

ans = []
def choose(num):
    if num == n + 1:
        for i in ans:
            print(i, end=' ')
        print()
        return
    

    for i in range(1, k + 1):
        ans.append(i) << 요 부분 
        choose(num + 1)
        ans.pop()

choose(1)

그래서 복습하는 김에 백트래킹 문제를 많이 풀었다.

이 중 역시 헷갈리는건 순열만들기와 N 개 중 M 개 고르기 문제.

def solution(curr_num , cnt):
    global ans
    #print(curr_num, cnt)
    if curr_num == n * 2 : << 이 부분에 전체 갯수 (N)
        if cnt == n :	<< 이 부분이 선택 갯수 (M)
           

        return
    
    part1.append(grid[curr_num])
    solution(curr_num + 1, cnt + 1) << curr_num 을 선택했을 때
    part1.pop()

    solution(curr_num + 1, cnt) << 안했을 때 
    


solution(0, 0)

여러 개중 몇 개를 선택할 경우 세워야 하는 조건식을 이해 못해 한참을 해맸고, 선택할지 안할지에 대한 고려도 놓쳐 또 한참 해맸다 ㅋㅋㅋ
기억에 작년에도 이런 문제를 유독 어려워해 공식을 암기했던 기억이 난다.

계속 풀어봐야 하는데... 어려워서 한문제도 시간이 참 오래 걸린다 ㅎㅎㅎ