Recursion

재귀는 곧 자연수, 귀납적인 정의와 동치다.

기저 조건에 대해서 반드시 종료되어야 하고, 모든 입력은 최종적으로 기저 조건에 수렴해야 한다.

함수 파라미터로 뭘 받고, 어디까지 계산한 후 다시 재귀 호출을 할지를 명확하게 정해야 한다. 함수 형태를 잘 잡아야 올바른 재귀 함수를 짤 수 있다.

모든 재귀 함수는 같은 의미의 반복문으로 바꿀 수 있다. 재귀 함수는 함수 호출 로드가 있기 때문에 메모리와 성능에서 약간 손해를 보지만 대신 코드가 아주 간결해진다.

재귀 함수 호출을 두 번 이상하면 아주 비효율적일 수 있다. e.g) 피보나치. 그런데 만약 함수 자체가 idempotent 하다면, 나중에 DP로 최적화할 여지가 많다.

1629번: 곱셈

import sys
a, b, c = map(int, sys.stdin.readline().rstrip().split())

def my_power(a, b, m):
    if b == 1:
        return a % m

    val = my_power(a, b//2, m)  # val == a^(b/2)
    val = val * val % m  # val = a^b = a^(b/2) * a(b/2)
    if b % 2 == 0:
        return val
    else:
        return val * a % m  # in case of b is an odd number

print(my_power(a, b, c))

이건 반복문으로도 풀 수 있지만 재귀적으로 생각하는 훈련에 좋은 문제이기도 하다.

Base Case로 a ^ 1 = a를 깔아두었다. a ^ 0 = 1을 깔아도 상관없다. 그러고나면 다음 식을 이용할 수 있다: a ^ b = a ^ (b/2) * a ^ (b/2)

여기서는 이 정의에 충실하게 먼저 a ^ (b/2)인 val을 구하고 이걸 두 번 곱했다. 코너 케이스로 b가 홀수일 때에는 b / 2가 나누어 떨이지지 않기 때문에 a ^ b = a ^ (b/2) * a ^ (b/2) * a 를 처리해줘야 한다.

거의 수학적인 정의를 그대로 써주면 되지만 따라가는 훈련을 해야한다.

아무튼 먼저 함수 형태를 잘 생각해봐야 하는데, 단순히 지금 턴에 옮길 원판 개수를 입력으로 받으면 안된다. 왜냐하면 원판을 옮길 때 1 -> 3으로 옮겨야할 때도 있고 1 -> 2로 옮겨야할 때도 있어서, 즉 원판을 어디에서 어디로 옮길지가 매번 달라지기 때문이다. 따라서 함수의 원형은 hanoi(f, t, n)이 되어야 하고 f -> t로 n개의 원판을 옮기는 함수라고 생각해야 한다.

그러고나면 이제 기저 조건을 따져봐야 한다. 자명한 케이스로 원판 1개를 옮겨야 한다면 그냥 f -> t로 곧바로 옮길 수 있다. 그럼 끝이다.

그럼 이제 Inductive Case를 생각하기 위해서 k - 1개를 옮길 수 있다고 가정할 때 k개를 어떻게 옮길지 고민해보자. k개가 기둥 1에 있고 이걸 기둥 3으로 옮기려고 한다면 다음 스텝을 밟아야 한다:

기둥 1에 있는 원판 중 k - 1개를 기둥 2로 옮긴다. k - 1개를 옮길 수 있다고 가정했으므로 (Inductive Hypothesis) 옮겨졌다고 가정한다.
k번째 원판을 3번 기둥으로 옮긴다.
2번 기둥에 있던 k - 1개의 원판을 기둥 3으로 마저 옮긴다. 역시 Inductive Hypothesis에 의해 옮길 수 있다.

이 과정을 거치게 되고, 우리는 k = 1일 때 옮기는 방법을 알고 있으므로 Inductive Definition에 따라 k = 2, 3, ..., 즉 모든 경우에 대해 옮길 수 있게 된다.

여기까지는 뇌가 어떻게 이해할 수 있다. 그런데 이걸 막상 코드로 옮기려면 좀 헷갈린다.

먼저 함수 원형이 hanoi(f, t, n) 이므로, k - 1개의 원판을 잠깐 담아두기 위한 버퍼 용도으 기둥 번호를 어떻게 구해야할지 고민해보자. 모든 케이스를 나열하면 다음과 같다:

기둥 1 -> 3 일때: 기둥 2
기둥 1 -> 2 일때: 기둥 3
기둥 3 -> 1 일때: 기둥 2
기둥 3 -> 2 일때: 기둥 1
기둥 2 -> 3 일때: 기둥 1
기둥 2 -> 1 일때: 기둥 3

즉, 순서 있는 기둥 3개를 나열하는 가짓수인 3! = 6이 모든 케이스가 되고 이 경우는 이걸 전부 하나의 해시 테이블에 만들어놨다가 돌려줘도 된다. 하지만 좀더 엘레강트한 방법을 고민해보자. 잘 살펴보면, 출발 기둥과 도착 기둥의 번호의 합을 총 가짓수에서 빼면 버퍼로 쓸 기둥의 번호가 나옴을 알 수 있다. 즉, 기둥 1 -> 3이면 6 - (1 + 3) = 2가 되고, 나머지도 모두 같은 방법으로 계산할 수 있다. 따라서, 이제 버퍼로 쓸 기둥의 번호도 알아냈기 때문에, 위의 스텝을 일반화 하면 다음과 같다:

기둥 f에 있는 k - 1개의 원판을 버퍼 기둥으로 옮긴다.
기둥 f에 있는 k번째 원판을 t기둥으로 옮긴다.
버퍼 기둥에 있던 k - 1개의 원판을 t기둥으로 옮긴다.

이렇게 해서 하노이 탑의 옮기는 순서는 구할 수 있다.

그럼 총 가짓수는 어떻게 구할까? 재귀 호출이 일어날 때마다 값을 누적해서 구해도 되지만, 귀납적 방법을 가지고 있기 때문에 원판의 개수가 주어지면 총 옮기는 횟수를 계산하는 수식을 구할 수 있다.

원판 k - 1개를 이동하기 위해서 m번 이동이 필요하다고 하자. 그러면 위의 귀납적 방법에 의해서 원판 k개를 이동하려면 먼저 1번 스텝에 의해서 m번, 2번 스텝에 의해서 1번, 그리고 3번 스텝에 의해서 m번 이동이 필요하다. 따라서 총 2 * m + 1 번의 이동이 필요하다. 기저 조건에 따르면 원판 1개를 옮기는 횟수는 1회이므로, 이로부터 초항이 1이고 일반항은 2*k + 1인 수열의 합이 곧 원판을 옮기는 총 횟수임을 알 수 있고 이는 곧 2^n - 1 임을 알 수 있…는데 솔직히 유도하는 방법 까먹었다. 등비수열 합 공식이 뭐더라?

N = int(input())

def hanoi(f, t, n):
    if n == 1:
        print(f, t)
        return

    buffer = 6 - f - t
    hanoi(f, buffer, n - 1)
    print(f, t)
    hanoi(buffer, t, n - 1)

print(2 ** N - 1)
hanoi(1, 3, N)

아무튼 이게 왜 올바른 재귀함수인지를 Concrete Example을 가지고 Reasoning 하려면 골 빠개져서 힘들다. 이럴 땐 위에서 설명한 방법처럼 먼저 기저 조건을 정으하고, 그 다음 k에 대해서 잘 동작하면 k + 1일 때에도 잘 동작하니까 나머지는 도미노 쓰러지듯이 주르륵 모든 입력에 대해서 잘 동작한다고 이해하고 넘어가야 한다. 익숙해지자.

1074번: Z

이거는 문제 설명 보면 재귀인건 알겠는데 대체 어떻게 함수를 짜야할지 한번에 떠올리기 힘들 것 같이 생겼다.

일단 함수 원형은 문제 조건에 따라 z(r, c, n)으로, 2^n x 2^n 배열에서 (r, c)를 방문하는 순서를 계산하는 함수라고 하자.

그러면 기저 조건은 아주 자명하게 n = 0 일 때 0일 것이다. n = 1 일 때를 기저로 가져갈 수도 있는데, 예제 입력을 보면 n = 1, r = 0, c = 0일 때 답이 0인걸로 봐서 r, c 그리고 방문 순서까지 전부 0부터 시작한다는 것을 알 수 있다. 따라서 n = 1일 때에는 [[0, 1], [2, 3]][r][c]로 시뮬레이션할 수 있다.

그럼 이제 Inductive Case를 고려해보자. 다음과 같은 사각형일 때

+---+---+
| 1 | 2 |
+---+---+
| 3 | 4 |
+---+---+

(r, c) 가 1번: z(r, c, n - 1)
(r, c) 가 2번: 1번 사각형 크기 + z(r, c - half, n - 1)
(r, c) 가 3번: 1, 2번 사각형 크기 합 + z(r - half, c, n - 1)
(r, c) 가 4번: 1, 2, 3번 사각형 크기 합 + z(r - half, c - half, n - 1)

방문 횟수이므로 사각형 크기의 합을 구하는 건 알겠는데, half는 무엇이며 이걸 왜 빼주는 걸까? z(r, c, n)의 정의가 2^n x 2^n 배열에서 (r, c)를 방문하는 순서이므로, 위와 같이 1, 2, 3, 4번 사각형을 그리고 나면 이 사각형의 각 변 절반의 길이를 half = 2 ^ (n -1)으로 구할 수 있다. 그러면 1, 2, 3, 4번 각 사각형의 크기는 half^2가 되고, (r, c)가 1번이 아닌 다른 사각형에 있다면 half에서 이 값을 빼줌으로써 일종의 zoom in을 할 수 있다.

import sys
N, R, C = map(int, sys.stdin.readline().rstrip().split())

def z(r, c, n):
    if n == 1:
        return [[0, 1], [2, 3]][r][c]
    half = 2 ** (n - 1)
    rect = half * half
    if r < half and c < half:  # 1
        return z(r, c, n-1)
    if r < half and c >= half: # 2
        return rect + z(r, c - half, n - 1)
    if r >= half and c < half:  # 3
        return 2 * rect + z(r - half, c, n - 1)
    return 3 * rect + z(r - half, c - half, n - 1)

print(z(R,C,N))

Last Update: 2023-01-25 11:47:28 PM

Recursion

1629번: 곱셈

11729번: 하노이 탑 이동 순서

1074번: Z