i can do ik!

1916 : (재귀함수) 피보나치 수열 (Large)

문제 설명

피보나치 수열이란 앞의 두 수를 더하여 나오는 수열이다.

첫 번째 수와 두 번째 수는 모두 1이고, 세 번째 수부터는 이전의 두 수를 더하여 나타낸다. 

피보나치 수열을 나열해 보면 다음과 같다.

1,1,2,3,5,8,13…
 
자연수 N을 입력받아 N번째 피보나치 수를 출력하는 프로그램을 작성하시오.

단, N이 커질 수 있으므로 출력값에 10,009를 나눈 나머지를 출력한다.

※ 이 문제는 반드시 재귀함수를 이용하여 작성 해야한다.

금지 키워드 : for, while, goto
시간 제한 : 1 Sec
메모리 제한 : 128 MB

입력

자연수 N이 입력된다. (N은 200보다 같거나 작다.)

출력

N번째 피보나치 수를 출력하되, 10,009를 나눈 나머지 값을 출력한다.

입력 예시

7

출력 예시

13

풀이

※ 주의 : 시간초과 -> DP의 전형적인 문제로 판단하여 Memorization이 필요

※ Memorization에 대해서는 뒤에서 자세히 알아보자

def fibonacci(n):
  if n == 0 or n == 1:
    return n
  if l[n] == 0:
    l[n] = fibonacci(n-1) + fibonacci(n-2)
  return l[n]
  
N = int(input())
l = [0]*201
print(fibonacci(N)%10009)

1915 : (재귀함수) 피보나치 수열

문제 설명

피보나치 수열이란 앞의 두 수를 더하여 나오는 수열이다.

첫 번째 수와 두 번째 수는 모두 1이고, 세 번째 수부터는 이전의 두 수를 더하여 나타낸다. 

피보나치 수열을 나열해 보면 다음과 같다.

1, 1, 2, 3, 5, 8, 13 …

자연수 N을 입력받아 N번째 피보나치 수를 출력하는 프로그램을 작성하시오.

※ 이 문제는 반드시 재귀함수를 이용하여 작성 해야한다.

금지 키워드 : for, while, goto
시간 제한 : 2 Sec
메모리 제한 : 128 MB

입력

자연수 N이 입력된다. (N은 20보다 같거나 작다.)

출력

N번째 피보나치 수를 출력한다.

입력 예시

7

출력 예시

13

풀이

def fibonacci(n):
    if n == 0:
        return 0
    elif n == 1 or n == 2:
        return 1
    else:
        return fibonacci(n-2) + fibonacci(n-1)

n=int(input())

fibonacci(n)

print(fibonacci(n))

1912 : (재귀함수) 팩토리얼 계산

문제 설명

팩토리얼(!)은 다음과 같이 정의된다.

n!=n×(n−1)×(n−2)×⋯×2×1

즉, 5!=5×4×3×2×1=120 이다.

n이 입력되면 n!의 값을 출력하시오.

이 문제는 반복문 for, while 등을 이용하여 풀수 없습니다.

금지 키워드 : for, while, goto
시간 제한 : 1 Sec
메모리 제한 : 128 MB

입력

자연수 n이 입력된다. (n<=12)

출력

n!의 값을 출력한다.

입력 예시

5

출력 예시

120

풀이

def factorial(a):
    if a==1:
        return 1
    return a*factorial(a-1)

n = int(input())

factorial(n)

print(factorial(n))

1905 : (재귀함수) 1부터 n까지 합 구하기

문제 설명

정수 n이 입력으로 들어오면 1부터 n까지의 합을 구하시오.

이 문제는 반복문 for, while 등을 이용하여 풀수 없습니다.

금지 키워드 : for, while, goto
시간 제한 : 1 Sec
메모리 제한 : 128 MB

입력

입력으로 자연수 n이 입력된다. (1<=n<=10,000)

출력

1부터 n까지의 합을 출력한다.

입력 예시

100

출력 예시

5050

풀이

import sys
sys.setrecursionlimit(1000000)

res = 0
def func(n):
  global res
  if(n!=1):
    func(n-1)
  res += n
  
func(int(input()))
print(res)

1904 : (재귀함수) 두 수 사이의 홀수 출력하기

문제 설명

시작수(a)와 마지막 수(b)가 입력되면

a부터 b까지의 모든 홀수를 출력하시오.

이 문제는 반복문 for, while 등을 이용하여 풀수 없습니다.

금지 키워드 : for, while, goto
시간 제한 : 1 Sec
메모리 제한 : 128 MB

입력

두 수 a, b 가 입력된다. (1<=a<=b<=100)

출력

a~b의 홀수를 모두 출력한다.

입력 예시

2 7

출력 예시

3 5 7

풀이

a, b = map(int,input().split())

def odd(a,b):
    if a%2 == 1:
        print(a, end=' ')
    if a==b:
        return

    odd(a+1,b)
odd(a,b)

1902 : (재귀 함수) 1부터 n까지 역순으로 출력하기

문제 설명

정수 n부터 1까지 출력하는 재귀함수를 설계하시오.

이 문제는 반복문 for, while 등을 이용하여 풀수 없습니다.

금지 키워드 : for, while, goto
시간 제한 : 1 Sec
메모리 제한 : 128 MB

입력

정수 n이 입력된다(1<=n<=200)

출력

n부터 1까지 한 줄에 하나씩 출력한다.

입력 예시

10

출력 예시

10
9
8
7
6
5
4
3
2
1

풀이

n = int(input())
def func(n):
  print(n)
  if(n!=1):
    func(n-1)
func(n)

1901 : (재귀 함수) 1부터 n까지 출력하기

문제 설명

1부터 정수 n까지 출력하는 재귀함수를 설계하시오.

이 문제는 반복문 for, while 등을 이용하여 풀수 없습니다.

금지 키워드 : for while goto
시간 제한 : 1 Sec
메모리 제한 : 128 MB

입력

정수 n이 입력된다(1<=n<=200)

출력

1부터 n까지 한 줄에 하나씩 출력한다.

입력 예시

10

출력 예시

1
2
3
4
5
6
7
8
9
10

풀이

n = int(input())
def func(n):
  if(n!=1):
    func(n-1)
  print(n)
  
func(n)

재귀란

• 컴퓨터 과학에서 재귀란 자신을 정의할 때 자기 자신을 재참조하는 방법을 의미한다.

재귀함수란

• 함수가 직접 또는 간접적으로 자신을 호출하는 프로세스.
• 재귀 알고리즘을 이용하면 복잡한 문제들도 간단하게 해결 할 수 있다.
• 호출이 깊어지면 성능의 저하가 있을 수 있다.
• 종료지점을 구현하지 않으면 스택 오버플로우가 발생할 수 있다.

재귀함수 장단점

장점

• 변수의 사용을 줄여준다.
• 코드의 가독성을 높일 수 있다.

단점

• 시간복잡도가 반복문에 비해 계산이 어렵다.
• 반복문보다 메모리 사용량이 많고 수행 시간이 더 길어질 수 있다.
• 함수 호출을 많이 하기에 StackOverFlow의 가능성이 잇다.
• 종결조건을 정하지 않으면 무한 반복이 일어난다.

재귀함수 사용의 예

• 1부터 n까지의 합
• ! 팩토리얼
• 최대공약수 문제
• 피보나치 수열 구하기
• 문자열의 길이를 구하는 등의 문제
• 2진수 변환하기 문제
• 배열 총합 문제