Programmers

[프로그래머스] 피보나치 수 / Python

개발하는 사막여우 2021. 1. 21. 09:06
반응형

문제주소 : programmers.co.kr/learn/courses/30/lessons/12945

 

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

피보나치 수는 F(0) = 0, F(1) = 1일 때, 1 이상의 n에 대하여 F(n) = F(n-1) + F(n-2) 가 적용되는 수 입니다. 예를들어 F(2) = F(0) + F(1) = 0 + 1 = 1 F(3) = F(1) + F(2) = 1 + 1 = 2 F(4) = F(2) + F(3) = 1 + 2 = 3 F(5) = F(3) + F(4) =

programmers.co.kr

<문제 설명>

더보기

문제 설명

피보나치 수는 F(0) = 0, F(1) = 1일 때, 1 이상의 n에 대하여 F(n) = F(n-1) + F(n-2) 가 적용되는 수 입니다.

예를들어

  • F(2) = F(0) + F(1) = 0 + 1 = 1
  • F(3) = F(1) + F(2) = 1 + 1 = 2
  • F(4) = F(2) + F(3) = 1 + 2 = 3
  • F(5) = F(3) + F(4) = 2 + 3 = 5

와 같이 이어집니다.

2 이상의 n이 입력되었을 때, n번째 피보나치 수를 1234567으로 나눈 나머지를 리턴하는 함수, solution을 완성해 주세요.

제한 사항

* n은 1이상, 100000이하인 자연수입니다.

입출력 예

n                                                                         return
3 2
5 5

 

<풀이법>

▒ 한줄 개념: 동적 계획법 ▒ 

피보나치 수를 구하는 평범한 문제인데, n의 범위가 조금 큽니다. 1 <= n <= 100000

따라서 재귀로 풀게 되면, 오류가 발생할 가능성이 있으니, 동적계획법을 이용해서 풀면 쉽게 풀립니다.

피보나치 수의 연산방식을 보면 다음과 같이 진행이 되는데, 이때 이미 한번 계산된 피보나치 수를 저장해두는 것이 동적계획법이라고 할 수 있습니다.

피보나치 값 저장 배열 선언 : fibo = [0,1]

f(1)과 f(0)을 이용해 f(2)를 계산할 수 있습니다. 얻어낸 f(2)를 저장합니다 : fibo = [0,1,1] 

f(2)와 f(1)을 이용해 f(3)을 계산할 수 있습니다. 얻어낸 f(3)을 저장합니다 : fibo = [0,1,1,2]

이런식으로 모든 피보나치 수에 대해 저장을 해나가면, 중복적인 계산을 할 필요가 없으므로 효율성을 얻을 수 있습니다.

<코드(Python)>

def solution(phone_book):
    answer = True # 디폴트 True
    phone_book.sort() # 정렬을 통해 연속된 인덱스만 비교
    for i in range(len(phone_book)-1): # 반복문을 통해 비교
        if phone_book[i] in phone_book[i+1]: # 접두어가 되는 번호가 있으면,
            answer = False # False
    return answer

 

 

더 많은 코드 보기(GitHub) : github.com/dwkim-97/CodingTest

 

 

반응형