프로그래머스 - 피보나치 수 (레벨2, swift)

 

문제출처 👇

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) = 2 + 3 = 5

와 같이 이어집니다.

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

 

제한사항

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

 

입출력 예

n	return
3	2
5	5

 

입출력 예 설명

피보나치수는 0번째부터 0, 1, 1, 2, 3, 5, ... 와 같이 이어집니다.

 

 

문제풀이

-> 피보나치 수열은 유명한 알고리즘 문제라 구글에 검색해 보면 여러가지 풀이법을 찾아볼 수 있다.

이 문제는 한 가지 조건이 더 추가되어 있는데 1234567을 나눈 나머지를 return하는 값을 구하면 된다.

나는 중복된 계산을 하지 않고 앞에서 계산된 값을 저장하여 참조할 수 있도록 효율성이 높은 동적 프로그래밍을 사용하여 풀었다.

 

동적 프로그래밍에 대해서 간단히 살펴보면

1) 문제를 작은 단위로 쪼갠다.

2) 작은 문제를 해결하고 값을 저장한다.

3) 저장된 값을 사용하여 조금씩 큰 문제를 해결한다.

 

위 방법을 바탕으로 피보나치 수열에 대한 문제를 해결할 경우 아래와 같이 하면 될 것이다.

1) fibonacci 수열의 계산법에 따라 하나씩 계산한다.

2) 계산한 값들을 배열에 저장한다

3) 앞에 이미 저장된 값들을 참조하여 다음 피보나치 수를 계산한다.

 

아래는 전체 코드이다.