반응형 분할정복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. 백준 1992: 쿼드트리 (파이썬) 문제: https://www.acmicpc.net/problem/1992 1992번: 쿼드트리 첫째 줄에는 영상의 크기를 나타내는 숫자 N 이 주어진다. N 은 언제나 2의 제곱수로 주어지며, 1 ≤ N ≤ 64의 범위를 가진다. 두 번째 줄부터는 길이 N의 문자열이 N개 들어온다. 각 문자열은 0 또 www.acmicpc.net 코드 #https://teching.tistory.com/ import sys res = "" def makeConftti(list): global res tmp = 0 for line in list: tmp += sum(line) n = len(list) if tmp == n*n: res += "1" return elif tmp == 0: res += "0" return #가.. 2022. 3. 29. 이전 1 다음 반응형
