7490번: 0 만들기 각 테스트 케이스에 대해 ASCII 순서에 따라 결과가 0이 되는 모든 수식을 출력한다. 각 테스트 케이스의 결과는 한 줄을 띄워 구분한다. www.acmicpc.net ** 문제 유형 재귀 호출, 완전 탐색 ** 풀이 자연수 N의 범위(3

1074번: Z 한수는 크기가 2N × 2N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다. 만약, N > 1이 라서 www.acmicpc.net ** 문제 유형 재귀 함수, 분할 정복 ** 풀이 Z 모양을 구성하는 4가지 방향에 대하여 차례대로 재귀적으로 호출 def sol(n, r, c): global result if n == 2: if r == R and c == C: print(result) return result += 1 if r == R and c + 1 == C: print(result) return result += 1 if r + 1 == R and c == C: print(re..

2747번: 피보나치 수 피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 www.acmicpc.net ** 문제 유형 재귀 함수 ** 풀이 피보나치 수열의 점화식 재귀 함수를 이용해 문제를 풀 수 있는지 검토 N은 최대 45 재귀적 구현의 한계: 과도한 중복 호출 -> O(2^n) n = int(input()) a, b = 0, 1 while n > 0: a, b = b, a + b n -= 1 print(a) f(n) 0 1 1 2 3 a b a + b ... ... a b ... ... a b ... a b

** 재귀 용법(Recursive Call, 재귀 호출) 함수 안에서 동일한 함수를 호출하는 형태 ** 예제 팩토리얼을 구하는 알고리즘 분석: 규칙이 보임 n! = n * (n-1)! def factorial(num): if num > 1: return num * factorial(num - 1) else: return num ** 예제: 시간 복잡도와 공간 복잡도 factorial(n) 은 n - 1 번의 factorial() 함수를 호출해서, 곱셈을 함 일종의 n-1번 반복문을 호출한 것과 동일 factorial() 함수를 호출할 때마다, 지역변수 n 이 생성됨 시간 복잡도/공간 복잡도는 O(n-1) 이므로 결국, 둘 다 O(n) ** 재귀 호출의 일반적인 형태 # 일반적인 형태1 def functi..