피보나치 수열

 

프로그래머스 멀리 뛰기 파이썬 

https://school.programmers.co.kr/learn/courses/30/lessons/12914?language=python3

프로그래머스

 

 

이 문제는 피보나치 수열을 이용하여 풀 수 있습니다. 효진이가 멀리 뛰기에서 한 번에 1칸 또는 2칸을 뛸 수 있다는 점은 피보나치 수열의 성질과 유사합니다. 예를 들어, 4칸을 뛰는 방법의 수를 구하는 것은 3칸을 뛰는 방법의 수와 2칸을 뛰는 방법의 수를 합한 것과 같습니다. 이는 피보나치 수열에서 각 항이 이전 두 항의 합으로 구성되는 것과 같은 원리입니다.

따라서, 이 문제를 해결하기 위한 파이썬 함수 solution을 다음과 같이 작성할 수 있습니다:

1. n이 1이하인 경우, 방법의 수는 n과 같습니다 (1칸 또는 0칸).
2. n이 2 이상인 경우, 초기 두 항을 1, 2로 설정하고, n-1번 반복하면서 피보나치 수열을 계산합니다.
3. 각 단계에서 계산된 값을 1234567로 나눈 나머지를 저장하여 오버플로우를 방지합니다.

코드는 다음과 같습니다:

def solution(n):
    if n <= 1:
        return n
    a, b = 1, 2
    for i in range(2, n):
        a, b = b, (a + b) % 1234567
    return b

# 예제 입력
print(solution(4))  # 출력: 5
print(solution(3))  # 출력: 3

이 함수는 주어진 n에 대해 멀리 뛰기를 할 수 있는 방법의 수를 1234567로 나눈 나머지를 반환합니다.

 

피보나치 수열은 수학에서 매우 유명한 숫자의 나열입니다. 이 수열은 각 숫자가 바로 앞의 두 숫자의 합으로 이루어진다는 특징을 가지고 있습니다. 피보나치 수열의 처음 두 숫자는 일반적으로 0과 1로 시작합니다. 이후의 각 숫자는 바로 앞의 두 숫자를 더해 구합니다.

피보나치 수열의 일반적인 정의는 다음과 같습니다:

• F(0) = 0, F(1) = 1
• F(n) = F(n-1) + F(n-2) for n > 1

여기서 F(n)은 n번째 피보나치 수를 나타냅니다.

예를 들어, 처음 몇 개의 피보나치 수를 나열해 보면 다음과 같습니다:

• F(0) = 0
• F(1) = 1
• F(2) = F(1) + F(0) = 1 + 0 = 1
• F(3) = F(2) + F(1) = 1 + 1 = 2
• F(4) = F(3) + F(2) = 2 + 1 = 3
• F(5) = F(4) + F(3) = 3 + 2 = 5
• … 이런 식으로 계속 이어집니다.

따라서 피보나치 수열은 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, … 와 같은 모습을 보입니다.

피보나치 수열은 자연계, 예술, 컴퓨터 과학, 경제학 등 다양한 분야에서 나타나며, 복잡한 문제를 단순화하거나 예측하는 데 사용됩니다. 예를 들어, 컴퓨터 과학에서는 피보나치 수열을 이용해 다양한 알고리즘과 데이터 구조를 설계하는 데 활용됩니다.

 

피보나치 수열을 생성하는 간단한 파이썬 예제를 제공해 드리겠습니다. 이 예제에서는 반복문을 사용하여 특정 개수의 피보나치 수를 생성합니다. 예를 들어, 처음 10개의 피보나치 수를 생성하는 함수를 작성해보겠습니다.

def fibonacci(n):
    # 첫 두 숫자를 정의합니다.
    a, b = 0, 1
    for _ in range(n):
        # 현재 숫자를 출력합니다.
        print(a, end=' ')
        # 다음 숫자를 계산합니다.
        a, b = b, a + b

# 처음 10개의 피보나치 수를 출력합니다.
fibonacci(10)

이 코드를 실행하면, 처음 10개의 피보나치 수가 출력됩니다:

0 1 1 2 3 5 8 13 21 34

이 함수는 지정된 개수(n)만큼의 피보나치 수를 생성합니다. a와 b는 각각 현재의 피보나치 수와 다음 피보나치 수를 나타냅니다. 각 반복에서 a는 현재 피보나치 수를, b는 다음 피보나치 수를 저장하고, a와 b는 각각 다음 두 피보나치 수로 업데이트됩니다.