[Level2] 피보나치 수 답안 및 풀이

◇ 문제 설명

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

 

◇ 초기 내용

※ [출처] 프로그래머스-코딩테스트 연습-문제명

※ 초기 내용을 참고하여 문제에 맞는 코드를 작성하세요.

class Solution {
    public int solution(int n) {
        int answer = 0;
        return answer;
    }
}

 

---

◇ 풀이 과정

아래 코드의 전반적인 문제 풀이과정

1. 피보나치 수를 저장할 ArrayList를 생성한다.
2. n>=2이므로, ArrayList의 인덱스 0, 1번에 각각 초기값 0과 1을 미리 할당해준다.
3. 피보나치 수를 계산하고, ArrayList에 저장할 메서드를 생성한다.
4. 위 메서드에서 재귀호출을 이용하여 피보나치 수를 계산한 후, 그값을 1234567로 나눈 나머지를 ArrayList에 저장한다.(피보나치수의 n번째값이 int형의 최대 크기를 넘을 수 있으므로 1234567을 나눈 나머지를 ArrayList에 저장) 
5. 재귀호출 중, 만약 이전에 ArrayList에 저장한 n번째 피보나치 수가 있을 경우, 재귀호출을 하지 않고 ArrayList에 있는 값을 바로 반환하여 코드의 효율성 향상(재귀호출의 단점 보완)

*피보나치 수 재귀호출 풀이 과정

1. n이 1보다 작으면(1또는 0) n자체를 반환(F(0) = 0, F(1) = 1이다)
2. n이 1보다 크다면 fibo(n-1) + fibo(n-2)를 반환하여 재귀호출 실행
   
   만약, n = 3이면(왼쪽에서 오른쪽 순서)
   

   n = 3 -> fibo(n-1) + fibo(n-2) ->1 + 1 = 2	fibo(n-1) -> (n = 2) -> fibo(n-1) + fibo(n-2) -> 1 + 0 = 1	fibo(n-1) -> (n = 1) = 1
   		fibo(n-2) -> (n = 0) = 0
   	fibo(n-2) -> (n = 1) = 1	-

   위와 같이 재귀호출이 될 것이다.

 

◇ 참고사항

첫번째,  ArrayList

• import java.util.ArrayList로 import 하기
• ArrayList<WrapperClass> arraylist = new ArrayList<WrapperClass>(); 로 ArrayList 생성
• <값 추가하기>
  arraylist.add(값) //ArrayList의 가장 마지막에 값 추가
  arraylist.add(인덱스, 값) //해당 인덱스에 값 추가(단, Array Out of Bounds 에러 주의)
• <값 가져오기>
  arraylist.get(인덱스)
• <ArrayList의 크기>
  arraylist.size()

 

두번째, Wrapper Class

• Java에서 기본 자료형을 객체로 표현한것
• 종류
  

  기본 자료형	WrapperClass
  byte	Byte
  char	Character
  int	Integer
  float	Float
  double	Double
  boolean	Boolean
  long	Long
  short	Short

세번째, 피보나치 수

피보나치 수란, 첫 번째 항의 값이 0이고 두 번째 항의 값이 1일 때, 이후의 항들은 이전의 두 항을 더한 값으로 이루어지는 수열이다.

피보나치 수 - 위키백과, 우리 모두의 백과사전

즉, F(0) = 0, F(1) = 1일때

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

과 같은 규칙으로 만들어진 수열이다.

◇ 답안

 

package Programmers_Level2;
//피보나치 수

import java.util.ArrayList;

class FibonacciSequence {
	//피보나치 수를 담을 arraylist fiboArr 선언
    //ArrayList는 배열과 유사하지만, 크기가 변할 수 있다는 특징이 있음
	static ArrayList<Integer> fiboArr = new ArrayList<>();

	public static void main(String args[]) {
		int n = 1234;
		int rs = solution(n);
		System.out.println(n + "의 결과 : " + rs);
	}

	public static int solution(int n) {
		int answer = 0;
        //n은 2부터 시작하므로 fiboArr에 0과 1의 초기값을 설정
		fiboArr.add(0, 0);
		fiboArr.add(1, 1);
        
        //answer에 fibo(n)의 값 저장
		answer = fibo(n);
		return answer;
	}

	//피보나치 수를 구하는 메서드 fibo
	public static int fibo(int n) {
    	//n이 ArrayList의 사이즈보다 작으면, ArrayList에 n번째 피보나치 수가 저장되어 있다는 뜻
        //재귀 호출을 사용하지 않고 바로 ArrayList에 담겨 있는 값을 가져옴
		if(n<fiboArr.size()) {
			return fiboArr.get(n);
		}
        //n이 ArrayList의 사이즈보다 크면, 아직 ArrayList에 n번째 피보나치 수를 계산하지 않은 것이므로
        //재귀호출을 통해 피보나치 수 계산
        else {
        	//n이 1보다 작으면, n 반환
			if (n <= 1) {
				return n;
			} else {
            	//재귀호출을 이용하여 피보나치 수 구한 후, 
                //int의 크기를 벗어날 수 있으므로(n의 최대값 : 100,000) 
                //1234567로 나눈 값을 ArrayList에 저장
				int result = (fibo(n - 1) + fibo(n - 2)) % 1234567;
				fiboArr.add(n, result);
				return result;
			}
		}
		

	}
}

 

◇ 실행결과

피보나치 수 실행결과

 

◇ 출처

https://programmers.co.kr/learn/challenges

코딩테스트 연습