반응형 피보나치 수열3 피보나치 수를 구하는 다양한 방법 알고리즘 문제를 풀다 보니 피보나치 수를 구하는 방법이 상당히 많다. 따라서 이 피보나치 수로 배울 수 있는 알고리즘이 다양하기에 한번 정리를 해보려고 한다. 피보나치 수열이란? 기원전 5세기 인도의 수학자 핑갈라가 쓴 책에서 처음 언급 됐으며 유럽에서 레오나르도 피보나치가 토끼 수의 증가에 대해서 이야기 하면서 유명해졌다. 해당 내용은 n번째 달의 토끼 쌍의 수는 첫 달에는 새로 태어난 토끼 한 쌍만이 존재한다. 두 달 이상이 된 토끼는 번식이 가능하다. 번식 가능한 토끼 한 쌍은 매달 새끼 한 쌍을 낳는다. 토끼는 죽지 않는다 이 문제를 통해서 나온 것이 바로 피보나치 수열이다. 첫 번째 달, 두 번째 달 까지는 1쌍이 존재할 것이다. 세 번째 달이 되면서 토끼가 번식이 가능해지면서 2쌍이 되고 3번.. 2022. 4. 6. 백준 11444: 피보나치 수 6 (파이썬) 문제: https://www.acmicpc.net/problem/11444 11444번: 피보나치 수 6 첫째 줄에 n이 주어진다. n은 1,000,000,000,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 코드 # https://teching.tistory.com/ import sys def matrixMultiple(matrix1, matrix2): res = [[0]*len(matrix2[0]) for _ in range(len(matrix1))] for i in range(len(matrix1)): for j in range(len(matrix2[0])): for k in range(len(matrix1[0])): res[i][j] += matrix1[i][k] .. 2022. 4. 6. 동적 계획법 (파이썬) 기본적인 접근 방식은 분할 정복 알고리즘과 비슷하다. 문제를 부분 문제로 나누어 각 부분 문제의 답을 계산하고, 이 계산한 결괏값을 이용해 원래 문제의 답을 산출한다. 그러나 동적 계획법은 문제를 나눌 때 부분 문제를 최대한 많이 이용하도록 나눈 다음, 주어진 부분 문제의 정답을 한번만 계산하고 저장해둔 뒤 다시 한 번 해당 문제를 풀 때에는 저장해둔 답을 바로 산출하여 속도를 향상한 것이다. 동적 계획벅을 구현하는 방법은 2가지가 있다. 하향식으로 문제를 풀어나가는 메모이제이션(Memoization) (주의 :메모라이제이션(Memorization) 아님!!) 상향식으로 문제를 풀어나가는 타뷸레이션(Tabulation) 즉, 계산했던 걸 저장한다라는 것이 핵심인 것이다. (캐싱이라고도 불림) 말로 하면 .. 2022. 2. 7. 이전 1 다음 반응형
