IT/모바일
저자: 한동훈(traxacun @ unitel.co.kr)
알고리즘 시간에 가장 많이 만나게 되는 문제중에 하나가 피보나치 수열이다. 특히, 재귀 호출을 이용하는 법과 재귀 호출로 작성한 것을 다시 비재귀 호출로 작성하는 법에 대해서 다룰 때 피보나치 수열을 예제로 많이 사용하고 있다. 13세기 이탈리아의 수학자 레오나르도 피보나치가 발견한 이 수열은 다음과 같다.
즉, 앞의 두 항목을 더한 값이 다음 항이 된다.
이 문제는 사실 토끼의 번식에 관한 문제로 피보나치가 27세 때인 1202년에 쓴 "계산판에 관한 책(Liber Abacci)"의 123-124 페이지에 소개된 것이며, 이 문제 하나만이 영원히 유명해지게 되었다.
앞서 소개한 수열을 설명하자면 토끼 한 쌍이 매달 새로 한 쌍의 토끼를 낳고, 새로 태어난 토끼는 두 달이 지나면서부터 또 매달 한 쌍의 토끼를 낳는다고 하자. 1년 후에는 144쌍이 생길 것이다.
사람들이 이 문제에 열광한이유는 자연의 도처에서 피보나치 수열을 발견할 수 있기 때문이다. 해바라기의 가운데에는 씨앗이 촘촘하게 박혀 있다. 그런데 이 씨앗의 배열을 자세히 관찰해 보면 시계 방향과 반시계 방향의 나선을 발견할 수 있다. 해바라기의 나선수는 크기에 따라 다르지만 대개 21개와 34개, 혹은 34개와 55개이다. 왜 이런가에 대해 다양한 설명이 있지만 그중 가장 그럴듯하게 받아들여지는 것은 피보나치 수를 따라 씨를 배열할 때 좁은 공간에 가장 많은 씨를 배열할 수 있다는 설이다.
또 다른 예로는 꽃잎의수를 들 수 있다. 치커리는 21장, 데이지는 34장과 같이 피보나치수가 되는 경우가 대부분이다. 식물의 줄기가 한 회전을 할 때마다 배열되는 잎차례도 피보나치 수열과 관련된다. 식물이 a번 회전하면서 b개의 잎이 나올 때 잎차례는 a/b가 되는데, 대부분의 식물에서 잎차례를 계산해 보면 분모와 분자에 피보나치 수가 들어있다. 이에 대해서도 다양한 설명이 있지만 가장 그럴듯하게 받아들여지는 것은 꽃잎은 꽃이 피기전 봉오리를 이루는 암술과 수술을보호하는 역할을 하는데 가장 효율적인 배치를 하는데 피보나치 수열의 수가 최적이라는 것이며, 나무가 잎을 배열할 때 위의 잎에 가리지 않고 햇빛을 최대한 받을 수 있도록 엇갈리면서 잎을 배치하기 때문이라는 것이다.
솔방울을 대상으로 한 연구에서도 피보나치 수열을 발견할 수 있음이 알려져 있다. 솔방울도 우선형 또는 좌선형의 배열을 가지며 대체로 5와 3의 나선형을 가진 솔방울이 발견된다. 피보나치 수열을 따르지 않는 솔방울은 전체 솔방울의 1-2%에 불과하며 이런솔방울도 10과 6의 나선을 갖는 경우가 대부분이다.
이외에도 달팽이 껍질의 나선 모양, 달팽이관을 비롯한 인체의 많은 기관, 우주의 은하의 모양, 물의 소용돌이, 태풍 등도 모두 피보나치 수열에 따른 나선형 구조를 갖는다.
피보나치 수열에는 이 보다 더 흥미로운 사실들이 많다. 한가지만 예를 들자면 피보나치 수열을 함수 F로 정의할 때 첫번째 항을 나타내는 함수를 F(1), 두번째 항을 나타내는 함수를 F(2)라 하자. 이를 일반적인 점화식으로 나타내면 다음과 같다.
이 피보나치 수열의 F(n)/F(n-1)의 비를 계속해서구해가면 어떤 숫자로 수렴하는 것을 알수가 있는데 이 숫자는 황금비율이라 일컬어지는 0.618033989...로 수렴한다.
즉, 피보나치 수열이 수백년간 큰 관심의 대상이 된 이유는
피보나치 수열의 25번째 항은 75025이고, 100번째 항은 21자리의 큰 수가 된다.
C#에서 double 형식은 32비트 자료형이며 15-16자리수까지의 정확성을 보장하기 때문에 이와 같이 100번째 항을 구하는데 적합하지 않다. 만약, double 형식을 사용하여 100번째 항을 구하면 그 결과는 다음과 같이 된다.
뒤의 0은 실제로 계산되지 않는 부분을 의미한다. 정의에 의해서 피보나치 수열을 구하는 함수를 재귀호출로 작성하면 다음과 같다.
위와 같이 재귀호출로 작성하게 되면 6번째 항인 8을 구하기 위해 그 이전항인 3과 5를 알아야하며, 3을 알기 위해서는 그 이전항인 1과 2를 알아야 한다. 마찬가지로 5를 알기 위해서는 그 이전항인 2와 3을 알아내야 하며, 각각을 구하기 위해 마찬가지로 그 이전항을 알아야 한다. 이처럼 계산 횟수가 급격하게 증가하기 때문에 매우 작은 수에 대해서만 적합하다. 이를 비재귀 버전으로 재작성하면 다음과 같다.
100번째 항과 같이 매우 큰 21자리 수를 출력하고 그 값이 정확히 354224848179261915075 이 되는지 확인하려면 Console.WriteLine( "{0:G25}", result ); 와 같은 코드를 작성하여야 한다. decimal 타입은 28-29자리 까지의 정확성만을 보증하기 때문에 이와 같은 코드로 구할 수 있는 피보나치 수열은 한계가 있다.
Programming Challenges: 알고리즘 트레이닝 북를 보면 41번 문제 "피보나치 수의 개수"를 구하는 문제가 있다.
이 문제는 a와 b 두 수 사시에 있는 피보나치 수가 몇 개인가를 구하는 것인데, 이 문제에서 제시될 수 있는 숫자의 범위는 1부터 10100이다. 10100은 다른 이름으로 구골(googol)이라 한다(구글이라는 이름이 여기서 따온 것인지는 모른다). 따라서, 이 41번 문제는 프로그래머에게 거대한 피보나치 수를 찾는 수학자의 모험에 동참할 것을 요구하면서 기본 자료형에서 제공하지 않는 큰 숫자를 다루는 방법에 대해서 물어보는 것이기도 하다.
레퍼런스
알고리즘 시간에 가장 많이 만나게 되는 문제중에 하나가 피보나치 수열이다. 특히, 재귀 호출을 이용하는 법과 재귀 호출로 작성한 것을 다시 비재귀 호출로 작성하는 법에 대해서 다룰 때 피보나치 수열을 예제로 많이 사용하고 있다. 13세기 이탈리아의 수학자 레오나르도 피보나치가 발견한 이 수열은 다음과 같다.
1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144 ...
즉, 앞의 두 항목을 더한 값이 다음 항이 된다.
이 문제는 사실 토끼의 번식에 관한 문제로 피보나치가 27세 때인 1202년에 쓴 "계산판에 관한 책(Liber Abacci)"의 123-124 페이지에 소개된 것이며, 이 문제 하나만이 영원히 유명해지게 되었다.
앞서 소개한 수열을 설명하자면 토끼 한 쌍이 매달 새로 한 쌍의 토끼를 낳고, 새로 태어난 토끼는 두 달이 지나면서부터 또 매달 한 쌍의 토끼를 낳는다고 하자. 1년 후에는 144쌍이 생길 것이다.
사람들이 이 문제에 열광한이유는 자연의 도처에서 피보나치 수열을 발견할 수 있기 때문이다. 해바라기의 가운데에는 씨앗이 촘촘하게 박혀 있다. 그런데 이 씨앗의 배열을 자세히 관찰해 보면 시계 방향과 반시계 방향의 나선을 발견할 수 있다. 해바라기의 나선수는 크기에 따라 다르지만 대개 21개와 34개, 혹은 34개와 55개이다. 왜 이런가에 대해 다양한 설명이 있지만 그중 가장 그럴듯하게 받아들여지는 것은 피보나치 수를 따라 씨를 배열할 때 좁은 공간에 가장 많은 씨를 배열할 수 있다는 설이다.
또 다른 예로는 꽃잎의수를 들 수 있다. 치커리는 21장, 데이지는 34장과 같이 피보나치수가 되는 경우가 대부분이다. 식물의 줄기가 한 회전을 할 때마다 배열되는 잎차례도 피보나치 수열과 관련된다. 식물이 a번 회전하면서 b개의 잎이 나올 때 잎차례는 a/b가 되는데, 대부분의 식물에서 잎차례를 계산해 보면 분모와 분자에 피보나치 수가 들어있다. 이에 대해서도 다양한 설명이 있지만 가장 그럴듯하게 받아들여지는 것은 꽃잎은 꽃이 피기전 봉오리를 이루는 암술과 수술을보호하는 역할을 하는데 가장 효율적인 배치를 하는데 피보나치 수열의 수가 최적이라는 것이며, 나무가 잎을 배열할 때 위의 잎에 가리지 않고 햇빛을 최대한 받을 수 있도록 엇갈리면서 잎을 배치하기 때문이라는 것이다.
솔방울을 대상으로 한 연구에서도 피보나치 수열을 발견할 수 있음이 알려져 있다. 솔방울도 우선형 또는 좌선형의 배열을 가지며 대체로 5와 3의 나선형을 가진 솔방울이 발견된다. 피보나치 수열을 따르지 않는 솔방울은 전체 솔방울의 1-2%에 불과하며 이런솔방울도 10과 6의 나선을 갖는 경우가 대부분이다.
이외에도 달팽이 껍질의 나선 모양, 달팽이관을 비롯한 인체의 많은 기관, 우주의 은하의 모양, 물의 소용돌이, 태풍 등도 모두 피보나치 수열에 따른 나선형 구조를 갖는다.
피보나치 수열에는 이 보다 더 흥미로운 사실들이 많다. 한가지만 예를 들자면 피보나치 수열을 함수 F로 정의할 때 첫번째 항을 나타내는 함수를 F(1), 두번째 항을 나타내는 함수를 F(2)라 하자. 이를 일반적인 점화식으로 나타내면 다음과 같다.
F(n) = F(n-1) + F(n-2)
이 피보나치 수열의 F(n)/F(n-1)의 비를 계속해서구해가면 어떤 숫자로 수렴하는 것을 알수가 있는데 이 숫자는 황금비율이라 일컬어지는 0.618033989...로 수렴한다.
즉, 피보나치 수열이 수백년간 큰 관심의 대상이 된 이유는
- 자연속에서 피보나치 수들이 반복적으로 나타나기 때문이다.
- 0.618033989..라는 황금비라고 부르는 이 비율이 갖는 중요성 때문이다. 이 비율은 카드 모양에서 부터 미술, 건축에 이르기까지 널리 쓰인다.
- 피보나치 수 자체가 지닌 흥미로운 성질 때문에 수론에서 예기치 못한 다양한 용도로 사용되고 있다.
1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144 ...
피보나치 수열의 25번째 항은 75025이고, 100번째 항은 21자리의 큰 수가 된다.
354224848179261915075
C#에서 double 형식은 32비트 자료형이며 15-16자리수까지의 정확성을 보장하기 때문에 이와 같이 100번째 항을 구하는데 적합하지 않다. 만약, double 형식을 사용하여 100번째 항을 구하면 그 결과는 다음과 같이 된다.
354224848179262000000
뒤의 0은 실제로 계산되지 않는 부분을 의미한다. 정의에 의해서 피보나치 수열을 구하는 함수를 재귀호출로 작성하면 다음과 같다.
위와 같이 재귀호출로 작성하게 되면 6번째 항인 8을 구하기 위해 그 이전항인 3과 5를 알아야하며, 3을 알기 위해서는 그 이전항인 1과 2를 알아야 한다. 마찬가지로 5를 알기 위해서는 그 이전항인 2와 3을 알아내야 하며, 각각을 구하기 위해 마찬가지로 그 이전항을 알아야 한다. 이처럼 계산 횟수가 급격하게 증가하기 때문에 매우 작은 수에 대해서만 적합하다. 이를 비재귀 버전으로 재작성하면 다음과 같다.
100번째 항과 같이 매우 큰 21자리 수를 출력하고 그 값이 정확히 354224848179261915075 이 되는지 확인하려면 Console.WriteLine( "{0:G25}", result ); 와 같은 코드를 작성하여야 한다. decimal 타입은 28-29자리 까지의 정확성만을 보증하기 때문에 이와 같은 코드로 구할 수 있는 피보나치 수열은 한계가 있다.
Programming Challenges: 알고리즘 트레이닝 북를 보면 41번 문제 "피보나치 수의 개수"를 구하는 문제가 있다.
이 문제는 a와 b 두 수 사시에 있는 피보나치 수가 몇 개인가를 구하는 것인데, 이 문제에서 제시될 수 있는 숫자의 범위는 1부터 10100이다. 10100은 다른 이름으로 구골(googol)이라 한다(구글이라는 이름이 여기서 따온 것인지는 모른다). 따라서, 이 41번 문제는 프로그래머에게 거대한 피보나치 수를 찾는 수학자의 모험에 동참할 것을 요구하면서 기본 자료형에서 제공하지 않는 큰 숫자를 다루는 방법에 대해서 물어보는 것이기도 하다.
레퍼런스
- 좋은 프로그램을 만드는 핵심 원리 25가지, 한빛미디어, 102-105p
- Programming Challenges: 알고리즘 트레이닝 북, 한빛미디어, 168p, p172.
- C# BigInteger Class
- Big-Numbers.com
- GMP(GNU Multiple Precision Arithmetic Library)
:C++에서 1000 bit 크기의 숫자를 다루고 싶다면 GMP를 방문하기 바란다.
TAG :
이전 글 : PHP Data Access 3. 캐싱
최신 콘텐츠