해당 포스트에서는 피보나치 수열(Fibonacci numbers)에 대해 소개하고, 실습으로 300보다 작은 모든 피보나치 숫자들을 찾는 방법을 소개합니다.
참고로, Python 코드는 아래 사이트에서 확인하실 수 있습니다.
피보나치 수열(Fibonacci numbers)?
피보나치 수열은 각 항이 바로 앞 두 항의 합과 같은 수열입니다. 즉, 0과 1로 시작하고, 그 다음 항부터는 바로 앞의 두 항을 더한 값으로 이루어진 수열입니다.
예를 들어, 피보나치 수열의 처음 몇 항은 다음과 같습니다.
| 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, ... |
피보나치 수열은 다양한 곳에서 만날 수 있습니다. 예를 들어, 자연계에서는 꽃잎, 나팔꽃의 씨앗 배열 등에서 피보나치 수열의 규칙성이 나타나고, 컴퓨터 과학 분야에서도 피보나치 수열은 많은 응용 분야가 있습니다.
컴퓨터 과학 응용 분야
- 암호학: 피보나치 수열을 이용해 암호화 기술을 개발하는데 사용됩니다. 피보나치 수열의 규칙성을 이용하여 암호화 키를 생성하거나, 암호화 알고리즘에서 키로 사용될 수 있습니다.
- 자료구조: 피보나치 힙(Fibonacci Heap)은 우선순위 큐 자료구조에서 사용되는 힙으로, 피보나치 수열의 규칙성을 이용하여 구현됩니다. 이를 이용하면 우선순위 큐 자료구조를 빠르게 구현할 수 있습니다.
- 동적 계획법: 동적 계획법(Dynamic Programming) 알고리즘에서 피보나치 수열은 매우 중요한 역할을 합니다. 동적 계획법에서는 피보나치 수열과 유사한 형태의 문제가 자주 등장하며, 이를 이용하여 최적화 문제를 해결하는 알고리즘을 구현할 수 있습니다.
- 그래픽 디자인: 그래픽 디자인에서는 피보나치 수열의 규칙성을 이용하여 자연스러운 곡선을 생성하는 데 사용됩니다. 피보나치 수열의 비율이 황금 비율에 근접하기 때문에, 이를 이용하여 자연스러운 비율을 만들어내는 것이 가능합니다.
[실습] 300보다 작은 모든 피보나치 숫자들을 찾아 나열하는 r코드를 찾으시오.
이번 실습에서는 피보나치 수열(Fibonacci numbers) 중 300보다 작은 숫자들을 찾는 방법에 대해 설명합니다. 프로그래밍의 방식은 다양하기에 결과는 동일하지만 접근 방식, 코딩 결과가 다를 수 있습니다. 아래 코드는 반복문에 repeat()를 사용하고, 숫자가 300을 넘으면 break() 되도록 짜여져 있습니다.
R코드
x <- c(0, 1)
repeat {
position <- length(x)
new <- x[position] + x[position - 1]
if (new > 300) break
x <- c(x, new)
} > x
[1] 0 1 1 2 3 5 8 13 21 34 55 89 144 233
코드 설명
먼저, 피보나치 수열을 담는 벡터 x를 생성하여 초기값인 0과 1을 입력해 줍니다. 다음에는 repeat() 반복문을 이용해 무한 반복하며, 현재 위치(position)를 계산하고, 그 위치에서의 새로운 항(new)을 계산합니다. 이 새로운 항이 300을 초과하는 경우, break() 문을 사용하여 루프를 종료합니다.
요약
- 0과 1로 시작하는 피보나치 수열을 생성
- 그 다음 항부터는 바로 앞의 두 항을 더한 값이 300을 초과하지 않을 때까지 계속해서 수열을 추가
- 두 항을 더한 값이 300을 초과하면 반복 중단
따라서, 코드를 실행하면 결과 벡터 x에 다음과 같은 피보나치 수열이 담기게 됩니다.
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584
관련 링크
[1] Problem 2 : 피보나치 수열에서 4백만 이하이면서 짝수인 항의 합
[2] [위키백과] 피보나치 수
[3] [Python] 피보나치 수열 (Fibonacci numbers)(https://didalsgur.tistory.com/entry/Python-%ED%94%BC%EB%B3%B4%EB%82%98%EC%B9%98-%EC%88%98%EC%97%B4-Fibonacci-numbers)