백준_단계별로 풀어보기_21단계_재귀

재귀 단계 (acmicpc.net)

재귀함수를 다뤄 봅시다.

재귀 단계

---

■ 백준 27433 팩토리얼 2_브론즈 5

- 팩토리얼은 단순 for문으로도 구할 수 있지만, 학습을 위해 재귀를 써 봅시다.

def factorial(n):
    if n > 1: return n * factorial(n-1)
    else: return 1

print(factorial(int(input())))

 

■ 백준 10870 피보나치 수 5_브론즈 2

- 피보나치 수 역시 단순 for문으로도 구할 수 있지만, 학습을 위해 재귀를 써 봅시다.

def fibonacci(n):
    if n <= 1:
        return n
    else:
        return fibonacci(n-2) + fibonacci(n-1)
print(fibonacci(int(input())))

# 수정코드: 메모제이션 추가
def fibonacci(n):
    if n in memo:
        return memo[n]
    if n <= 1:
        return n
    else:
        tmp = fibonacci(n-2) + fibonacci(n-1)
        memo[n] = tmp
        return tmp
memo = dict()
print(fibonacci(int(input())))

 

■ 백준 25501 재귀의 귀재_브론즈 2

- 재귀의 동작을 파악하는 문제. 이 문제의 설명을 팰린드롬으로 쓰실 수 있는 분이 계신다면 요청 게시판에 건의 바랍니다. 감사합니다.

import sys
def recursion(s, l, r, cnt):
    cnt += 1
    if l >= r: return "1", str(cnt) #아무 이상없이 순회 마치면 1 반환
    elif s[l] != s[r]: return "0", str(cnt) #인덱스 처음, 끝 쌍이 다르면 0 반환
    else: return recursion(s, l+1, r-1, cnt)
def isPalindrome(s):
    cnt = 0
    return recursion(s, 0, len(s)-1, cnt)

for _ in range(int(input())):
    print(" ".join(isPalindrome(sys.stdin.readline().rstrip())))

# # 고수코드: 재귀가 아니라 그냥 for문으로 해결해버린 것
# import sys
# ans = []
# for _ in range(int(sys.stdin.readline())):
#     s = sys.stdin.readline().rstrip()
#     if s == s[::-1]: # 이렇게 슬라이싱하면 reverse되서 나옴
#         ans.append(f'1 {len(s) // 2 + 1}')
#         continue
#     for i in range((len(s) + 1) // 2):
#         if s[i] != s[-1 - i]:
#             ans.append(f'0 {i + 1}')
#             break
# print("\n".join(ans))

 

■ 백준 24060 알고리즘 수업-병합 정렬 1_실버 3 (복습)

- 재귀를 활용하여 정렬하는 방법을 배우는 문제

• 병합 정렬은 시간복잡도 O(nlogn)
• 하나의 리스트를 두 개의 균일한 크기로 분할 후 각 부분 리스트를 정렬한 다음 병합
• 길이 1까지 쪼갰다가 정렬-병합 반복 시작
• 주의! 문제에선 45132와 같이 홀수인 경우를 병합할 때 45 132가 아닌 451 32처럼 앞이 크게 병합하기 때문에 가운데 기준을 맞춰주는 mid변수에 1을 더해준 뒤 2로 나눔

def merge_sort(arr):
    # 크기가 1이하면 반환
    if len(arr) <= 1:
        return arr

    # 리스트를 2분할
    mid = (len(arr)+1) // 2
    left = arr[:mid]
    right = arr[mid:]

    # 2분할한 리스트를 각각 merge sort진행
    left_sorted = merge_sort(left)
    right_sorted = merge_sort(right)
    return merge(left_sorted, right_sorted)

