직접 풀어보자! 재귀 5문제
안녕, 나 코딩냥이다냥! 재귀 문제는 작은 값을 손으로 따라가보는 것이
거의 전부라냥. n = 2 나 n = 3 으로 종이에 그려보고 시작하자냥. 그것만
하면 코드는 서너 줄이라냥.
재귀를 짤 때 순서
- 멈추는 조건을 먼저 쓴다 — 가장 작은 경우에 뭘 해야 하냥?
- 자기 호출을 쓴다 — 더 작은 문제로 어떻게 넘기냥?
- 호출 앞뒤에 할 일을 넣는다 — 언제 출력하고 언제 더하냥?
1번을 빼먹으면 RecursionError 로 터진다냥. 항상 먼저 쓰자냥.
0 과 1 로 된 길이 n 인 문자열을 전부 사전순으로 출력한다냥.
갈래가 두 개라냥 — 지금 자리에 0 을 놓느냐 1 을 놓느냐라냥.
0 을 먼저 부르면 0 으로 시작하는 게 전부 먼저 나와서 사전순이
된다냥. 순서를 바꾸면 결과가 뒤집힌다냥.
n = int(input())
def go(cur):
if len(cur) == n:
# 완성됐다냥
return
# 0 갈래와 1 갈래를 부른다냥
go("")원판 n개를 1번에서 3번으로 옮기는 횟수와 순서를 출력한다냥.
기둥 세 개의 역할이 호출마다 바뀐다냥. 이게 이 문제의 전부라냥.
hanoi(k-1, start, via, end) # 목적지가 via 로 바뀐다냥
print(start, end)
hanoi(k-1, via, end, start) # 출발지가 via 로 바뀐다냥인자 순서를 헷갈리면 횟수는 맞는데 이동 순서가 틀린다냥. 채점기는 순서까지 본다냥.
답은 1 2, 1 3, 2 3 이라냥.
작은 원판을 2번에 잠깐 두고, 큰 원판을 3번으로 보내고, 작은 원판을 3번에
얹는다냥. 이 세 줄이 나오는지 먼저 확인하고 n = 3 으로 넘어가자냥.
n = int(input())
moves = []
def hanoi(k, start, end, via):
if k == 0:
return
# 위 k-1개를 via 로, 큰 거 하나를 end 로, 다시 k-1개를 end 로
hanoi(n, 1, 3, 2)
print(len(moves))
for m in moves:
print(m)n번째 피보나치 수를 출력한다냥. n 이 90까지 간다냥.
순수 재귀로 짜면 시간 초과가 난다냥. 숨겨진 테스트에 큰 n 이 있다냥.
같은 값을 다시 계산하지 않도록 적어두면서 풀어야 한다냥.
세 가지 방법이 다 된다냥. 재귀 연습이 목적이니 앞의 둘을 추천한다냥.
- 딕셔너리에 직접 적어두기 (메모이제이션)
@lru_cache(None)붙이기- 3장에서 배운 반복문으로 풀기
F(0) = 0 이라는 것도 확인하자냥. F(0) = 1 로 두면 전부 한 칸씩 밀린다냥.
from functools import lru_cache
# @lru_cache(None) 을 붙여보자냥
def fib(k):
if k < 2:
return k
return fib(k-1) + fib(k-2)
print(fib(int(input())))a 를 b번 곱한 값을 m 으로 나눈 나머지를 출력한다냥. b 가 10^18 까지
간다냥.
b 번 반복하면 절대 못 끝낸다냥. 지수를 절반으로 쪼개야 한다냥.
그리고 절반을 구한 결과는 변수에 담아 한 번만 부르자냥.
half = power(a, b // 2) # 이렇게냥power(a, b//2) * power(a, b//2) 라고 쓰면 두 번 계산해서 빨라지는 효과가
사라진다냥.
곱할 때마다 % m 을 해주자냥. 안 하면 숫자가 어마어마하게 커진다냥.
b = 0 인 경우도 확인하자냥. 답은 1 % m 이라냥. m 이 1이면 0이라냥.
a, b, m = map(int, input().split())
def power(base, e):
if e == 0:
return 1 % m
half = power(base, e // 2)
# 짝수면 half*half, 홀수면 half*half*base 라냥. 매번 % m 하자냥
print(power(a % m, b))주어진 수 중 하나 이상을 골라 더해서 target 을 만들 수 있는지 판별한다냥.
각 수마다 갈래가 두 개라냥 — 고르거나, 안 고르거나. 1번 문제와 똑같은 구조라냥.
go(i+1, sum + arr[i]) # i번째를 고른다냥
go(i+1, sum) # 안 고른다냥"하나 이상" 이라는 조건을 놓치면 안 된다냥.
아무것도 안 고르면 합이 0이라, target 이 0일 때 무조건 YES 가 나와
버린다냥. 몇 개를 골랐는지 같이 넘기면서 세자냥.
숨겨진 테스트가 정확히 이걸 확인한다냥.
n, target = map(int, input().split())
arr = list(map(int, input().split()))
found = False
def go(i, s, picked):
global found
if i == n:
# picked 가 0보다 크고 s 가 target 이면 찾은 거다냥
return
# 고르는 갈래와 안 고르는 갈래
go(0, 0, 0)
print("YES" if found else "NO")다 풀었냥?
1번과 5번이 똑같은 구조였다는 걸 봤냥? "각 자리마다 두 갈래"라냥. 하나는 문자를 붙이고 하나는 수를 고르는 것뿐, 뼈대는 같다냥. 재귀를 익히면 이런 문제들이 한 묶음으로 보이기 시작한다냥.
스스로 점검해보자냥
- 다섯 문제를 전부 채점기에서 통과했냥?
- 멈추는 조건을 왜 먼저 쓰는지 설명할 수 있냥?
- 3번에서 메모이제이션이 왜 필요했는지 설명할 수 있냥?
- 4번에서
half를 변수에 담는 이유를 설명할 수 있냥?
일곱 챕터를 다 왔다냥! 훑기, 문자열, 누적, 정렬, 세기, 이분 탐색, 그리고 재귀까지라냥. 특히 재귀는 나중에 배울 트리와 그래프의 바탕이라냥. 지금 어질어질해도 괜찮다냥. 손으로 따라가는 연습을 계속하면 어느 순간 자연스러워진다냥. 정말 수고했다냥~