안드로이드 개발자 이직 공부 #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) : 매번 같은 동작을 방지하기 위해서 별도의 함수의 결과를 저장하는 배열을 마련해둔 후 이 값을 재활용하는 최적화 기법.

---