[코드트리 챌린지] 4주차 (9/27-10/2), 백트래킹

이번에도 어김없이 돌아온 실력진단평가 시간~

진단결과

이번주 새로운 진단평가 결과

저번주와 같은 백트래킹 부분이 부족하다는 진단결과를 받았다.

나는 내가 이 개념을 마스터했다!에 대한 기준을 '남한테 설명할 수 있는가?'로 삼고 있다. 

그런데, 솔직히 공부하면서도 백트래킹 연습문제를 풀 때 남한테 설명할 수 있을 자신은 없었다.

코드트리도 그 마음을 알았는지 매주 느끼지만,,진단 너무 정확하다..

이렇게 빼도박도 못하게 되었으니 백트래킹을 얼른 다시 공부해봐야겠다 마음을 먹고 공부를 시작했다.

백트래킹이라는 게 참,, 이론은 이해가 되는데 문제로 풀 때가 되면 뇌가 정지된다. 근데 문제를 몇 개 풀어보니까 이론 자체도 깊이 있게 파악을 못했다는 문제가 발견되었다.

 

학습 전략

백트래킹에 관련된 카테고리는 오른쪽 사진과 같았다

백트래킹은 전에 공부할 때와는 다르게 이제 알고리즘을 본격적으로 다뤄서 그런지 문제 하나당 소요되는 시간이 굉장히 길었다.

그래서 전부 다 풀기에는 무리가 있다고 판단되었고, 백트래킹의 기본과 어떤 경우에 사용되는지를 파악하는게 먼저였기때문에 넓고 얕은 지식이 우선되어야한다고 판단했다.

이번주는 꼭 백트래킹 문제를 풀기 위해서 기본개념에 대한 내용을 주체적으로 이해하고, 이전에 풀었던 코드를 보지 않고 다시 작성해보는 시간을 가졌다.

 

풀었던 문제

이번에 골라온 문제는 너무 간단하겠지만, 다른 플랫폼에서 알고리즘 문제를 풀 때 많이 나왔던 풀이의 기본이 되는 것 같아서 선정해왔다.

# 거꾸로 순열

1부터 n까지의 수를 정확히 한 번씩만 사용하여 만들 수 있는 가능한 모든 수열을 구해주는 프로그램을 작성해보세요. 단, 사전순으로 가장 뒤에 있는 수열부터 먼저 출력하도록 합니다.

'한 번씩만 사용하여'라는 조건이 붙었기 때문에 사용했는지 안했는지를 알기위해서 visited 배열을 사용하는 접근이 많은 문제에서 사용되기에 선정한 것이다!

이 문제는 심지어 가장 뒤에 있는 수열부터 거꾸로 출력해야하기 때문에 조금 당황할 수도 있겠지만, 그냥 단순히 거꾸로 돌려주면 된다.

 

풀이 전략

1부터 n까지를 거꾸로 for문을 돌릴 수만 있으면 된다고 판단했다.

range(n,0,-1)을 통해서 n부터 1까지 -1씩 줄어들면서 반복되도록 만들었다.

n = int(input())
visited=[False]*(n+1)
arr=[]

def choose_number(curr_num):
    if curr_num == 0:
        for elem in arr:
            print(elem, end=" ")
        print()
        return

    for i in range(n, 0, -1):
        if visited[i]==True:
            continue
        
        visited[i] = True
        arr.append(i)
        choose_number(curr_num-1)
        arr.pop()
        visited[i] = False

choose_number(n)

코드트리의 모법 답안에서는 choose_number(0)으로 실행을 시작해서 => if curr_num == n: 일때 출력될 수 있도록 구현이 되어있다.

curr_num 같은 경우, 해당 자리 위치를 알려주는 거라서 굳이 n부터 시작할 필요가 없었는데 풀이를 보고 왜 이렇게 생각했지,, 싶긴 했다

백트래킹에 대한 이해가 조금 된 것 같으니 응용문제들도 풀면서 백트래킹에 대한 시야를 넓혀야겠다.

느낀 점

이번에 공부를 하고 다시 실력진단평가를 보면서 느꼈던 점 중에 하나가 평가를 하면서 복습도 된다는 점이었다.

백트래킹을 2주동안 공부하게 되면서 평가를 시작할 때 전에 것도 못 풀면 어떡하지 생각이 들었었는데 사실 그걸 진단하기 위한 평가인데 겁을 먹은 게 너무 웃기다,,

하여튼! 취준을 하고 있는 지금도 그렇고, 모든 공부가 시간을 쏟는 것에 비해 가시적으로 보이는 결과가 없기 때문에 힘든 것이라고 생각한다. 근데 코드트리는 커리큘럼도 존재하고 실력진단을 통해서 점수도 나오기때문에 퀘스트 깨는 것과 같은 재미가 있다.

물론 점수가 있다보니 개인적으로 점수를 계속 올리려는 압박이 생기기는 한다. 이 부분은 누구한테 평가받는 것이라고 생각하지 않는 마인드가 필요하다고 느꼈다.

 

**추가

다음주차 글을 작성하다가 너무 기뻐서 여기다가도 남기고 싶어서 수정하러 왔다!

신나는 그래프

꺅! 점수상승!

610 -> 645 🫶

이게 바로 성취감인가..

성장곡선 가보자고~