[코드트리 청약통장]6회차 미션 - 내 손 안에 백트래킹(개념부터 구현까지)

0. 지난 회차 요약 및 이번 회차 목표

1회차 갭체크 결과

 지난 회차에서는 한 달 동안 코드트리를 사용하면서 본인이 얼마나 변화/성장했는지를 알아보기 위한 시간을 가졌다. 결과적으로 초반 비슷해보였지만 내가 시뮬레이션에서 가장 어려워하고 시간을 많이 쏟아붓는게 어떤 건지 파악할 수 있었고, 공부 방향성도 재설정할 수 있었다.

 

그럼 이번 회차에서는..? 솔직히 시뮬레이션 학습을 할까 하다가 이게 아닌 차라리 처음 1회차때 손도 못댔던 어려웠던 그 문제에 도전해보기로 했다. 위 사진을 참고하면 그 문제는 백트래킹을 활용하여 푸는 문제였다.

 

자, 그럼 백트래킹 학습을 해보러 가겠다.

 

https://www.codetree.ai/ko/no-free-lunch-2026/?ref=MLF7M3

3년 만에 돌아온, 코드트리 청약 통장 챌린지 | 코드트리

혹시 아직 참여하지 않았거나 공부를 하고 싶다면 코드트리를 써보는걸 추천한다.

1. 백트래킹 개념(이론) 학습하기

  위 링크를 타고 들어가서 좌측 메뉴탭의 트레일 모양의 버튼을 누르면 다음과 같은 화면이 나오게 된다.

백트래킹 알고리즘 트레일

내가 풀던 시뮬레이션 I은 트레일 2에 머물고 있었다..

 

그래서 그런지 트레일 4단계에 머무는 알고리즘 입문 단계는 너무나 높아보이는 벽이었다.

지금 사진 보면 한 문제를 풀었는데, 난이도가 Easy임에도 불구하고 어떻게 풀어야하는지 감이 안와서 계속 '개념-문제'를 왔다갔다했다. 그러다가 우여곡절 끝에 풀이 방법을 찾아냈다.

 

 아직 코드로 풀어내는 연습이 많이 필요하다고 느낀 시간이었다..

2. 실습 해보기(문제 풀이시간)

https://www.codetree.ai/ko/trails/complete/curated-cards/intro-n-permutations-of-k-with-repetition/description

K개 중에 1개를 N번 뽑기 설명 | 코드트리

 위에 겨우 풀어낸 문제가 이 문제다.

문제를 설명하자면 1~K 사이의 숫자를 N번 만큼 뽑았을 때 나올 수 있는 경우의 수를 모두 구하는 문제였다. 얼핏 보면 그냥 Brute force랑 뭐가 다를까 싶긴 하다만... 아무튼 문제를 풀어보았다.

 

 처음 문제를 접했을 때, 중복순열?이 생각났다. 예를 들면 입력값이 K=2, N=2이면 총 4가지의 경우가 나올 수 있기 때문이다. K와 N의 크기가 커짐에 따라 구해야하는 경우의 수는 늘어난다는 것을 알 수 있었다.

 

 맞긴 맞았는데 푸는 데 상당한 시간이 걸렸다..(아직 개념이 부족한 거 아닐까..?)

학교에서 코딩을 알려줄 때도 기능별로 함수를 나눠서 작성하는 것이 유지보수 등 다양한 관점에서 이득을 볼 수 있다고 가르치곤 한다. 하지만 나는 기능을 어떻게 분해해서 함수별로 나눠야하는지 이 부분이 상당히 어렵게 느껴졌기 때문에, main 메서드에 다 때려넣다가 이번에는 함수별로 수행하는 동작을 나눠봤다.

 

 우선, counSet 함수(이름 이상해도 양해 바랍니다..) countSet을 통해 몇 번을 반복해서 결과 리스트에 숫자를 넣을 것인지 결정하는 기능을 수행한다.

조금 더 쉽게 말하자면, 1부터 K까지 요소들을 집어넣을 건데, 모든 경우의 수를 구하기 위해서는 요소 하나를 집어넣고, countSet 함수, 즉 자기 자신을 호출해서 완성시켜야한다.

처음에는 이 부분이 생각이 나지 않아서 상당히 고민했었는데, 반복문을 N의 개수에 따라 다르게 설정해야하는건가..? 하는 생각이 계속 맴돌다가 개념을 다시 보고 돌아와서 재귀함수의 형태로 코드를 완성할 수 있었다.

정리하자면, countSet 함수에서 answer에 요소를 하나 추가하고 countSet 함수를 호출하는 이유는, 요소를 추가하고 다음 칸으로 옮겨서 또 추가하고, 그 다음 칸으로 옮겨서 추가해야할 때, 옮겨갈 이동 장치가 필요했던 것이다. 그 이동 장치가 재귀 호출의 형태로 구현될 수 있었던 것이고, 그렇게 N번째 칸까지 옮겨지게 되면 cnt==N이라는 조건식이 성립되어 한 줄이 완성되는 것이다.

그렇게 N개가 출력되고, 이 과정이 반복문이 도는 동안 printAnswer가 K번 돌테니 처음에 생각해냈던 모든 경우의 수, K^N이 완성 되는 셈이다. 

 

printAnswer함수는 말 그대로 답을 출력하는 것에 사용되는 함수이다. answer에 추가 작업이 끝났으면, 즉 countSet 함수 내부에서 cnt 값이 N이 되어 조건문에 걸리면 이 함수가 호출되는 것이다.

함수가 호출되면 answer라는 배열 리스트에 있는 요소들을 하나씩 꺼내서 출력하는 작업을 진행하도록 코드를 작성하였다.

(사실 여기서 향상된 for문 쓰는 방법도 까먹어서 찾아봄..ㅎ)

3. 회고

 확실히 약점이라고 한 것에는 다 이유가 있구나 싶었다..(백트래킹 하나 풀었는데 탈탈 털려버린 기분...)

그래도 약점이라고 생각했던 백트래킹에 대해서 조금은 알아갈 수 있는 시간이었다.(그래도 백트래킹 구현은 이런 식으로 하는 거구나 하는 정도는 알아갈 수 있었어요)

 

 솔직히 이런 식으로 개념서를 작성해본 적은 없었는데 이번 기회에 기록하는 습관을 계속 들여갈 수 있는 초석이 마련된 것 같았다.

 

 학원에서 수학 오답노트 하듯이 내가 풀었던 문제들을 장황하지 않게, 핵심만 간단히 해서 어떤 생각으로 문제를 풀었는지 돌아볼 수 있고, 나중에서도 답이나 고칠 점을 찾을 수 있는 반환점이 될 수 있겠다고 생각했다.

 

이렇게 기초 문제를 풀며 이론을 쌓아가면서 이 또한 북마크 기능을 추가하여 개념을 잘 활용할 수 있는 좋은 문제, 어려워서 풀지 못했던 문제 등을 보관하여 나만의 학습 로드를 설계할 수 있겠다고 생각했다.

 

수학도 처음에는 풀리지 않았던 문제들이 유형별 문제 풀이, 반복적인 개념 노출 등을 통해 다시 손댈 수 있듯이 알고리즘 문제도 같을 것이라고 생각한다.

코드트리는 완벽이 아닌 완성으로 나아갈 수 있도록 도움을 주는 조력자인 것이다.