자바 피보나치 수열 코드 재귀/메모이제이션 기법

05 March 2020 - 2 mins read time
Tags: 자바 손코딩

피보나치 수열

피보나치 수열은 자기 이전의 숫자와 그 이전의 숫자의 합으로 연결된 수의 순서이다. 0, 1, 1, 2, 3, 5, 8, 13, 21, 34 …. 이런식으로 진행이 되며 수식으로 표현하면 fibo[n] = fibo[n-1] + fibo[n-2] 로 표현이 가능하다.

피보나치 수열 코드 버전 1 - 재귀

재귀를 활용한다면 코드를 짧고 간결하게 피보나치 수열 로직을 구현할 수 있다.

int n = 10
fibo(n)

int fibo(int n) {
  if(n == 0 || n == 1){ 
    return 1
  } else {
    return fibo(n-1) + fibo(n-2)
  }
}

재귀로 피보나치 수열의 값을 구하는 방법은 쉽지만 단점이 존재한다. 수가 커졌을 경우 스택의 복귀 주소가 계속해서 쌓이다가 스택 오버플로우가 발생하여 코드가 멈추게 된다. 즉, 일정 숫자 이상의 크기는 재귀를 활용하는 것은 좋지 않은 방법이다.

피보나치 수열 코드 버전 2 - 메모이제이션

메모이제이션 기법을 활용하여 피보나치 수열의 코드를 구현해 보자.

int n = 10
int [] fibo = new int[n + 1]
fibo[0] = 1 ; fibo[1] = 1

for(int i=2 ; i<=10 ; i++) {
  fibo[i] = fibo[i-1] + fibo[i-2]
}

배열을 활용하여 이전의 피보나치 수열의 값을 저장함. fibo[2] = fibo[1] + fibo[0] 처럼 계속해서 저장된 값을 활용할 수 있다. 숫자가 늘어나도 배열의 사이즈를 크게 또는 타입형만 바꿔주면 되므로 스택 오버플로우의 문제를 걱정할 필요가 없다.

int n = 10
int [] fibo = new int[n + 1]
fibo[0] = 1 ; fibo[1] = 1

fibo(fibo[i]) {
  for(int i=2 ; i<=10 ; i++) {
    if(fibo[i] != 0) continue

    fibo[i] = fibo[i-1] + fibo[i-2]
  }
}

위의 코드의 일부를 함수로 작성하여 호출한다면 효율적인 활용이 가능하다. 이전의 연산이 존재하는 값은 연산이 더 이상 필요없다. 즉, fibo[100]을 한번 구하면 1~99까지는 연산이 더 필요하지 않다. 101이라면 1~100까지 연산을 진행하지 않고 101번째만 연산하면 된다.