프로그래밍_파이썬_백준_10870번_피보나치수열

 

N = [0,1] #피보나치 수열의 첫번째 항(0) 과 두번째 항(1)
N1=0 
N2=0
num = int(input()) # N번째 인덱스 값
sum=0 # N번째 피보나치 수
for i in range(2,num+1): # 첫번째항(0)과 두번째 항()1이 주어졌으므로 2부터 반복문 시행
    N1=N[i-1] # IF 첫번째는 N[2-1] -> N[1]
    N2=N[i-2] # IF 첫번째는 N[2-2] -> N[0]
    k = N1+N2 # IF 첫번째는 k == N[1]+N[0] 즉 여기서 k는 N[2]
    N.append(k) # k의 값을 N의 리스트 마지막 부분에 추가해준다

print(N[num])

#알고리즘, #백준, #백준온라인, #파이썬, #C언어, #C, #자바, #JAVA, #Python, #python, #프로그래밍, #1712번, #PYTHON, #파이썬독학, #파이썬공부, #파이썬연습, #파이썬반복문, #코딩, #코딩독학, #파이썬for, #파이썬while, #코딩반복문, #파이썬기초, #파이썬초보, #파이썬기본, #파이썬수학, #파이썬알고리즘, #수학알고리즘, #피보나치수열, #피보나치

​

안녕하세요. 오늘은 백준 온라인 10870번 피보나치 수열에 대해서 풀어봅시다!

​

문제는

n번째 피보나치 수를 출력하라!

문제는 이렇게 됩니다.

사용자에게 숫자를 입력받아 그 해당하는 숫자의 피보나치 수를 출력을 하는 것입니다.

​

​

우선 피보나치 수가 무엇인지 알아야 겠죠?

​

어떤 남자가 벽으로 둘러싸인 장소에 한 쌍의 토끼들을 둔다. 만약 각 쌍이 두 번째 달부터 매달 토끼를 한 쌍씩 낳는다고 가정한다면 그 해에 얼마나 많은 쌍의 토끼가 생산되겠는가?

이 결과로서 생기는 수열은 다음과 같다.

1, 1, 2, 3, 5, 8, 13, 21, ···

이 수열은 그 결실이 많다고 판명되었고, 수학과 과학의 많은 분야에서 적용되고 있다. 이 수열을 ‘피보나치 수열’이라 하고, 이 수열에서 나타나는 수들을 ‘피보나치 수’라고 한다.

​

피보나치 수열을 생성하는 기본 규칙은 처음 두 항은 1이고, 세 번째 항부터는 바로 앞의 두 항의 합이 된다는 것이다. 그래서 세 번째 항은 첫 번째 항 1과 두 번째 항 1을 더한 값인 2가 된다. 그리고 네 번째 항은 두 번째 항 1과 세 번째 항 2를 더한 값인 3이 된다.

[네이버 지식백과] 피보나치 수열 [Fibonacci Sequence] (컴퓨터 개론, 2013. 3. 10., 김종훈, 김종진)

[출처 : https://terms.naver.com/entry.naver?docId=2270442&cid=51173&categoryId=51173]

 

피보나치 수열

이탈리아 수학자 피보나치(Fibonacci)가 발견한 피보나치 수열은 토끼 번식 이야기에서 출발한다. 어떤 남자가 벽으로 둘러싸인 장소에 한 쌍의 토끼들을 둔다. 만약 각 쌍이 두 번째 달부터 매달 토끼를 한 쌍씩 낳는다고 가정한다면 그 해에 얼마나 많은 쌍의 토끼가 생산되겠는가? 이 결과로서 생기는 수열은 다음과 같다. 1, 1, 2, 3, 5, 8, 13, 21, ··· 이 수열은 그 결실이 많다고 판명되었고, 수학과 과학의 많은 분야에서 적용되고 있다. 이 수열을 ‘피보나치 수열’이라 하고, 이 수열에서 나타나는 수들을 ‘피보...

terms.naver.com

​

위에 내용을 참고하여 간략하게 정리해드리면

​

3번째항은 1번째 항과 2번째항을 더한 것입니다.

4번째항은? -> 3번째항과 2번째항을 더한 것입니다.

​

​

이를 활용해 우리는 피보나치 수열을 구한다음, 해당 인덱스 값에 맞는 수를 출력을 해주면 됩니다

​

우선 저는 백준 온라인에 나온 예시대로 첫번째 항이 0, 그리고 두번째 항이 1을 기준으로 해서 구하였습니다.

​

 

N = [0,1] #피보나치 수열의 첫번째 항(0) 과 두번째 항(1)
N1=0 
N2=0
num = int(input()) # N번째 인덱스 값
sum=0 # N번째 피보나치 수
for i in range(2,num+1): # 첫번째항(0)과 두번째 항()1이 주어졌으므로 2부터 반복문 시행
    N1=N[i-1] # IF 첫번째는 N[2-1] -> N[1]
    N2=N[i-2] # IF 첫번째는 N[2-2] -> N[0]
    k = N1+N2 # IF 첫번째는 k == N[1]+N[0] 즉 여기서 k는 N[2]
    N.append(k) # k의 값을 N의 리스트 마지막 부분에 추가해준다

print(N[num])

​

우선 여기서는 N1과 N2가 주어지지 않았다면 피보나치 수를 구하기 힘들었을겁니다. 그래서 주어진 채로

피보나치 수열을 구하였습니다.(실제로는 N1만으로도 피보나치 수열을 구할 수 있습니다.)

​

for 문 안에 수식들은 대부분 직관적으로 이해하시기 쉬우실 겁니다.

하지만 마지막 N.append(k)는 뭐지? 라는 생각을 하실 겁니다.

​

우선 5번째 항이라고 예시를 듭시다.

그러면 N1 = N[4] , N2=N[3] 가 됩니다

N[4]는 3

N[3]는 2 이므로

​

k = 3+2 => 5가 됩니다.

​

그러면

​

N.append(5) 가 되는데

append 함수는 해당 리스트에 값을 추가해라 입니다!

즉, N.append(5)는 N 리스트에 5를 추가해라 가 되고,

기존에 N은 N= [0,1,1,2,3] 이었을 겁니다. 그리고 5를 추가하면

​

N = [0,1,1,2,3,5 ]가 되고

5번째 인덱스 값은 5가 됩니다 # N[5] = 5

​

​

​

소스 코드에 주석 부분을 잘 보시고 하나하나씩 따라가시면 충분히 이해하실 수 있을 겁니다.

모르는 부분은 댓글로 달아주세요!