[백준BOJ] 단계별로 문제풀기 - 재귀 정답 및 후기(파이썬, python)

백준 알고리즘에서 제공되는 문제들 중 단계별로 문제 풀기 - 재귀를 파이썬으로 풀어보았다. 코드는 4문제 통째로 깃허브에 올려놓았으며 각 문제마다 주석으로 표시해놨다.

 

https://www.acmicpc.net/step/19

재귀 단계

원본 코드는 깃허브에!

github.com/tomy9729/Algorithm/blob/master/BaekJoon/Step-by-step%20troubleshooting(%EB%8B%A8%EA%B3%84%EB%B3%84%EB%A1%9C%20%EB%AC%B8%EC%A0%9C%ED%92%80%EA%B8%B0)/10.%20%EC%9E%AC%EA%B7%80.py

tomy9729/Algorithm

0. 전체 후기

재귀란 자기를 정의할 때 자기 자신을 재참조하는 것을 말하며 재귀함수란 자기자신을 다시 호출하는 함수이다. 재귀함수 문제들의 기본 아이디어는 반복적인 구조를 찾는 것이다. 더 나아가 가장 효율적인 구조를 찾는 것이 중요하다. 그런 점에서 문제를 보는 넓은 시야와 창의력이 요구된다고 생각한다. 반복 구조가 한눈에 보이지 않는다면 과정들을 일일이 수행해보는 것도 문제를 푸는데 도움이 된다. 재귀 함수는 잘만 사용하면 시간 복잡도를 줄이는데 큰 도움이 된다. 추후에 재귀 함수 문제들을 더 풀어볼 계획이다.

 

1. 10872번 팩토리얼

재귀함수에 대해서 공부할 때 가장 먼저 풀어보는 팩토리얼 문제이다. 팩토리얼 개념을 알고 있어도 재귀 함수를 처음 배우는 입장에서는 어려울 수 있다. 팩토리얼 문제를 처음 풀었던 대학교 1학년 때는 이 문제를 푸는데 상당히 오래 걸렸었다. 물론 지금은 금방 풀었다. 재귀 함수를 처음 공부할 때 재귀 함수를 어렴풋이 이해하기에 아주 좋은 문제라고 생각한다.

#10872번 팩토리얼
def fact(n) : 
  if n > 0 : 
    return n*fact(n-1)
  else : 
    return 1

n = int(input())
print(fact(n))

 

2. 10870번 피보나치 수 5

함수 구성은 팩토리얼과 비슷하지만 피보나치 수의 재귀함수는 함수 안에 재귀 함수가 두 개 존재한다는 점에서 차이가 있다. 팩토리얼을 풀었다면 쉽게 풀 수 있다. 

#10870번 피보나치 수 5
def fibo(n) : 
  if n == 0 : 
    return 0
  elif n == 1 : 
    return 1
  else : 
    return fibo(n-1) + fibo(n-2)

n= int(input())
print(fibo(n))

 

3. 2447번 별 찍기 -10

반복적인 구조를 찾는 것은 어렵지 않았으나 이를 구현하는데 시간이 꽤 걸렸다. 반복적인 구조를 다음과 같이 설정했다. n*n 정사각형의 크기가 얼마든지 9개의 정사각형으로 나누고 가운데 정사각형만 빈칸으로 찍는다. 다음 겉에 있는 8개의 정사각형에서 반복한다. 단 이를 실제 출력 창에 찍는데 시간이 오래 걸렸다. 처음에는 가장 큰 정사각형부터 찍고 재귀 함수를 통해 작은 정사각형에서 반복할 때 이미 찍혀버린 별을 빈칸으로 바꾸려고 했다. 단 이렇게 하려니 빈칸의 위치를 특정하기가 어려웠다. 그래서 처음부터 알맞게 찍는 방법으로 했다. 가장 큰 정사각형 기준으로 가운데 정사각형만 빈칸으로 두고 나머지 정사각형은 재귀 함수를 통해 해당 위치에 맞는 값만 가져오도록 한다. 

#2447번 별 찍기-10
def star(n) :
  if n == 3 : 
    return [['*','*','*'],['*',' ','*'],['*','*','*']]
  arr = [[0]*n for i in range(n)] #입력받은 크기만큼의 n*n 배열을 만든다.
  temp = star(n//3) #시간초과를 회피하기 위함. 반복문 전에 재귀함수를 한 번만 수행하도록 한다.
  for i in range(n) : 
    for j in range(n) : 
      if i >= n//3 and i < 2*n//3 and j >= n//3 and j < 2*n//3 : #빈칸으로 두는 조건
        arr[i][j] = ' '
      else :
        arr[i][j] = temp[i%(n//3)][j%(n//3)] #좌표에 해당하는 값만 가져온다.
  return arr

n=int(input())
x = star(n)
for i in range(n):
    for j in range(n):
        print(x[i][j],end='')
    print(end='\n')

 

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

재귀함수 문제에서 팩토리얼만큼이나 유명한 하노이탑 문제이다. 그러나 나는 하노이탑 문제를 풀어본 적이 없어서 시간이 꽤 오래 걸렸다. 위 문제들과는 달리 아이디어가 바로 떠올리지 않아 하노이탑 게임을 직접 플레이해봤다. 규칙을 찾기 위해 약 30판 정도 해본 것 같다. 두 가지 규칙을 찾을 수 있었는데 가장 먼저 발견했던 것이 탑의 크기에 따른 최소 이동수였다. 하노이탑은 층을 하나 높일 때마다 최소 이동 수는 하나 낮은 탑의 이동수에 2를 곱하고 1을 더한 값이다. 예를 들어 하노이탑 n층의 최소 이동수가 x라면 하노이탑 n+1층의 최소 이동수는 2x+1이다. 이 사실을 알고 나니 하노이탑의 규칙이 눈에 들어왔다. 하노이탑에서 가장 아래 원판을 옮기기 위해서는 그 위에 쌓여있는 또 하나의 하노이탑을 옮겨야 한다. 즉 하노이탑 n층을 옮기기 위해서는 하노이탑 n-1층을 먼저 옮겨야 한다. 그다음 가장 아래 원판은 목적지로 옮기고 한 번 더 하노이탑 n-1층을 이동시킨다. 그렇다면 하노이탑 n-1층은 어떻게 옮기지? 마찬가지다. 하노이탑 n-2층을 옮기면 된다. 이 구조를 재귀 함수로 표현할 수 있다. 

처음에는 함수에 원판번호, 출발지, 도착지만 매개변수로 두어 함수를 만들었으나 이렇게 만들면 재귀 함수로 만들 수 없어 경유지라는 새로운 매개변수를 추가했다. 하노이탑에서 원판을 옮길 수 있는 위치는 세 군데이며 이는 모두 출발지, 도착지, 경유지로 구성되게 만들 수 있다. 재귀 함수 과정에서 출발지, 도착지, 경유지를 헷갈리지 않도록 유의하자.

#11729번 하노이탑 이동 순서
n = int(input())
c = 0

def hanoi(n,s,d,v) : # n : 원판번호 s : 출발지 d : 도착지 v : 경유지
  if n == 1 : 
    print("{} {}".format(s,d)) 

  else : 
    hanoi(n-1,s,v,d)
    print("{} {}".format(s,d))
    hanoi(n-1,v,d,s)

def count(n) : 
  if n == 1 : return 1
  else : 
    return 2*count(n-1)+1
  
print(count(n))  
hanoi(n,1,3,2)