프로그래머스 LV2 "피보나치 수"

프로그래머스 LV2 피보나치 수

기초부터 다시 공부를 하기위해 프로그래머스 라는 사이트에서 코딩테스트를 LV0 부터 가능한곳까지 못하는곳은 레퍼런스를 찾아가며 풀어보려고 합니다.

매일 1개의 풀이를 하고 그 풀이에대한 나의 생각 및 해석을 적어보려합니다.

오늘은 LV2 문제 ‘피보나치 수’ 문제입니다.

위 이미지가 프로그래머스 코딩문제입니다.

문제는 매개변수로 n이 주어집니다. 해당 피보나치 수열을 1234567으로 나눈 나머지를 출력하는 문제입니다.

그럼 오늘의 문제를 한번 풀어보겠습니다.

기본 세팅 코드도 알아보겠습니다.

function solution(n) {
  var answer = 0;
  return answer;
}

기본 세팅 코드는 매개변수 n이 입력되고 함수 안에는 answer이라는 변수가 선언되어 리턴하는 간단한 기본 세팅 코드입니다.

문제를 풀기전에 오늘의 문제이름인 피보나치 수열에 대해서 한번 알아보고 문제를 이어서 풀어보겠습니다.

피보나치 수열

피보나치 수열(Fibonacci sequence)은 각 숫자가 앞의 두 숫자의 합으로 이루어진 수열을 말합니다. 예를 들어, 수열의 첫 번째와 두 번째 숫자는 각각 0과 1로 시작합니다. 그 다음부터는 이전 두 숫자의 합이 됩니다. 따라서 피보나치

수열은 다음과 같습니다: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, …

피보나치 수열을 구하는 방법은 여러 가지가 있습니다:

1. 재귀적 방법: 가장 직관적인 방법으로, 함수가 자기 자신을 호출하여 값을 계산합니다. 예를 들어, n번째 피보나치 수를 구하려면 n-1번째와 n-2번째 피보나치 수를 더하는 방식입니다. 하지만 이 방법은 중복 계산이 많아 비효율적입니다.

2. 메모이제이션을 사용한 재귀적 방법: 재귀적 방법의 비효율성을 개선하기 위해 이미 계산된 값을 저장해두고 필요할 때 다시 사용하는 방법입니다. 이를 통해 중복 계산을 피할 수 있습니다.

3. 반복적 방법: 반복문을 사용하여 피보나치 수를 계산하는 방법입니다. 이 방법은 변수 두 개를 사용하여 이전 두 값을 기억하고, 이를 이용해 다음 값을 계산합니다. 반복적 방법은 재귀적 방법보다 훨씬 효율적입니다.

4. 동적 계획법(Dynamic Programming): 이 방법은 배열을 사용하여 이전에 계산된 값을 저장하고, 이를 바탕으로 다음 값을 계산하는 방식입니다.

이렇게 피보나치 수열에 대해서 알아보았습니다.

그럼 위 에서 말한대로 문제를 만들어보겠습니다.

function solution(n) {
  var answer = 0;
  const calc = 1234567;
  let a = 0, b = 1, result;
  for (let i = 2; i <= n; i++) {
    result = (a + b) % calc;
    a = b;
    b = result;
    answer = result;
  }
  return answer;
}

위 코드의 간단한 설명을 알려드리겠습니다.

1. 초기화:
   • a와 b를 각각 0과 1로 초기화합니다. 이는 F(0)과 F(1)을 의미합니다.
   • 상수 calc를 1234567로 설정하여 모든 계산이 이 값을 기준으로 모듈로 연산되도록 합니다.
2. 반복문:
   • 2부터 n까지 반복하면서 피보나치 수를 계산합니다.
   • 각 단계에서 a와 b를 업데이트합니다. result를 사용하여 (a + b) % calc를 계산하고, a는 b로, b는 result로 업데이트합니다.
3. 결과 반환:
   • 반복이 끝난 후, b는 n번째 피보나치 수를 나타내며, 이를 반환합니다.

그럼 코드를 프로그래머스에 한번 확인해보겠습니다.

성공이네요!

오늘은 프로그래머스 LV2 ‘피보나치 수’ 문제의 대해서 알아봤습니다.

제 방법이 꼭 정답은 아니니 그저 이런방법도 있구나하고 참고용으로만 봐주시면 감사하겠습니다.

감사합니다.