[programmers] 프로그래머스 Level2 피보나치 수(파이썬 Python)

(주)그렙

 

[programmers] 프로그래머스 Level2 피보나치 수

(파이썬 Python)

 

* 문제출처 : 프로그래머스 코딩 테스트 연습, 알고리즘 문제

 

 

 

1) 문제

---

프로그래머스 피보나치 수 파이썬

코딩테스트 연습 - 피보나치 수

 

 

 

 

 

2) 풀이 과정

---

 

(1)

F(1)과, F(2) 부터 우선 정의

Why? 문제에서 주어진 제한사항

 

1<=n<=100000

 

f(1) = 1

f(2) = 1 부터 먼저 정의

 

(2)

3이상 부터의 관계 정리

 

n = 3 - > 1회

: F(3) = F(2) + F(1)

 

n = 4 - > 2회

: F(4) = F(3) + F(2)

: F(3) = F(2) + F(1)

 

n = 5 - > 3회

: F(5) = F(4) + F(3)

: F(4) = F(3) + F(2)

: F(3) = F(2) + F(1)

 

*  반복은 (0, n-2)로 지정하면 되겠구나.

 

(3)

F(n) = F(n-1) + F(n-2)

F(n-1) = F(n-2) + F(n-3)

 

변수 n-1 - > n-2로 이동

변수 n - > n-1로 이동

(순서 중요)

 

 

 

 

 

 

 

 

 

< < 사고 과정 > >

---

 

1. 주어진 n을 바탕으로 이전 수의 합을 통해 만들어 나가는 과정

 

2. F(n)과 F(n-1)의 관계를 파악.(3이상의 수가 입력 됬을 경우)

 

3. 만약 7이 들어 왔다 하면, 위에서 아래로 연산을 거쳐야 함.

: 입력된 n을 기준으로 아래와 같은 함수를 연산을 해야 함

 

'''

 

F(n) = F(n-1) + F(n-2)

 

F(7) = F(6) + F(5)

F(6) = F(5) + F(4)

F(5) = F(4) + F(3)

F(4) = F(3) + F(2)

F(3) = 2

 

 

'''

 

보기 쉽게 이미지로 나타내보면

(n에 7이 입력된 경우)

 

 

 

 

 

 

 

 

3) 코드

---

def solution(n):
 
    if (n == 1):
        answer = 1
    elif (n == 2):
        answer = 1
    else:
        nMinus_one = 1
        nMinus_two = 1
        
        for _ in range(0, n-2):
            answer = (nMinus_one + nMinus_two)
            
            nMinus_two = nMinus_one
            nMinus_one = answer
            
    return (answer % 1234567)

 

 

 

 

 

4) 정리 노트

---

X