BOJ 재귀함수

하노이

# from_pos는 도형들이 시작하는 위치
# to_pos는 도형들이 가야할 곳
# aux_pos는 둘 다 제외한 보조 기둥

count = 0
lst =[]
def hanoi(n, from_pos, to_pos, aux_pos):
    if n== 1: # n이 1일 때는 그냥 옮겨주면 된다.
        lst.append(from_pos)
        lst.append(to_pos)
        global count
        count += 1
        return  #그러고는 함수 끝내기

    hanoi(n-1, from_pos, aux_pos, to_pos) # n-1개의 도형들이 보조기둥에 위치해야한다.(재귀 함수 호출)
    lst.append(from_pos) # n번째 가장 큰 도형을 3번으로 옮긴다.
    lst.append(to_pos)
    count += 1
    hanoi(n-1, aux_pos, to_pos, from_pos) # 보조기둥의 n-1개를 3번으로 옮겨야한다. (재귀 함수 호출)

n = int(input())
hanoi(n, 1, 3, 2)
print(count)
for i in range(0, len(lst), 2):
    print(lst[i], lst[i+1])

참고 출처

이 문제는 솔루션을 참고했다.
원리는 아래와 같다.

1. N-1개의 도형들을 aux pos에 위치하도록 한다.
2. N 번째 도형을 목표지점(3번)으로 옮긴다.
3. 1번의 도형들을 3번으로 옮긴다.

이런 의문이 들 것이다.

한 번에 하나의 도형만 옮길 수 있는데 1번이 가능한가?

위와 같은 접근은 문제를 역순으로 풀어나간 것이다. 재귀함수 안에서 다시 재귀함수를 불러서 반복되는 과정 속에서 n-1개 -> n-2개 ..... -> 1개까지 거꾸로 풀려나간다. 그렇게 되면 한 번에 하나씩 옮긴다는 규칙을 만족하게 된다.

재귀함수를 만들 때는

1. 패턴을 파악해서 한단계씩 분해하고
2. 반복을 멈출 조건을 걸어주고
3. 가장 마지막 단계에서부터 맨 처음 단계까지 역순으로 어떻게 풀어나갈지 그려보는 게 중요한 것 같다.

별찍기

# 별찍기
n_ = int(input())
k_ = n_**(1/3)
# k_ = 3
# n_ = 3**k_
square = [['*' for _ in range(n_)] for _ in range(n_)]
def star(n, k, row_start, col_start):
    # k=1일 때
    if k==1:
        square[row_start+1][col_start+1] = ' '
        return
    col_range = range(col_start+3**(k-1), col_start+3**(k-1)*2)
    row_range = range(row_start + 3 ** (k - 1), row_start + 3 ** (k - 1) * 2)
    for row in range(n):
        if row in row_range:
            for col in range(n):
                if col in col_range:
                    square[row][col] = ' '

    # 가운데 빈칸 제외 n-1패턴으로 채우기
    for ii in range(0, n, n//3): # row
        for kk in range(0, n, n//3): # col
            star(n-1, k-1, ii, kk)
star(27, 3, 0, 0)
for i in square:
    for ii in i:
        print(ii, end='')

디버깅해야한다.
아이디어는 맞았으나, 틀렸다.