[ 알고리즘 ] 재귀와 동적 계획법(DP) 쉽게 이해하기 ( 피보나치 수열, 배낭 문제, 최장 공통 부분 수열 등 )

재귀(Recursion)는 함수가 자기 자신을 반복적으로 호출하는 방법입니다. 재귀 함수는 문제를 더 작은 문제로 나누어서 해결하는 방식으로, 한 단계씩 쌓아가면서 전체 문제를 해결합니다. 쉽게 말해, 큰 문제를 여러 개의 작은 문제로 쪼개서 하나씩 해결하는 거라고 생각하시면 됩니다.

재귀 함수의 기본 형태입니다

def recursive_function(n):
    if n == 0:  # 기본 조건 (Base Condition)
        return 1
    return n * recursive_function(n - 1)

위 코드는 팩토리얼을 계산하는 간단한 예시입니다. 입력된 n이 0이 될 때까지 함수가 자기 자신을 호출합니다.

재귀의 핵심은 기본 조건(Base Condition)으로, 이 조건이 있어야 무한히 반복되지 않고 끝날 수 있습니다.

재귀 함수는 기본 조건이 없으면 끝없이 반복되기 때문에 항상 기본 조건을 명확히 하는 것이 중요합니다.

기본 조건이 설정되어야만 함수 호출이 멈추고 결과를 반환할 수 있습니다.

재귀로 문제 풀기

재귀는 특히 이런 상황에서 유용합니다.

문제를 더 작은 문제로 쉽게 나눌 수 있을 때
트리 구조나 그래프처럼 계층적인 구조를 탐색할 때
같은 패턴이 반복되는 문제를 풀 때

재귀는 주로 수학적인 문제나 규칙이 반복되는 문제에 많이 사용됩니다. 예를 들어, 피보나치 수열을 재귀로 쉽게 구현할 수 있습니다. 피보나치 수열은 정의는 다음과 같습니다

F(0) = 0, F(1) = 1
F(n) = F(n-1) + F(n-2) (n ≥ 2)

def fibonacci(n):
    if n <= 1:
        return n
    return fibonacci(n-1) + fibonacci(n-2)

하지만 이 방법은 중복 계산이 많아서 비효율적 입니다. 예를 들어, fibonacci(5)를 계산하려면 fibonacci(4)와 fibonacci(3)을 호출하고, 그 과정에서 fibonacci(3)과 fibonacci(2)도 여러 번 호출됩니다. 이렇게 중복된 계산을 많이 하기 때문에 시간이 오래 걸릴 수 있는데요, 그래서 동적 계획법(DP)을 사용하는 것이 좋습니다.

# 2. 동적 계획법 ( Dynamic Programming , DP )

DP 란 ?

동적 계획법(DP)은 재귀의 비효율적인 점을 해결하기 위해 나온 방법입니다. DP는 문제를 작은 하위 문제로 나누어 해결하고, 이미 계산한 결과를 저장해서 중복 계산을 피하는 방식입니다. 이를 메모이제이션(Memoization) 이라고도 합니다.

메모이제이션은 이전에 계산된 결과를 메모리에 저장하고, 필요할 때 이를 다시 사용함으로써 같은 계산을 반복하지 않도록 합니다. 이렇게 하면 컴퓨터가 해야 할 일이 줄어들고, 계산 속도가 훨씬 빨라집니다. 특히 피보나치 수열처럼 중복되는 계산이 많은 문제에서 DP는 매우 유용하게 사용됩니다.

DP에는 두 가지 주요 방식이 있습니다

탑다운(Top-Down) 방식: 재귀와 메모이제이션을 함께 사용해서 하위 문제를 점진적으로 해결합니다. 이 방식은 재귀를 이용하되, 이전에 계산된 값을 저장해서 중복 계산을 피하는 방식입니다.
바텀업(Bottom-Up) 방식: 작은 문제부터 차례대로 풀어나가는 방식입니다. 보통 반복문을 사용해서 해결하며, 이 방식은 재귀 호출 없이 모든 작은 문제를 직접 해결해 나가는 방식입니다.

탑다운 방식은 재귀를 사용하므로 코드가 직관적이고 이해하기 쉽지만, 호출 스택을 많이 사용해서 메모리 문제가 생길 수 있습니다. 반면에 바텀업 방식은 메모리를 덜 쓰지만 코드가 좀 더 복잡하게 느껴질 수 있습니다.

피보나치 수열 ( Fibonacci Sequence )

앞에서 본 피보나치 수열 문제를 동적 계획법으로 해결하면 중복 계산을 피할 수 있습니다.

아래는 메모이제이션을 활용한 피보나치 수열의 탑다운 방식 구현입니다.

def fibonacci_dp(n, memo={}):
    if n in memo:
        return memo[n]
    if n <= 1:
        return n
    memo[n] = fibonacci_dp(n-1, memo) + fibonacci_dp(n-2, memo)
    return memo[n]

