재귀 함수를 공부해보자.
스터디에서 프로그래머스 최대공약수 최소공배수를 구하는 문제를 같이 풀었는데, 다른 사람의 풀이에 유클리드 호제법을 과, 재귀함수를 이용하여 최대공약수를 구하는 풀이가 나와있었다. 재귀함수에 대해서 발표를 해야겠다는 생각이 들어 공부해보기 시작했다.
피보나치 수열을 재귀함수를 이용해 구해보자.
재귀함수를 이용하는 대표적인 문제는 피보나치 수열을 구하는 것이 있었다.
점화식 a (n) = a (n-1) + a (n-2) 에 따라서 다음과 같이 간단하게 구할 수 있었다.
public int fibonacci(int nth) {
switch (nth) {
case 0:
return 0;
case 1:
return 1;
}
return fibonacci(nth - 1) + fibonacci(nth - 2);
}
문제
그런데 이 방법으로 피보나치 수열을 구하는 것은 아주 비효율적이다. 하나의 메서드를 호출할 때 두 개의 메서드를 호출하므로 시간 복잡도가 O(2^n)이 나오기 때문이다. 즉 입력 크기 n에 대해 지수적으로 증가한다.
메모이제이션(Memoization)
메모이제이션이란?
메모이제이션(memoization)은 동일한 입력에 대한 함수 호출의 결과를 저장하여, 나중에 동일한 입력에 대한 함수 호출이 발생할 때, 계산을 피하고 저장된 값을 재사용하는 기법이다. 이를 통하여 중복 계산을 효율적으로 방지하여 알고리즘의 실행 시간을 개선할 수 있다. 일반적으로 재귀적인 알고리즘에서 사용된다.
일반적인 메모이제이션의 작동 과정
- 함수가 호출되면 입력 값을 확인하여, 해당 입력 값이 이전에 계산되었는지 확인한다.
- 만약 입력 값이 이전에 계산되었다면, 저장된 결과를 반환한다.
- 만약 입력 값이 이전에 계산되지 않았다면, 함수를 호출하여 계산을 수행하고 그 결과를 저장한다.
메모이제이션은 보통 배열이나 해시 맵과 같은 자료구조를 사용하여 중간 결과를 저장한다. 이 자료구조를 "메모이제이션 테이블"이라고도 부르며, 입력 값을 키(key)로 사용하고 결과 값을 값(value)으로 저장한다.
메모이제이션을 이용하여 아까의 코드를 개선시켜보자.
public int fibonacci(int n) {
int[] memo = new int[n + 1]; // 중간 결과를 저장할 배열
return fibonacciHelper(n, memo);
}
private int fibonacciHelper(int n, int[] memo) {
// 중간 결과가 이미 계산되어 저장된 경우, 바로 반환
if (memo[n] != 0) {
return memo[n];
}
// 피보나치 수 계산
if (n <= 1) {
memo[n] = n;
} else {
memo[n] = fibonacciHelper(n - 1, memo) + fibonacciHelper(n - 2, memo);
}
return memo[n];
}
위 코드에서 memo 배열은 이전에 계산한 중간 결과를 저장하기 위한 배열이다. memo[n]는 nth 번째 피보나치 수를 저장하는 용도로 사용된다.
fibonacciHelper 메서드는 n 번째 피보나치 수를 계산하는 재귀적인 도우미 메서드입니다. 먼저 memo[n]이 0이 아니라면 이미 계산된 결과이므로 그 값을 반환한다. 그렇지 않은 경우, 계산을 수행하고 그 결과를 memo[n]에 저장한 후 반환한다.
이렇게 메모이제이션을 활용하면 중복 계산을 피할 수 있어 시간 복잡도는 O(n)으로 줄어들게 된다.
메모이제이션은 동적 계획법의 핵심이 되는 기술이라고 하는데.. 동적 계획법은 다음에 알아보는 걸로! 오늘은 아 이런게 메모이제이션이구나 하고 찍먹해보는 걸로!!
'STUDY > JAVA' 카테고리의 다른 글
[TIL] 프로그래머스 - 같은 숫자는 싫어 (GPT 첫 개시!) (0) | 2023.06.27 |
---|---|
[TIL] java.lang.IllegalStateException 해결하기 (0) | 2023.06.26 |
[TIL] 프로그래머스 lv.2 다음 큰 숫자 (비트연산자) (0) | 2023.06.22 |
[TIL] 예외 되던지기(Exception re-throwing)는 언제 사용될까? (0) | 2023.06.21 |
[TIL] ConcurrentModificationException (0) | 2023.06.20 |