https://www.acmicpc.net/problem/1003
1003번: 피보나치 함수
각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다.
www.acmicpc.net
문제 이해
피보나치 함수 문제는 피보나치를 재귀함수로 풀었을 때, 0과 1이 각각 몇 번씩 등장하게 되는지에 대한 문제이다. 문제에서는 코드 예시를 C언어로 해두었다.
문제에 들어가기 전에 파이썬은 재귀함수를 사용할때 늘 깊이에 대한 생각을 하지 않을 수 없다. 왜냐하면 파이썬 언어 내부적으로 재귀함수의 깊이를 1000회로 제한을 두었기 때문이다.
백준 1676 팩토리얼 0의 개수 파이썬 풀이 - recursionError
https://www.acmicpc.net/problem/1676 1676번: 팩토리얼 0의 개수 N!에서 뒤에서부터 처음 0이 아닌 숫자가 나올 때까지 0의 개수를 구하는 프로그램을 작성하시오. www.acmicpc.net 코드 1 def factorial(num) : if num ==
juice-in-fruit.tistory.com
이전에 팩토리얼 문제 풀면서 파이썬에서의 재귀 깊이를 다룬 내용이다. 심심하면 참고하면 좋을듯하다!
기본적으로 파이썬은 재귀의 깊이를 1000회로 걸어두었고 그 제한을 풀 수 있지만 권장되는 방법은 아니다. 정도만 짚고 문제로 다시 돌아가보도록 하자.
접근법
재귀함수를 돌리면서 0 또는 1이 등장할때마다 count += 1 하는 식으로 접근하면 좋을 듯 하지만 앞서 말했듯이 파이썬은 재귀로 돌리려고 했다간 에러를 마주하게 될 테니 강제로 다른 알고리즘을 선택해야 한다(거의 반 강제다). 대표적인 방법은 DP(Dynamic Programming)가 있다. 값을 저장하여 계산의 횟수를 줄이는 방법이다.
입력받은 숫자 n에 대하여 각각 0,1이 몇번 등장하는지 값을 저장해 두면 메모리를 사용하는 대신 연산량을 줄일 수 있다.
코드
import sys
t = int(sys.stdin.readline().strip())
memo = {0:[1, 0], 1:[0,1]} # key-val의 val은 [0의 개수, 1의 개수]
def fibonacci(n:int) -> int:
for i in range(2, n + 1) :
if i not in memo :
memo[i] = [memo[i - 1][0] + memo[i - 2][0] , memo[i - 1][1] + memo[i - 2][1]]
return memo[n]
for _ in range(t) :
n = int(sys.stdin.readline().strip())
answer = fibonacci(n)
print(answer[0], answer[1])
시간복잡도
dp를 사용하지 않고 재귀로 풀게 되면 fibonacci(n), fibonacci(n - 1), fibonacci(n - 2)...... n이 0 혹은 1이 될때까지 이어나가게 된다. 시간복잡도는 O(2^n)가 된다. 반면 dp를 사용하여 풀게 되면 입력받게 되는 t와 입력받는 숫자 n으로 O(t * n)가 된다. 문제에서 T의 범위는 주어지지 않았지만 N은 40보다 작거나 같은 자연수라 하였기에 O(T)의 시간복잡도라고 할 수 있다. 코딩테스트에서 보통 시간복잡도가 10^8승을 넘지 않으면 풀 수 있기 때문에 적당한 알고리즘을 택해 풀었다고 생각할 수 있겠다.
이 문제는 DP문제가 낯선 사람들에게 다이나믹 프로그래밍에 적응할 수 있는 문제라고 생각됐다. 처음 DP문제를 접하면 어떤 식으로 접근해야 할지 매우 난감한데 팁은 손으로 직접 몇 가지 경우의 수를 노트에 쓰거나 그려보는 걸 추천한다. dp는 결국 점화식을 구하는 것이 중요하기 때문이다.
'알고리즘' 카테고리의 다른 글
백준 11726 2xn 타일링 파이썬 풀이 (0) | 2024.02.07 |
---|---|
백준 1181 단어정렬 파이썬 풀이 (3) | 2024.02.07 |
백준 1676 팩토리얼 0의 개수 파이썬 풀이 - recursionError (0) | 2024.01.19 |
백준 10992 별 찍기 - 17 파이썬 풀이 (2) | 2024.01.18 |
백준 10991 별 찍기 - 16 파이썬 풀이 (0) | 2024.01.18 |