이 방법은 이미 계산한 값을 memo에 저장해 두기 때문에, 필요할 때 바로 사용할 수 있습니다. 이렇게 하면 시간 복잡도가 크게 줄어듭니다. 예를 들어, fibonacci(50)을 구할 때 재귀 방식으로는 매우 오래 걸리지만, 메모이제이션을 사용하면 훨씬 빠르게 결과를 얻을 수 있습니다.

또한, 바텀업 방식으로 피보나치 수열을 구현할 수도 있습니다. 이 방식은 작은 문제부터 차례대로 풀어가며 모든 값을 저장합니다.

def fibonacci_bottom_up(n):
    if n <= 1:
        return n
    dp = [0] * (n + 1)
    dp[1] = 1
    for i in range(2, n + 1):
        dp[i] = dp[i-1] + dp[i-2]
    return dp[n]

이 방식은 반복문을 사용해 각 단계에서 값을 계산하고 저장하므로, 메모리를 효율적으로 사용할 수 있습니다.

배낭 문제 (Knapsack Problem)

배낭 문제는 제한된 용량의 배낭에 최대한 많은 가치를 가지는 물건들을 넣는 문제입니다.
각 물건은 무게와 가치가 있고, 배낭의 용량을 넘지 않으면서 물건의 가치를 최대화해야 합니다.

배낭 문제는 실생활에서도 많이 볼 수 있는데요. 예를 들어, 여행을 갈 때 캐리어에 최대한 많은 물건을 넣고 싶지만, 공간이 제한되어 있어서 중요한 물건만 골라야 하는 상황과 비슷합니다.

배낭 문제는 DP를 사용해서 해결할 수 있습니다. 배낭 문제를 바텀업 방식으로 해결하는 코드는 다음과 같습니다.

def knapsack(weights, values, capacity):
    n = len(values)
    dp = [[0] * (capacity + 1) for _ in range(n + 1)]
    
    for i in range(1, n + 1):
        for w in range(1, capacity + 1):
            if weights[i-1] <= w:
                dp[i][w] = max(values[i-1] + dp[i-1][w-weights[i-1]], dp[i-1][w])
            else:
                dp[i][w] = dp[i-1][w]
                
    return dp[n][capacity]

이 코드에서는 dp 배열을 사용해 각 단계에서 최적의 선택을 기록하고, 마지막에 최대 가치를 반환합니다. 이 문제를 해결하면서 물건을 고르는 과정에서 선택의 중요성을 배우게 됩니다. 여러 선택지 중에서 어떤 것을 고르느냐에 따라 결과가 크게 달라질 수 있습니다.

최장 공통 부분 수열 (Longest Common Subsequence, LCS)

최장 공통 부분 수열(LCS)은 두 문자열에서 가장 긴 공통 부분을 찾는 문제입니다.

예를 들어, "ABCBDAB"와 "BDCAB"의 LCS는 "BCAB" 입니다. 이 문제는 두 문자열 사이의 유사성을 찾아내는 데 사용되고 있습니다.

LCS 문제는 특히 유전자 분석이나 문서 비교 등에서 많이 사용됩니다. 두 개의 문자열이 얼마나 비슷한지 알기 위해 최장 공통 부분 수열을 찾아내는 것 입니다.

이 문제도 DP를 사용해서 해결할 수 있습니다. LCS의 동적 계획법 구현은 다음과 같습니다.

def lcs(X, Y):
    m, n = len(X), len(Y)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if X[i-1] == Y[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])
                
    return dp[m][n]

이 코드는 dp 배열에 각 문자의 비교 결과를 저장하고, 최종적으로 가장 긴 공통 부분 수열의 길이를 반환합니다. 이 문제를 풀다 보면 문자열 사이의 패턴을 찾아내고, 어떻게 공통된 부분을 찾아내는지 이해할 수 있게 됩니다.

# 3.요약 정리

요약 정리

재귀와 동적 계획법(DP)은 알고리즘 문제를 해결하는 중요한 기법입니다.

재귀는 문제를 작게 나누어 직관적으로 해결하는 데 유용하지만, 반복 계산이 많으면 비효율적일 수 있습니다.

이때 DP를 사용하면 중복 계산을 줄이고 훨씬 효율적으로 문제를 해결할 수 있습니다.

피보나치 수열, 배낭 문제, 최장 공통 부분 수열 같은 문제들은 재귀와 DP의 개념을 이해하고 적용하는 좋은 연습이 될 수 있습니다.

재귀는 큰 문제를 작은 문제로 쪼개는 사고를 길러주고, DP는 계산을 최적화하는 방법을 알려줍니다. 이 두 가지 기법을 잘 익혀두면 알고리즘 문제 해결 능력을 크게 향상시킬 수 있습니다.

현재글[ 알고리즘 ] 재귀와 동적 계획법(DP) 쉽게 이해하기 ( 피보나치 수열, 배낭 문제, 최장 공통 부분 수열 등 )

AMoon - 개발자의 각종 개발 정보 공유