백준 알고리즘 9단계 (재귀함수)

• 새롭게 배운 내용

1) 10872번 팩토리얼

재귀 함수란 자기 자신을 호출하는 함수를 말한다.
즉, 정의 단계에서 자기 자신을 호출시킨다.
이를 활용하여 팩토리얼을 구현해봤다.

N = int(input())

# 입력한 값까지 곱해주는 재귀함수
def factorial(i, n):
    if i <= N:
        n *= i
        i += 1
        return factorial(i, n)
    else:
        return n

# n과 i에 1을 넣어 재귀함수 호출
print(factorial(1, 1))

2) 피보나치 수

피보나치 수는 0번째는 0 1번째는 1로 시작되며, n = (n-1) + (n-2) 로 정의된다.

n = int(input())

# 파라미터로 들어온 입력값은 재귀를 통해 (n-1)과 (n-2)로 나누어지며
# 결국 0 또는 1이 될 때까지 재귀함수를 호출하여 0과 1이 더해진다.
def fibonacci(i):
    if i == 0:
        return 0
    elif i == 1:
        return 1
    else:
        return fibonacci(i-1) + fibonacci(i-2)

print(fibonacci(n))

3) 2447번 별찍기 (재귀함수, 프랙탈 구조)

❌❌❌ <1회차 최종 실패! -> 코드 리뷰 및 이해에 초점>

처음에 핵심 구조 (프랙탈 구조)임을 이해하고 이에 대한 코드를 작성하려 했다.
2차원 배열에 대한 개념이 없어서 1차원 배열을 활용하여 재귀함수로 정답코드를 작성하려하다 보니 굉장히 애를 먹었던 문제이다.
구글링하여 정답 코드를 참고해보니 1차원 배열을 이용한 답안은 모두 반복문을 사용했다.
나는 공부하는 입장이기에 재귀함수로 완성 코드를 탐구하고 싶었고, 2차원 배열을 활용한 (아주 깔끔하고 논리적인..) 코드를 운좋게 찾을 수 있었다. 작성자님의 조언대로 디버깅을 해보며 결국 이해까지는 완료한 상태이다.
따라서 아래에는 내가 작성한 것이 아니며 고수님의 코드에 내가 이해한대로 주석만을 덧붙인 코드를 첨부한다.
출처:https://study-all-night.tistory.com/5
2차원 배열에 대한 개념 없이 이해하다보니 상당히 시간이 오래 소요되었지만 결국 내 나름대로 이해할 수 있었고, 앞으로 2차원 배열을 더욱 학습하고 꼭 다시 풀어보고 싶은 문제이다. 그때는 내가 작성한 코드를 밑에 덧붙이겠다.

# 별 찍는 재귀 함수
def draw_star(n):
    # 전역 변수인 Map을 불러온다.
    global Map

    # n이 3이 될 때 까지 recursion하여  n이 3일 때의 3x3 2차원 배열을 전체 배열의 [:3][:3]에 입력해준다.
    if n == 3:
        Map[0][:3] = Map[2][:3] = [1] * 3
        Map[1][:3] = [1, 0, 1]
        return

    a = n // 3
    draw_star(n // 3)
    # 3의 거듭제곱 단계별로 아래 반복문이 돌며 값이 채워진다
    # 범위가 3인 것은 모든 단계에서 크게보면 결국 이전 단계의 결과가 한칸으로 3x3 배열을 채우기 때문이다.
    for i in range(3):
        for j in range(3):
            # 모든 단계에서 가운데에 들어가는 칸은 0 그대로 냅둔다 (공백)
            if i == 1 and j == 1:
                continue
            # 3의 거듭제곱 범위에서,
            for k in range(a):
                # 좌항은 Map의 [3의 거듭제곱 x 0,1,2중 하나(행)][3의 거듭제곱 x 0,1,2 : 3의 거듭제곱 x 1,2,3까지(열)]
                # 즉 좌항은 새롭게 값이 들어갈 부분이고,
                # 우항은 기존에 값이 들어가 있던곳이자 좌항에 넣어줄 값이 된다 ( 프랙탈 구조이기에 반복되기 때문)
                Map[a * i + k][a * j:a * (j + 1)] = Map[k][:a]  # 핵심 아이디어


N = int(input())

# 메인 데이터 선언 (입력 받은 값 x 입력 받은 값의 배열을 만들어준다.)
Map = [[0 for i in range(N)] for i in range(N)]

draw_star(N)

# 0행 부터 순차적으로 배열에 담긴 값을 * 혹은 공백으로 출력해준다.
for i in Map:
    for j in i:
        if j:
            print('*', end='')
        else:
            print(' ', end='')
    print()

4) 11729번 하노이 탑 이동순서

❌❌❌ <1회차 최종 실패! -> 코드 리뷰 및 이해에 초점>

재귀함수의 대표 예제
핵심은 a(n) = 2a(n-1) + 1 이다.
예를들어 a(5)가 첫번 째 장판에 있는 경우는 a(4)의 원판(1,2,3,4)을 2번째 장판으로 옮길 때 a(4), 5번 째 원판을 3번째 장판으로 옮길 때 1, 마지막으로 2번째 장판에 있는 a(4) 원판들을 다시 a(5)로 옮길 때 a(4)가 된다.
따라서 위 세가지 단계
1) a(n-1)을 1번에서 2번까지 옮기기
2) n원판을 1번에서 3번으로 옮기기
3) a(n-1)을 2번에서 3번으로 옮기기
로 정리가 된다.
아래 코드는 위 3단계에 따라 recursion하는 함수를 구현한 것이다.

N = int(input())

def hanoiCnt(n):
    if n == 1:
        return 1
    else:
        return 2 * hanoiCnt(n-1) + 1

def hanoi(n, from_, to_, via_):
    if n == 1:
        print( str(from_) + ' ' + str(to_))
    else:
    	# 1단계
        hanoi(n-1, from_, via_, to_)
        # 2단계
        print(str(from_) + ' ' + str(to_))
        # 3단계
        hanoi(n-1, via_, to_, from_)

print(hanoiCnt(N))
hanoi(N, 1, 3, 2)