안드로이드 개발자 이직 공부 #03
재귀 알고리즘[Android]
3. 이직 공부
- 재귀 알고리즘
1, 1, 2, 3, 5, 8, 13...
피보나치수열을 손 코딩해 보세요.
public int fibonacci(int n) {
if (n < 2) {
return n;
} else {
return fibonacci(n - 1) + fibonacci(n - 2);
}
}
시간 복잡도는 어떤가요?
fibonacci 함수를 n번씩 2번 호출하기 때문에 O(2n)입니다.
재귀(Recursion) 함수는 Java로 개발할 때 잘 안 쓰죠.
자칫하면 무한 루프에 빠질 수도 있고 코드가 직관적이지 않거든요.
스택에도 무리가 가구요.
하나의 함수에서 자신을 다시 호출하여 작업을 수행하는 방식으로 주어진 문제를 푸는 방법이다. 재귀 호출이나 되부름이라고 불리기도 한다.
https://www.youtube.com/watch?v=ln7AfppN7mY
자기 자신을 다시 호출하는 알고리즘입니다.
재귀 알고리즘을 사용하기 좋은 문제로는 팩토리얼, 하노이탑, 피보나치수열 이 있는데 피보나치수열을 봅시다.
public int fibonacci(int n) {
if (n < 2) {
return n;
} else {
return fibonacci(n - 1) + fibonacci(n - 2);
}
}
재귀 함수를 써서 'n = 6'인 fibonacci 값을 얻을 때 보시면,
아래처럼 똑같은 연산을 반복하네요.
fibonacci(6)
= fibonacci(5) + fibonacci(4)
= fibonacci(4) + fibonacci(3) + fibonacci(3) + fibonacci(2)
= fibonacci(3) + fibonacci(2) + fibonacci(2) + fibonacci(1) + fibonacci(2) + fibonacci(1)
....
for loop로 바꿔보세요.
public int fibonacci(int n) {
if(n <2) {
return n;
} else {
int tmp, current=1, last=0;
for(int i = 2; i <= n; i++){
tmp = current;
current += last;
last = tmp;
}
return current;
}
}
시간 복잡도는 어떤가요?
O(n)입니다.
시간 복잡도가 절반으로 줄었네요 ㅎㅎ
이런 게 효율적인 알고리즘인가!! 하는 깨달음을 얻었네요.
만약 fibonacci(10), fibonacci(34), fibonacci(1000), fibonacci(10)을 연속으로 호출하면?
피보나치 함수 안에서는 값을 재활용하지만 이 함수를 호출할 때마다 새로 계산을 해야 해요.
이럴 땐 동적 계획법이 있어요.
Dynamic Programming(동적 계획법) 아시나요?
Dynamic Programming으로 작성해 주세요.
처음엔 다이나믹 프로그래밍이라길래 뭔가 역동적으로? 프로그래밍하는 건가 싶었어요.
평범한 안드로이드 개발자가 접해본 적 없는 용어죠ㅠ
복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법을 말한다.
정렬 알고리즘에 썼던 분할 정복법과 비슷해 보이지만 차이가 있어요.
분할 정복법
1. 해결하고자 하는 문제를 작은 크기의 동일한 문제들로 분할
2. 큰 문제를 해결
동적 계획법
1. 해결하고자 하는 문제를 작은 크기의 문제들로 분할
2. 이 문제들을 바탕으로 큰 문제를 해결.
쉽게 말하면 작은 크기의 문제를 재활용하냐에요.
int [] results = new int [n + 1];
results [1] = 1;
results [2] = 1;
public int fibonacciDP (int n) {
if (results[n] != -1) {
return results[n];
} else {
results [n] = fibonacciDP [i - 1] + fibonacciDP [i - 2];
return results [n];
}
}
동적 계획법과 메모이제이션으로 작성한 코드예요.
시간 복잡도는 O(n)이지만 이 함수를 여러 번 호출한다면 시간 복잡도는 다른 방법에 비해 엄청나게 줄어드네요.
하지만 별도의 저장 공간이 있기 때문에 공간 복잡도는 다른 방법에 비해 안 좋아요.
메모이제이션(memoization) : 매번 같은 동작을 방지하기 위해서 별도의 함수의 결과를 저장하는 배열을 마련해둔 후 이 값을 재활용하는 최적화 기법.
