[프로그래머스 Lv.2] 피보나치 수 | 개념 및 풀이 (JS)

<목차>

0. [프로그래머스] Lv.2 피보나치 수
1. 해결한 코드
2. 피보나치 수열에 대한 설명

 

 

0. [프로그래머스] Lv.2 피보나치 수

문제 설명

 

요즘은 레벨 1, 2 위주로 프로그래머스 문제를 보고 있는데, 오늘은 프로그래머스 설명만으론 이해하기 어려운 '피보나치 수' 문제를 풀게 되었다. 문제 이해가 안 되니 코드 짜는 것도 도통 감이 안 와서 일단 정답을 봤다.

 

여러 풀이가 있었지만 가장 간단하면서 보기 좋은 코드를 선택해 코드 분석을 하였다. 그 내용은 아래와 같다.

 

 

1. 해결한 코드

function solution(n) {
    let fib = [0, 1];  // 피보나치 수는 0과 1로 시작하므로 첫 두 항을 초기화
    for (let i = 2; i <= n; i++) {  // 피보나치 수열의 3번째 항부터 n번째 항까지 계산
        fib[i] = (fib[i-1] + fib[i-2]) % 1234567; // 이전 두 항의 합을 1234567로 나눈 나머지를 계산해 저장
        // 모듈로 연산을 하는 이유는 수가 매우 커질 수 있는 경우를 대비하여
        // JavaScript에서 숫자 처리 시 발생할 수 있는 정밀도 문제나 오버플로우를 방지하기 위함
    }
    
    return fib[n];  // 계산된 n번째 피보나치 수를 반환
}

 

처음 보는 개념이 늘 바로 이해되면 좋겠지만, 뭐든지 바로 이해가 안 될 때가 더 많다. 피보나치 수열의 개념과 풀이도 나한텐 그렇게 느껴졌다. 이럴 땐 잘 작성된 설명과 풀이를 본 뒤, 조금이라도 이해하고 넘어가는 게 중요하다. 그래야 다음에 유사한 문제가 나왔을 때 내 힘으로 문제를 풀 수 있다.

 

 

2. 피보나치 수열에 대한 설명

피보나치 수열은 수학에서 매우 유명한 수열로, 자연계의 다양한 현상과 관련이 있다고 한다. 이 수열의 개념과 규칙을 알아보니 생각보다 간단하면서도 재밌었다.

 

 

기본 규칙

피보나치 수열은 다음과 같은 간단한 규칙으로 정의된다.

• 첫 번째와 두 번째 수는 0과 1
• 이후의 각 수는 바로 앞 두 수의 합임

즉, 수열은 이렇게 시작한다. 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...

 

 

예시 설명

• 0과 1을 시작으로,
• 세 번째 수는 0+1=1,
• 네 번째 수는 1+1=2,
• 다섯 번째 수는 1+2=3,
• 여섯 번째 수는 2+3=5,

위와 같은 식으로 수가 계속된다.

 

 

수학적 성질

피보나치 수열은 수학적으로 다양한 흥미로운 성질을 가지고 있다.

예를 들어 피보나치 수의 비율은 황금비와 근접해 가며, 비율이 약 1.618로 수렴한다는 것을 의미한다. 황금비는 예술, 건축, 자연 등 많은 분야에서 조화롭고 균형 잡힌 비율로 간주된다.

 

 

자연계와의 관련성

피보나치 수열은 자연계에서도 자주 발견된다고 한다.

 

 

예를 들어 많은 꽃의 꽃잎 수가 피보나치 수이거나, 해바라기 씨의 배열, 소용돌이치는 갤럭시의 팔 등에서 피보나치 패턴을 찾아볼 수 있다.

 

 

프로그래밍에서의 응용

프로그래밍에서 피보나치 수열은 재귀적 알고리즘을 설명하거나 테스트할 때 자주 사용된다. 이 수열은 기본적인 재귀 함수의 예로 활용되며, 더 효율적인 알고리즘(예: 동적 프로그래밍)의 필요성을 보여주는 예시로도 사용된다.

 

 

Reference

• [Math is Fun] Fibonacci Sequence - https://www.mathsisfun.com/numbers/fibonacci-sequence.html
• [Wolfram MathWorld] Fibonacci Number - https://mathworld.wolfram.com/FibonacciNumber.html