[알고리즘] 코드트리 알고리즘 입문 - 시뮬레이션 to 백트래킹

오늘 글은 저번처럼 한 문제만 기록하지 않고, 진도를 꽤 나갔기 때문에 그동안 느낀 점들을 기록하려 한다.

시뮬레이션 챕터

우선 시뮬레이션 챕터를 풀이하면서(난이도 중까지 풂) 매 순간이 고통의 연속이었다. 시간복잡도가 O(n^2)인 문제들만 모아놓은 챕터이다보니 어떤 자료구조로 접근할지 고민하기보다 문제 자체를 이해하고 어떻게 구현할지 고민하는데 거의 모든 시간을 할애했다. 대체로 2차원 리스트 안에서 직사각형을 이동시키거나 패턴에 맞게 점을 이동시키는 류의 문제였는데, 괴랄한 테스트케이스를 통과하지 못해서 고민하고 또 고민하는 영겁의 시간이었던 것 같다 ..

백트래킹 챕터

어찌저찌 2주 동안 시뮬레이션 챕터의 난이도 중짜리 문제들을 다 풀고 백트래킹 챕터로 넘어오고 나니 한결 가벼워진 느낌이다. 대신 지금 풀고 있는 문제들은 재귀함수 관련된 문제들인데 재귀함수가 전개되는 차례에 익숙하지 않아서 아직 경직된 사고를 하는 중이다. 난이도 하 인 문제 하나를 가져와 설명하면 좋을 것 같다.

백트래킹 - 아름다운 수

https://www.codetree.ai/missions/2/problems/beautiful-number/submissions

n = int(input())
answer, result = [], []

def beautiful_number(answer):
    # print('enter')
    if len(answer) == n:
        # print(answer)
        result.append(answer)
        # print('exit')
        return
    elif len(answer) > n:
        # print('exit')
        return

    for i in range(1, 5):
        # print(f'i:{i}')
        # print(f"answer:{answer}")
        if len(answer) + i <= n:
            # 1은 무조건1개, 2는 무조건 2개, 3은 무조건 3개 연속임
            answer.extend([i] * i)
            beautiful_number(answer)
            for _ in range(i):
                answer.pop()
            
    # print('exit')
    return

beautiful_number(answer)
print(len(result))
# Credits to @bosungpark형님

n자리의 아름다운 수(해당 숫자만큼 연달아 같은 숫자가 나오는 숫자의 배열)를 구하는 문제였다. 다른 사람들은 나처럼 실제로 숫자를 리스트에 집어넣는 방식이 아니라 count 변수에 해당 숫자만큼 더하는 식으로 접근하기도 하던데, 나는 처음부터 list.extend([숫자] * 숫자)를 활용해야겠다 생각했다.

여기까진 좋았는데, 앞서 말했듯 재귀용법에 익숙하지 않아서 자꾸 max recursion 에러를 맛봤다. 아름다운 수 유닛을 재귀적으로 추가해줘야 한다는 건 나도 아는데, n자리 배열이 될 때 return시키는 방법과 조건에 맞지 않으면 아름다운 수 유닛을 추가하지 않게 하는 방법을 떠올리지 못했다.

그러다 같이 알고리즘 스터디를 하는 멋쟁이 형님과 내 문제 접근 방식이 일치했었다는 기억이 떠오르면서 그 분의 코드를 염탐한 것. 형님의 코드를 보고 나니 막혔던 시야가 트인 느낌을 받았다.

왜냐면 난 그 이전 몸풀기 문제에서 모두 재귀함수 인자로 정수값을 줬었기 때문에 의심하지 않고 정수값을 집어넣어 풀려고 시도했었는데, 형님은 그런 나의 뒤통수를 얼얼하게 후리듯 인자로 빈 리스트를 넘겨주고, 재귀적으로 그 리스트에 값을 밀어넣고 그 변한 리스트를 검사하는 로직을 구현한 것이었다..!

초장부터 답지를 보면 아무짝에도 쓸모없지만, 막혀서 더이상 손댈 수 없는 상태에서 답지를 보며 깨달음을 얻는 것은 벽과 같이 느껴지는 넘지 못하는 계단 앞에서 트램펄린의 도움을 받아 단번에 빅스텝 쩜프를 뛰는 것과 같다.

---

아 근데 이거 말고도 이번 학기 듣는 수업들 꼬박꼬박 노션에 받아적고 추가학습하고 보충해놔야 하는데... 매일 학교에서 집으로 귀환하면 지쳐서 자빠져 누워있다 하루가 지나가곤 한다. 지져스 크라잉.. 프로젝트 개발도 밀리지 않게 해야하는데 며칠째 손도 못대고 있는 중. 나보다 열심히 사는 주변 지인들을 보면 경외감을 느끼곤하는 요즘이다