정글[Week_02]: 기초적인 알고리즘에 입문하다

2주차 부터는 본격적인 알고리즘 훈련 과정을 밟는다. 기존에 코딩 테스트를 연습해보았고, 몇몇 회사의 코테도 본 경험을 바탕으로, "기초적인 커리큘럼을 다시 밟을 때 이점이 있을까?" 하는 의문이 있었으나, 나의 착각이었다. 사실, 10 to 23이라는 몰입 높은 커리큘럼에 맞춰, dictionary, list, set, string, int 와 같은 자료구조나 반복/조건문은 바로 넘어간다. 이후에는 바로 재귀함수로 넘어가는데, 어떤 방식으로 작동하는지, 재귀함수의 유형이 무엇인지... 이를 분석하면서 학습을 하게 된다.

 

 

재귀함수, 그리고 백트래킹

이 둘의 차이는 무엇일까? 일단 둘 다 호출한 함수 안에 함수를 부르는 재귀 함수라는 점에서는 동일하다. 재귀함수는 기본적으로 함수가 자기를 또 불러오기 때문에.. 아무런 설정이 없으면 무한으로 호출이 되어, stack 초과와 같은 에러가 생기게 된다.

재귀함수를 설명하는 밈

당연히. 이런 에러를 방지하기 위해서 재귀함수에서는 base case라는 기본 조건을 설정한다. 예를 들어, 자기가 받은 인자를 항상 -1을 하여 값을 넘겨주는 함수가 있다고 치자. 이 함수가 만약 5를 받았다면, 5, 4, 3, 2, 1, 0, -1.... 과 같이 무한으로 마이너스의 길을 가게 된다. 그런데 이 함수에 "0이 되었을 경우, 더 이상 진행하지 않는다" 와 같은 return 조건을 생성하면, 0에서 멈추게 된다.

하지만 재귀함수는 단 하나의 자식?재귀함수를 호출하지 않는다. 아래 그림과 같이, 하나의 재귀함수가 두 개의 자녀 재귀함수를 호출하고.. 이것이 반복되면 자식이 기하급수적으로 늘어나게 된다. 그럼 이렇게 기하급수적으로 늘어난 노드를 모두 순회할 필요가 있는가? 라고 의문을 가질 수 있다. 이러한 의문에서 출발한 것이 백트래킹이다.

벌써 2단계 밖에 안갔는데 1에서 4개로 탐색할 대상이 늘어났다

 

아래 백트래킹을 한 재귀함수의 흐름을 보자. 특정 노드에서는 더 이상 자식노드로 가지 않고, 미리 "가지치기"를 한다는 점을 알 수 있다. 이렇게 탐색 시간을 효율화 하는 것을 백트래킹 재귀함수라고 할 수 있겠다.

 

Python으로 간략하게 나타내면 아래와 같이 코드를 작성할 수 있다. 결국엔 base case와 좀 다른 return 조건이 추가되었다고 생각하면 좋다.

def backtracking(depth):
    # 1. Base Case (진짜 끝에 도달했을 때)
    if depth == 5:
        return 

    # 2. 유턴 조건 (여기가 말씀하신 '추가 케이스'입니다!)
    if 이_길은_정답_가능성이_없음: 
        return # 여기서도 가지치기를 하고 더 이상 탐색을 안한다

    # 가능성이 있다면 더 내려감
    backtracking(depth + 1)

 

 

재귀함수는 큰 문제를 나눠서 풀 때 사용이 가능하다

하노이의 탑, 문제의 구조가 보이는가..?

하노이의 탑이라는 문제를 들어본 적이 있는가? 상당히 흔한 문제인 만큼, 여기서는 설명을 짧게 하고자 한다. 탑의 한 층 한 층 옮겨서 1번 봉에서 3번 봉으로 모두 옮기면 된다. 다만, 작은 원반 위에 큰 원반을 올릴 수는 없다.

답답하게 느껴질 수 있지만, 문제에 대해 거시적으로 바라보자. n개의 층이 있을 경우, n-1개는 목적지인 3번 봉이 아닌 다른 봉에 옮긴 다음, 마지막 1개는 3번 봉에 옮기고 이후 n-1개를 3번 봉에 옮기면 된다. 여기서, 문제를 분해해 보자. 위 그림은 n-1개를 통채로 옮기는 것 처럼 묘사하였지만, n-1개 또한 애초에 n-1번째 층과 나머지 n-2개 전체 통으로 보고 위와 같은 그림을 그릴 수 있다. 그 다음은 n-2 통을 => n-2번째 층 + n-3개 통 이런 식으로 계속 해체가 가능하다.

처음에는 상당히 어려울 수 있다. 그러나 이를 이해하기 시작하면, 아래와 같이 생각보다 간단한? 재귀함수로 문제가 풀어지는 쾌감을 느끼게 된다.

def recursion_move(floors, start, end):
    if floors == 1:
        print(f"{start} {end}")
        return
    
    mid = 6 - start - end

    recursion_move(floors - 1, start, mid)
    print(f"{start} {end}")
    recursion_move(floors - 1, mid, end)

아무튼 이번 week02에서는 재귀함수에 대해 더 깊에 파헤칠 수 있는 소중한 경험이었다. 다음 주자 자료를 보니, 이분탐색/정렬/우선순위 큐와 같은 본격적인 자료구조 활용에 들어가는 거 같다. 

지나가는 이번 주를 생각하며, 다음 주를 기대하는 마음을 담아, 이번 글을 마친다.

그럼 뿅.