def merge(left, right):
    i, j = 0, 0
    sorted_list = []

    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            sorted_list.append(left[i])
            ans.append(left[i])
            i += 1
        else:
            sorted_list.append(right[j])
            ans.append(right[j])
            j += 1

    while i < len(left): # 왼쪽 배열 부분이 남은 경우
        sorted_list.append(left[i])
        ans.append(left[i])
        i += 1
    while j < len(right): # 오른쪽 배열 부분이 남은 경우
        sorted_list.append(right[j])
        ans.append(right[j])
        j += 1
    return sorted_list

n, k = map(int, input().split())
arr = list(map(int, input().split()))
ans = []
merge_sort(arr)
print(ans[k-1] if len(ans) >= k else -1)

 

■ 백준 4779 칸토어 집합_실버 3

- "- -"

import sys

def cantor(n):
    if n <= 1: return "-"
    return cantor(n//3) + " " * (n//3) + cantor(n//3)

for x in sys.stdin:
    print(cantor(3**int(x)))

 

■ 백준 2447 별 찍기-10_골드 5 (복습)

- 재귀적인 패턴을 재귀함수로 찍는 문제

• 3x3, 9x9,... 박스를 만들어 나가는 과정을 한 줄씩 구현하였다.
• 2년 전 c언어로도 한참 헤맸었는데 또 헤매서 알고리즘 공부를 등한시한 게 부끄러울 따름이다.
• c언어로 풀었던 메커니즘을 이용하니 파이썬에선 시간초과가 발생했다.
• 그도 그럴게 원소 하나하나를 재귀하는 거였으니...

def star_stamp(n):
    if n == 1:
        return ["*"]
    stars = star_stamp(n//3)
    ans = []
    for x in stars:
        ans.append(x*3)
    for x in stars:
        ans.append(x + " "*(n//3) + x)
    for x in stars:
        ans.append(x*3)
    return ans

n = int(input())
print("\n".join(star_stamp(n)))

 

■ 백준 11729 하노이 탑 이동 순서_골드 5 (복습)

- 너무 깊숙이 들어가지 맙시다. 깊숙히 들어가는 건 컴퓨터가 알아서 해줄 거예요.

# 최초코드: 464ms
# def hanoi(n, from_pos, by_pos, to_pos):
#     if n == 1:
#         ans.append(str(from_pos)+" "+str(to_pos))
#         return
#     hanoi(n-1, from_pos, to_pos, by_pos) #아래 원판 제외 by로 이동
#     ans.append(str(from_pos)+" "+str(to_pos)) #아래 원판 이동
#     hanoi(n-1, by_pos, from_pos, to_pos)#아래 원판 제외 by에서 to로 이동
#
# ans = []
# hanoi(int(input()), 1, 2, 3)
# print(len(ans))
# print("\n".join(ans))

# 수정코드: 56ms / 내 코드에 맞게 메모제이션을 적용해봤는데 고수코드랑 판박이다;;
import sys
def hanoi(n, from_pos, by_pos, to_pos):
    key = (n, from_pos, by_pos, to_pos)
    if key in memo:
        return memo[key]
    elif n == 1:
        return f"{from_pos} {to_pos}"
    tmp = "\n".join([hanoi(n-1, from_pos, to_pos, by_pos), f"{from_pos} {to_pos}", hanoi(n-1, by_pos, from_pos, to_pos)])
    memo[key] = tmp
    return tmp

ans = []
memo = dict()
n = int(input())
print(2**n -1)
sys.stdout.write(hanoi(n, 1, 2, 3))

# #고수코드: 메모이제이션을 활용해서 효율을 높였다.
# def hanoi(value, start, finish, support):
#     key = (value, start, finish, support)
#     if key in memo:
#         return memo[key]
#     if value == 1:
#         return f"{start} {finish}"
#     if value >= 2:
#         output = "\n".join(
#             [hanoi(value - 1, start, support, finish), f"{start} {finish}", hanoi(value - 1, support, finish, start)])
#         memo[key] = output
#         return output
#
# memo = {}
# num = int(input())
# print(f"{2 ** num - 1}")
# print(hanoi(num, "1", "3", "2"))