[Swift Algorithm] 피보나치 수 Programmers(Lv.2)

문제 설명

피보나치 수는 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

 

내 문제 풀이

func solution(_ n:Int) -> Int {
  var fibo = [0, 1]
  
  for i in 2...n {
    fibo.append((fibo[i-2] + fibo[i-1]) % 1234567)
  }
  
  return fibo[n]
}

• 어차피 n은 2 이상만 입력되고, 0, 1의 경우 피보나치 수를 구할 필요가 없기 때문에 [0, 1] 배열을 생성해준다.
• fibo 배열에 2부터 해당 수의 이전 수, 그 전 수를더한 값을 1234567로 나눈 나머지를 append 해준다. 
• 처음에는 1234567로 나눈 나머지를 추가하지 않고, 나누지 않은 값들을 모두 배열에 담고 나중에 나머지를 구하는 식으로 구현했었는데, 그렇게 하니까 수가 너무 커져서 오류가 발생했다.

 

💡 피드백

• 구현할 때 꼭 담을 수 있는 값의 크기도 생각해주자!
• 피보나치는 필수적이고, 개념을 잘 알아두면 다른 문제에서도 활용이 가능하기 때문에 잘 기억해두자.

 

---

 

🖍 [ 추가 ] 1주일 후 다시 풀어보기

func solution2(_ n:Int) -> Int {
    if n == 0 { return 0 }
    else if n == 1 { return 1 }
    return (solution2(n - 1) + solution2(n - 2)) % 1234567
}

• 얼마 전 공부한 재귀함수로 풀면 간단할 것 같아서 시도해본 코드이다.
• 재귀를 사용하니 코드는 간단하지만, 시간복잡도가 O(2^n)이 되기 때문에 시간 초과로 틀렸다.

 

---

 

문제

https://programmers.co.kr/learn/courses/30/lessons/12945