프로그래밍 일지

problem 문제링크: https://www.acmicpc.net/problem/11726 알고리즘 : 다이나믹 프로그래밍 입력 - n solution 2*n 크기의 직사각형을 2*1 의 타일로 채우는 경우의 수는 n+1 번째의 피보나치수와 같다. dp[] 배열의 1, 2번째에 피보나치수 1, 1 을 할당해둔다. n까지 피보나치 수를 구해 10007로 나눈 나머지 값을 dp의 i 번째에 넣는다. n+1 까지 피보나치 (수 % 10007) 을 한 값을 구하고 dp[n]을 출력한다.[ [code] n = int(input()) dp = [1, 1] for i in range(2, n + 1): dp.append((dp[i - 1] + dp[i - 2]) % 10007) print(dp[n])

문제링크 : www.acmicpc.net/problem/10870 가장 기본적인 피보나치 수 문제로 재귀함수를 이용하여 풀 수 있다. [code]

문제링크 : www.acmicpc.net/problem/2748 피보나치 함수 - 재귀함수의 시간복잡도를 줄이기 위해 2742번에서 사용했던 매모이제이션을 사용한다 - n 이 90 일때 피보나치수 = 2880067194370816120 -> 피보나치함수와 메모이제이션 long long 형 사용 [code]

문제링크 : www.acmicpc.net/problem/2747 피보나치 시리즈 첫 번쨰 문제이다 피보나치수5(www.acmicpc.net/problem/10870) 로 풀었던 코드로 풀어보려 했으나 시간 초과가 나서 메모이제이션 으로 풀었다. 메모이제이션(memomemoization) - 피보나치수를 구하는 재귀함수는 재귀 횟수가 N² 으로 늘어나기 떄문에 fibo(n) 번째의 값을 기억해두고 다음에 호출이 필요할때 다시 재귀하는것을 방지하는 역할을 한다 [code]