본 포스트는 여러 피보나치 수열 알고리즘 관련 게시글 중 해당 포스트를 참고하여 Python to Java로 작성해본 포스트입니다.
피보나치 수열이란?
피보나치 수열(Fibonacci Sequence)은 단순한 단조 증가(monotonically increasing) 수열로 0번째 항은 0, 1번째 항은 1, 그 외 항은 전번, 전전번 항의 합으로 표현된다.
바로 위 그림은 피보나치 수열의 첫 10항 정도를 보여주고있다.
흔히 나오는 문제는, 0 이상의 정수 n이 주어질 때 n번재 피보나치 수를 구하는것이다.
n번째 피보나치 수를 구하는 fibo함수는 다음과 같이 정의할 수 있을 것이다.
기본 재귀적 풀이
앞서 만든 fibo함수를 그대로 구현하면 된다.
public class FibonacciTest {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
long findNum = Integer.parseInt(br.readLine());
for(int i = 0; i<=findNum; i++){
System.out.println(i+"번째 피보나치수 : " + fibo(i));
}
br.close();
}
public static long fibo(long input){
if(input<2){
return input;
}else{
return fibo(input-1)+fibo(input-2);
}
}
}
n이 0이나 1일 때는 값도 0, 1이기 때문에 그대로 반환하면 되고, 2 이상일 대만 재귀 함수 두개로 분기해 값을 반환한다.
시간 복잡도는 한수가 한번 호출되면 다시 두번 호출되기 때문에, 지수적으로 증가해 $O(2^{n})$ 이 된다.
반복적 풀이
위의 그림을 다시 보자. 가령 내가 10번째 피보나치 수를 찾고 싶다면 0번째, 첫번째 피보나치 수부터 계속 반복적으로 더해서 앞으로 하나씩 전진하며 최종적으로 10번째에 도달할 수 있다.
따라서, 피보나치 알고리즘을 재귀적으로도 풀 수 있지만, for를 활용한 반복문을 통해서도 해결할 수 있는 여지가 있다.
public class FibonacciTest {
static long a = 0;
static long b = 1;
static long sum = 1;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
long findNum = Integer.parseInt(br.readLine());
for(int i = 0; i<=findNum; i++){
System.out.println(i+"번째 피보나치수 : " + fibo(i));
}
br.close();
}
public static long fibo(long input){
if(input<2){
return input;
}else{
sum = a + b;
a = b;
b = sum;
return b;
}
}
}n이 2 미만일때는 아까와 같이 그대로 반환한다. 그리고 전역변수 sum에 앞의 두 값을 더한 후, 전역변수 a에 b값을, 그 다음 전역변수 b에 sum값을 넣어줘서 한칸씩 전진하여 피보나치수를 구할 수 있도록 한다.
다시말해
0
(0, 1)
0, (1, 1)
0, 1, (1, 2)
0, 1, 1, (2, 3)
0, 1, 1, 2, (3, 5)
0, 1, 1, 2, 3, (5, 8)
0, 1, 1, 2, 3, 5, (8, 13)
0, 1, 1, 2, 3, 5, 8, (13, 21)
0, 1, 1, 2, 3, 5, 8, 13, (21, 34)
0, 1, 1, 2, 3, 5, 8, 13, 21, (34, 55)
0번째부터 10번째까지 이런식으로 연산이 이뤄지고, b 값이 피보나치 수가 되는것이다.
앞의 재귀에 비해 매우 효율적인 방법이며, 시간 복잡도는 $O(n)$ 이 된다.
동적 계획법을 사용한 풀이
피보나치 알고리즘에서 동적 계획법이 쓰이는 이유는, 기본적으로 피보나치 알고리즘이 너무나도 비효율적이기 때문이다.
처음 다룬 재귀적 알고리즘같은 경우, 식은 매우 간단하고 기본 정의에 충실하지만 효율은 매우 좋지 않다.
예를들어, 재귀적 알고리즘을 사용하여 100번째 피보나치 수를 구해본다고 했을때, 시간복잡도는 까마득할것이다..
위 사진은 7번째 피보나치 수를 구할 때의 값을 구하는 과정을 표현하고 있다.
7번째 값을 구하기 위해서는 5, 6번째 값을 구해야 한다. 그 둘을 더해야 하기 때문이다.
알고리즘에서는 이와 같이 원 문제를 해결하기 위해 원 문제보다 작은 5, 6번째 같은 값을 구하는 것을 '부분문제(subproblem)를 푼다'고 한다. 이 부분문제를 풀기 위해 함수의 재귀 호출을 사용했다.
문제는 이 부분문제들이 fib(0), fib(1)를 만나기 전까지 계속 쪼개지며 굉장히 많이 등장한다는 것이다.
정확이는, 부분문제의 수가 아닌 부분문제가 중복(overlapping subproblems)된다는 것이다.
그림에서 7번째 피보나치 수를 구하기 위해 fib(3)이 얼마나 많이 등장하는가? 정확히 5번 등장한다.
이는 n이 커질수록 기하급수적으로 커지는데, 이 이유때문에 재귀적 알고리즘을 사용하여 100번째 피보나치 수를 구해야 할 때 프로세스가 멈추는것이다.
재귀적 풀이의 시간 복잡도는 $O(2^{n})$ 이므로, n이 100이라면 $O(2^{100})$... 따라서 엄청나게 큰 수이다.
가장 큰 문제는 부분문제가 너무 많이 중복되는것이다. 그렇다면, 각 부분문제를 해결할때마다 그것을 저장하고 필요할때마다 가져다 쓰면 중복 문제를 해결할 수 있지 않을까?
예를들어, 위의 7번째 피보나치 수를 구하기 위해서 3번째 피보나치 수 부분문제를 5번 해결한다고 했는데, 애초에 처음 해결했을 때, 그부분을 따로 저장해둔다면 그 값이 또 필요할 때 반복 계산할 필요가 없어진다.
따라서 동적 계획법이 굉장히 좋은 결과를 만들어낼 수 있다는것이다.
동적 계획법 풀이에서는 부분문제들을 해결할 때마다 값을 저장하는 캐시를 만든다. 이런 동적 계획법 문제를 풀 때 해결할 수 있는 방법이 크게 반복문을 사용하는 반복적 풀이(iterative)와 재귀적 풀이(recursive)가 있다.
반복적 동적 계획법 풀이
부분문제의 답을 계산할 캐시의 형태나 타입은 문제의 특성에 따라 다양하게 설정할 수 있는데, 이렇게 쉬운 문제에서는 n번째 피보나치 수를 n인덱스에 저장하는 1차원 배열이면 충분해보인다.
public class FibonacciIteration {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
long inputNum = Integer.parseInt(br.readLine());
long result = iterationFibo(inputNum);
System.out.println(result);
br.close();
}
static long iterationFibo(long input){
if(input<2){
return input;
}
long[] cache = new long[(int) input+1];
cache[0]=0;
cache[1]=1;
for(int i = 2; i<=(int)input; i++){
cache[i] = cache[i-1] + cache[i-2];
}
return cache[(int) input];
}
}
위와 달리 순식간에 답이 나온다. cache의 크기를 n이 아닌, n+1 로 한 것은 크기를 n으로 하면 캐시의 마지막 인덱스가 n-1이 되기 때문이다.
위 코드는 iterationFibo라는 이름의 함수로 기능을 모듈화하였다.
재사용성이 향상되었고, 전역 공간을 낭비하지 않는다. 그리고 캐시가 함수가 끝날때마다 삭제된다.
그리고 n이 2보다 작을 때는 그 값을 바로 반환하도록 하였는데, 0번째와 1번째 수는 인덱스 값과 일치하기때문에 쓸데없는 연산을 하지 않고 바로 반환시키는것이다.
부분문제의 값을 저장하고 그 부분문제를 해결해 나가며 최종적으로 답을 구한다. 사실 위 풀이는 기본적인 반복적 풀이와 원리가 같다.
둘을 굳이 분류한 이유는 아까처럼 두 변수를 반복할 수 있는 것은 피보나치 알고리즘의 특수한 특성일 뿐이며 지금처럼 푸는 것이 동적 계획법의 정석이기 때문이다.
재귀적 동적 계획법 풀이
반복적 동적 계획법 풀이도 훌륭하지만, 재귀 함수를 사용하는 동적 계획법 풀이도 존재한다.
앞서 기본 재귀적 풀이의 비효율성을 언급하면서 '동적 계획법을 도입해 첫 부분문제를 해결하고 다시 필요할 때마다 가져다 쓰자'라고 하였는데 이 방법이 조금 더 괜찮다.
이 방법은 재귀적 풀이와 비슷하다. 차이가 있다면 캐시를 만들고, 그 캐시에서 부분문제의 답을 찾고 없으면 직접 계산한다는 정도이다.
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
long inputInt = Integer.parseInt(br.readLine());
long result = recursionFibo((int) inputInt);
System.out.println(result);
br.close();
}
static long recursionFibo(int input){
if(input<2){ //기저사례 #1.
return input;
}else{
long[] cache = new long[input+1];
Arrays.fill(cache, -1);
cache[0] = 0;
cache[1] = 1;
if(cache[input] != -1){ //기저사례 #2.
return cache[input];
}else{ //기저사례 충족 못할 시 값을 실제로 구함
cache[input] = recursionFibo(input-1) + recursionFibo(input-2);
return cache[input];
}
}
}함수를 재귀적으로 풀 때 언제나 염두에 두어야 할 것은 함수가 더 이상 재귀 호출하지 않고 끝날 조건을 설정해줘야 하는 것이다. 그렇지 않으면 함수 스택이 넘치게 된다. 재귀 함수가 끝나도록 하는 조건을 기저사례( base case ) 라고 한다.
피보나치 알고리즘에서 기저사례는 n이 2 미만일 때다.(n은 0 이상의 정수로 이미 한정했다) 그리고 우리의 알고리즘에서는 기저사례가 하나 더 추가되는데, 그것은 원하는 부분문제를 이미 해결했을 때이다.
5번째 피보나치 수를 구하는 부분문제를 해결했다면, 다시 그 수가 필요할 때 그대로 가져다 쓰면 된다. 위 함수에서는 기저사례 #2. 에 해당한다.
위 코드에서 cache의 모든 인덱스를 '-1'로 초기화했다. 꼭 '-1'일 필요는 없는데, 모든 피보나치 수는 0 이상의 정수이기 때문에 캐시 값이 '-1'이라는 것은 n번째 피보나치 수를 아직 계산하지 않았다는 것이 된다.
따라서 캐시의 n번째 인덱스의 값이 '-1'이 아니면 n번째 피보나치 수를 구하는 부분문제를 이미 해결했다는 뜻이기에 그대로 값을 반환한다.
두 기저사례를 하나라도 만족하지 못하면 재귀함수를 호출해 값을 구한다. 이때, 새로 구한 n번째 값을 캐시에 저장함으로써 향후 이 값이 필요할 때 다시 사용한다.
많은 동적 계획법 문제의 경우, 위의 재귀적, 반복적 동적 계획법을 모두 사용할 수 있다. 무엇을 쓸지는 취향의 문제이다.
다만 재귀적인 방법은 함수를 계속 호출하는 데 따르는 오버헤드가 발생하기 때문에 절대적으로는 반복적 동적 계획법 풀이에 비해 시간이 오래 걸린다. 그렇지만 둘 다 시간 복잡도는 $O(n)$으로 효율에 있어 극적인 차이가 발생할 정도로 비효율적이지는 않으니(BigO 표기법에서 상수를 무시하는 것과 같은 이치다) 너무 걱정하지 않아도 된다.
행렬 곱셈을 활용한 풀이
행렬의 곱셈을 활용한 알고리즘이다.
이 절에서는 n번째 피보나치 수를 $Fn$이라고 하자
이때, 피보나치 수들을 행렬화할 수 있는데, 이런 정리를 이끌어낼 수 있다.
$\begin{pmatrix} F_{n+1} & F_{n} \\ F_{n} & F_{n-1} \end{pmatrix} = \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}^n$
이 식을 통하면 오른쪽 행렬을 n번 제곱하면 나오는 행렬의 [0,1] 또는 [1,0]값이 $Fn$이 된다.
즉 우리는 행렬 곱셈을 통해 피보나치 수를 구하게 되는 것이다.
그렇다면 먼저 제곱수를 구해야하는데 이에 관해 생각해봐야한다.
가령 계산을 통해 $2^64$를 구해야 한다면 어떻게 구하는 것이 최선일까? 보통은 '2를 64번 곱한다'라고 대답하지만 이보다 더 좋은 방법이 있다. 이는 $2^1$을 제곱하고 그 결과물인 $2^2$를 제곱, 또 그 결과를 제곱,... 해서 $2^64$까지 만드는 것이다.
2의 1제곱부터 계산하면 총 6번의 계산이 나오는데 이는 $log_264$와 일치한다. 즉 이 방법을 통하면 2의 n제곱을 구하는데 $O(log_2n)$의 시간으로 끝낼 수 있을 것이고 위의 행렬식도 같은 방법으로 제곱해 나가면 이전의 방법들의 $O(n)$을 획기적으로 개선할 수 있다.
이런 질문을 할 수 있다. 'n이 2의 제곱수가 아닐 경우 어떻게 해야하는가?' 예를 들어 $2^100$을 2의 제곱수를 사용하여 어떻게 구해야할까? 당연한 말이지만 모든 자연수는 2의 제곱수의 합으로 표현할 수 있다. 100은 4, 32, 64의 합이고 그렇다면 $2^4$, $2^32$, $2^64$를 구해 이 셋을 곱하면 $2^100$을 만들 수 있다. 복잡도는 여전히 $log_2n$이다.
이 방법을 통해 주어진 행렬의 n제곱을 만들어내서 결과 행렬의 [1,0]을 반환하는 함수를 만들면 된다.
최종적으로 우리는 코드상 두가지 기능을 만들어야한다.
1. 두 행렬을 곱하는 기능 : 위 정리에서는 2 X 2 크기의 정방 행렬을 사용하는데 두 개의 행렬을 곱하는 기능을 만든다.
2. 실제로 곱하는 기능 : 주어진 n에 대해 기본 행렬을 n번 곱한 행렬을 완성하는 기능을 만든다.
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
long inputInt = Integer.parseInt(br.readLine())-1;
long result = matrixFibo((int) inputInt);
System.out.println(result);
br.close();
}
static long matrixFibo(int input) {
int k = 0;
long[][] ZERO = {{1, 0}, {0, 1}};
long[][] BASE = {{1, 1}, {1, 0}}; //곱셈을 시작해 나갈 기본 행렬
long[][] result = ansMatrix;
if(input<2){
return input+1;
}else{
while(k<input){
result = matrixMultiply(result, ansMatrix);
k++;
}
return result[0][1];
}
}
static long[][] matrixMultiply(long[][] matrix1, long[][] matrix2){
int m1 = matrix1.length;
int n1 = matrix1[0].length;
int m2 = matrix2.length;
int n2 = matrix2[0].length;
long[][] temp = new long[m1][n2];
for(int i=0; i<m1; i++){
for(int j=0; j<n2; j++){
for(int k=0; k<n1; k++){
temp[i][j] += matrix1[i][k]*matrix2[k][j];
}
}
}
return temp;
}행렬의 곱셈을 이용해 피보나치 알고리즘을 구현했다. 각 부분에 대한 설명은 아래와 같다.
1. 변수 선언
- n에 0이 들어올 경우를 위한 ZERO항등원을 만든다. 위 값은 실제로 행렬의 항등원으로 n이 0일 때는 [1, 0] 인덱스 값이 0이 된다. BASE행렬은 우리가 곱해 나갈 기본 행렬이 된다. 앞선 정리의 오른쪽이 되는 행렬이다. 이를 n번 곱하는 것이 우리의 목적이고 2의 제곱을 활용하여 구한다. 이때 이들은 수정을 가하지 않을 상수 취급하기 위하여 변수명을 대문자화했다.
2. 두 행렬을 곱하는 함수 matrixMultiply 구현
- 인자로 받은 두 행렬을 곱하는 함수를 만든다. 이 알고리즘은 너비, 길이가 같은 정방형 행렬(square matrix)만 취급하기 때문에 코드가 단순하다. 대신 이름에 이를 꼭 명시해주어야 한다.
3. 실제로 BASE행렬의 n승을 구하는 함수를 구현
- 행렬 피보나치 알고리즘에서는 이 함수만 이해하면 된다. 먼저 최종 결과물인 matrix행렬을 만든다. n이 0일 경우를 대비해 ZERO가 되어야 한다. k는 2의 k승을 계산할 때 쓰인다. 0부터 시작해서 값을 키워나가며 n이 $2^k$를 포함하는지(가령, 100이 16, 32, 64 등을 포함하는지)를 확인할 것이다. tmp는 k가 커짐에 따라 BASE를 $2^k$번 곱한 값을 저장해 나간다. n을 구성하는 $2^k$마다에서 matrix 변수에 자신을 곱해나가며 matrix를 키울 것이다.
- while문을 통해 주어진 n이 1, 2, 4, 8,... 등을 포함하는지 계산한다. 무한루프에 빠지지 않게 조건을 주어야 하는데 $2^k$가 n이하일 때까지만 계산한다. 100은 $2^6$보다는 크기 때문에 이를 포함할 수 있지만 자신보다 큰 제곱수는($2^7$ 이상) 상식적으로 포함할 수 없다.
- 0 이상의 정수 k에 대해 자연수 n이 $2^k$를 포함하는지 어떻게 확인할까? 비트 연산이 적절해 보인다. 100은 이진수로 $1100100_{(2)}$이고, 이때 1이 되는 자리수들이 100을 구성하는 4, 32, 64가 된다. 100에 k를 0에서 1씩 키워 나가 AND연산을 하면 100이 $2^k$를 포함할 때는 1, 아닐 때는 0을 반환할 것이다.
- 이 원리를 바탕으로 matrix를 곱해 나간다. n을 2진수로 변환했을 때 k번째 자리수가 1로 채워져 있다면('n&(1<<k)!=0')matrix에 tmp를 곱하고, 아니면 이번 k에서는 건너뛴다. 이번 k일때 n이 $2^k$를 포함하는 여부와 상관없이 while문을 벗어나기 전까지는 k는 1씩 증가시키고, tmp는 자신을 곱해 $2^k$번째 행렬을 꾸준히 만든다. 100이 8, 16을 포함하지 않다가 32를 포함한 것과 마찬가지로.
(작성중)
'ETC > 알고리즘 이론' 카테고리의 다른 글
| [알고리즘] 리스트의 모든 조합 구할때 고려할점 (permutations, combinations VS product) (Python) (0) | 2021.08.20 |
|---|---|
| [알고리즘] 경우의 수 (순열, 조합) 구하기 - itertools (Python) (0) | 2021.08.06 |
| [알고리즘] 재귀함수 (Recursive Function) (0) | 2021.08.02 |
| [알고리즘] Towers of Hanoi - 하노이의 탑 알고리즘 (0) | 2020.10.04 |
| Edgher W. Dijkstra - Go To Statement Considered Harmful 을 읽고. (0) | 2020.05.26 |
댓글