[Swift] 프로그래머스 연습 문제(Level 2) : 피보나치 수

실제 코딩테스트의 문제를 통하여 알고리즘 분석과 코딩 능력을 향상시킵니다.

 

 

#. 구독 대상

• 기본 알고리즘을 코딩 테스트 문제를 통하여 학습하고 싶으신 분
• 취업 및 이직을 준비하고 계신 개발자
• Swift를 통하여 코딩 테스트 문제를 살펴보고 이해를 하고 싶으신 분
• 코딩 테스트에 대한 거부감을 없애기 위하여 기초부터 하나씩 공부해보고 싶으신 분
• 기타 알고리즘과 문제 해결 능력에 대해서 관심이 있는 모든 개발자분

참고 사항

본 코딩 테스트 문제에 대한 설명 및 해결 방안은 최적의 답이 아닐 수 있습니다.

본 강의에서 지향하는 목표는 바로 특정 문제에 대한 최적의 해결 방법을 찾기보다는 특정한 문제에 대해서 충분히 이해할 수 있고 다양한 방법을 통하여 해결하는 방법을 찾고 향상시키는데 그 목적이 있습니다.

좀 더 좋은 알고리즘 및 코드가 있으시다면 언제든지 본 게시물의 댓글을 통해서 제시해주시면 감사하겠습니다.

 

 

 

---

 

 

 

코딩 테스트 문제

 

먼저 오늘 살펴볼 문제에 대해서 먼저 살펴보겠습니다.

 

https://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은 2 이상 100,000 이하인 자연수입니다.

 

 

 

 

 

---

 

 

 

 

입출력 예

n	return
3	2
5	5

입출력 예 설명

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

 

 

 

 

---

 

 

문제 분석

 

오늘 문제는 피보나치 수열을 활용하여 특정 조건에 맞는 값을 반환하는 문제입니다. 기본 조건은 입력값 n은 2이상 100,000 이하의 자연수이며 n번째 피보나치 수를 1234567로 나눈 값을 반환하면 되면 문제입니다.

 

이전에 작성했던 Swift 재귀호출에서도 피보나치수열에 대해서 잠시 언급한 적도 있습니다. 관련 강좌를 아래와 같으니 참고하시면 감사하겠습니다.

 

https://joycestudios.tistory.com/52

[Algorithm] Recursive(재귀) : 자기 자신을 호출하는 재귀 함수와 재귀 호출 그리고 꼬리 재귀(Tail Recurs

 

 

 

 

---

 

 

 

알고리즘

 

그렇다면 본 문제를 해결하기 위한 알고리즘을 하나씩 살펴보면 아래와 같습니다.

 

 

• 피보나치 수열을 위한 이전 값을 저장하는 변수를 선언한다.(시작은 0이므로 0으로 설정)
• 피보나치 수열을 위한 다으 값을 저장하는 변수를 선언한다.(두번째 값 시작은 1으로 1로 설정)
• 입력된 n의 횟수만큼 반복하여 피보나치 수열을 더한 후 1234567로 나누어준다.
• 다음 피보나치 수로 넘어가기 위하여 이전 값을 다음 값으로 바꾸어준다.
• 1234566로 나누어 생성된 값을 다음 피보나치 수 값으로 설정한다.
• 최종 마지막 피보나치 결과 값을 반환한다.

 

 

 

 

---

 

 

 

코드 설명

 

그렇다면 위의 알고리즘에 대해서 하나씩 살펴보면서 코드로 작성을 해보도록 하겠습니다.

 

 

• 피보나치 수열을 위한 이전 값을 저장하는 변수를 선언한다.(시작은 0이므로 0으로 설정)

// 피보나치 수열을 위한 이전 값을 저장하는 변수를 선언한다.(시작은 0이므로 0으로 설정)
var prev = 0

 

• 피보나치 수열을 위한 다으 값을 저장하는 변수를 선언한다.(두번째 값 시작은 1으로 1로 설정)

// 피보나치 수열을 위한 다으 값을 저장하는 변수를 선언한다.(두번째 값 시작은 1으로 1로 설정)
var next = 1

 

 

• 입력된 n의 횟수만큼 반복하여 피보나치 수열을 더한 후 1234567로 나누어준다.
• 다음 피보나치 수로 넘어가기 위하여 이전 값을 다음 값으로 바꾸어준다.
• 1234566로 나누어 생성된 값을 다음 피보나치 수 값으로 설정한다.

// 입력된 n의 횟수만큼 반복하여 피보나치 수열을 더한 후 1234567로 나누어준다.
for _ in 2...n {
    var div = (prev + next) % 1234567

    // 다음 피보나치 수로 넘어가기 위하여 이전 값을 다음 값으로 바꾸어준다.
    prev = next
    // 1234566로 나누어 생성된 값을 다음 피보나치 수 값으로 설정한다.
    next = div
}

 

 

• 최종 마지막 피보나치 결과 값을 반환한다.

// 최종 마지막 피보나치 결과 값을 반환한다.
return next

 

 

 

 

 

 

위의 코드들을 모두 조합하여 최종 코드를 완성하면 아래와 같습니다.

 

 

최종 코드

func solution(_ n:Int) -> Int {
    // 피보나치 수열을 위한 이전 값을 저장하는 변수를 선언한다.(시작은 0이므로 0으로 설정)
    var prev = 0
    
    // 피보나치 수열을 위한 다으 값을 저장하는 변수를 선언한다.(두번째 값 시작은 1으로 1로 설정)
    var next = 1
 
    // 입력된 n의 횟수만큼 반복하여 피보나치 수열을 더한 후 1234567로 나누어준다.
    for _ in 2...n {
        var div = (prev + next) % 1234567
    
        // 다음 피보나치 수로 넘어가기 위하여 이전 값을 다음 값으로 바꾸어준다.
        prev = next
        // 1234566로 나누어 생성된 값을 다음 피보나치 수 값으로 설정한다.
        next = div
    }
    
    // 최종 마지막 피보나치 결과 값을 반환한다.
    return next
}

 

 

 

 

---

 

 

 

이상으로 오늘 제시한 문제에 대해서 분석 및 코드를 작성해 보았습니다.

 

감사합니다.

 

 

 

 

---

[참고 자료(References)]

 

[1] 프로그래머스 - 피보나치 수 : https://programmers.co.kr/learn/courses/30/lessons/12945

[2] 피보나치 수(위키백과) : https://ko.wikipedia.org/wiki/피보나치_수