[코딩 인터뷰]개념과 알고리즘 - 재귀와 동적 프로그래밍

 

[ 접근법 ]

: 재귀적 해법은 부분문제에 대한 해법을 통해 완성됩니다. 따라서 많은 경우, 단순히 f(n-1)에 대한 해답에 무언가를 더하거나, 제거하거나, 아니면 그 해답을 변경하여 f(n)을 계산해 냅니다. 아니면 데이터를 반으로 나눠 각각에 대해서 문제를 푼 뒤 이 둘을 병합하기도 합니다.

 

👀 상향식 접근법

: 계산하면서 아래로 내려가는 형태를 말하며 간단한 경우들에 대한 풀이법을 발견하는 것으로부터 시작합니다. 핵심은 이전에 풀었던 사례를 확장하여 다음 풀이를 찾는 것입니다.

 

👀 하향식 접근법

: 출력형태를 만들어놓고 회수하는 형태로 어떻게 하면 N에 대한 문제를 부분 문제로 나눌 수 있을지 생각해 봐야 합니다. 나뉜 부분문제의 경우가 서로 겹치지 않도록 주의해야 합니다.

 

👀 반반 접근법

: 데이터를 절반으로 나누는 방법입니다. 병합 정렬 또한 '반반 접근법'을 이용한 정렬 방법입니다.

 

 

[ 재귀적 해법 vs 순환적 해법 ]

 재귀적 알고리즘을 사용하면 공간 효율성이 나빠질 수 있습니다. 재귀 호출이 한 번 발생할 때마다 스택에 새로운 층을 추가해야 합니다. 이는 재귀의 깊이가 n일 때 O(n)만큼의 메모리를 사용하게 된다는 것을 의미합니다.

 재귀적 알고리즘을 순환적으로 구현하는 것이 더 나을 수 있습니다. 모든 재귀적 알고리즘은 순환적으로 구현될 수 있지만, 순환적으로 구현된 코드는 때로는 훨씬 더 복잡합니다.

 

 

[ 동적계획법 & 메모이제이션 ]

⭐ 동적프로그래밍
: "쿤 문제"를 "부분 문제"로 나누고 "부분 문제"의 정답으로 "큰 문제"의 해답을 찾아가는 알고리즘 설계 기법입니다. 거의 대부분 재귀적 알고리즘과 반복적으로 호출되는 부분문제를 찾아내는 것이 관건입니다.

 

👀 피보나치수열

재귀

int fibonacci(int i){
    if(i==0) return 0;
    if(i==1) return 1;
    return fibonacci(i-1) + fibonacci(i-2);
}

 

하향식 동적 프로그래밍(메모이제이션)

int fibonacci(int n){
    return fibonacci(n, new int[n+1])
}

int fibonacci(int i, int[] memo){
    if(i==0|i==1) return 1;
    if(memo[i]==0){
        memo[i] = fibonacci(i-1, memo) + fibonacci(i-2, memo);
    }
    return memo[i]
}

 

상향식 동적 프로그래밍

int fibonacci(int n){
    if(n==0) return 0;
    else if(n==1) return 1;
    int a = 0;
    int b = 1;
    for(int i=2; i<n; i++){
        int c = a+b;
        a = b;
        b = c;
    }
    return a+b;
}