재귀, 백트래킹, 동적 프로그래밍의 공통점과 차이점

공통점

• 복잡한 문제를 더 작은 부분 문제로 나누어 해결하는 방식
• 대게 최적화 문제나 조합 문제를 해결하는데에 사용한다.

---

차이점

재귀

특징

• 함수가 자기 자신을 호출하여 문제를 해결
• 종료조건(base case)이 필수적

예시

: 팩토리얼 계산, 하노이 탑, 피보나치 수열

# 피보나치 수열
def factorial(n):
    if n == 0 or n == 1:
        return 1
    return n * factorial(n-1)

# 하노이 탑
def hanoi_tower(n, start, end, middle):
    if n == 1:
        print(f"원반 1을 {start}에서 {end}으로 옮깁니다.")
        return
    
    hanoi_tower(n-1, start, middle, end)
    print(f"원반 {n}을 {start}에서 {end}으로 옮깁니다.")
    hanoi_tower(n-1, middle, end, start)

# 사용 예
n = 3  # 원반의 개수
hanoi_tower(n, 'A', 'C', 'B')

# 실행 결과
원반 1을 A에서 C으로 옮깁니다.
원반 2을 A에서 B으로 옮깁니다.
원반 1을 C에서 B으로 옮깁니다.
원반 3을 A에서 C으로 옮깁니다.
원반 1을 B에서 A으로 옮깁니다.
원반 2을 B에서 C으로 옮깁니다.
원반 1을 A에서 C으로 옮깁니다.

• 장점: 구현이 직관적이고 간단하다.
• 단점: 중복 계산이 많이 발생할 수 있어 비효율적일 수 있음.

 

백트래킹(Backtracking)

특징

• 가능한 모든 경우의 수를 탐색하는 완전 탐색 기법
• 해를 찾는 도중 해가 아니면 되돌아가서 다시 탐색

예시

: N-Queens, 스도쿠, 부분집합의 합

# N-Queens
def solve_n_queens(n):
    def is_safe(board, row, col):
        # 같은 열, 대각선 체크
        for i in range(row):
            if board[i] == col or \
               board[i] - i == col - row or \
               board[i] + i == col + row:
                return False
        return True

    def backtrack(board, row):
        if row == n:
            solutions.append(board[:])
            return
        for col in range(n):
            if is_safe(board, row, col):
                board[row] = col
                backtrack(board, row + 1)

    solutions = []
    backtrack([-1] * n, 0)
    return solutions

• 장점: 불필요한 탐색을 줄여 효율성을 높임 👉 가지치기(pruning)
• 단점: 최악의 경우 모든 경우를 다 살펴봐야 할 수 있다.

 

동적 계획법(DP, Dynamic Programming)

특징

• 큰 문제를 작은 부분 문제로 나누어 해결
• 부분 문제의 결과를 저장하여 재사용(메모이제이션)

예시

: 피보나치 수열, 최장 증가 부분 수열(LIS), 최장 공통 부분 수열(LCS), 배낭 문제(Knapsack)

# 피보나치 수열
def fibonacci(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]

# 최장 증가 부분 수열(LIS)
def longest_increasing_subsequence(arr):
    n = len(arr)
    # dp[i]는 arr[i]로 끝나는 최장 증가 부분 수열의 길이
    dp = [1] * n
    
    for i in range(1, n):
        for j in range(i):
            if arr[i] > arr[j]:
                dp[i] = max(dp[i], dp[j] + 1)
    
    # 가장 긴 증가 부분 수열의 길이 반환
    return max(dp)

# 사용 예
arr = [10, 22, 9, 33, 21, 50, 41, 60, 80]
print(longest_increasing_subsequence(arr))  # 출력: 6

• 장점: 중복 계산을 피해 효율적으로 문제를 해결
• 단점: 메모리 사용량이 증가할 수 있다.

---

간단한 비유

재귀: 큰 퍼즐을 작은 퍼즐로 나누어 푸는 것
백트래킹: 미로에서 막다른 길을 만나면 되돌아가서 다른 길을 찾는 것
동적 계획법: 이미 푼 수학 문제의 답을 메모해두고 다음에 재사용하는 것

 

각 방법은 문제의 특성에 따라 선택적으로 사용되며, 때로는 함께 사용되기도 한다.

이 셋을 완전한 별개의 알고리즘이라 보긴 어렵다. 서로 연관되며 중첩사용하기도 한다.

• 백트래킹, 동적 계획법 모두 재귀를 사용하여 구현 가능
• 재귀로 구현된 알고리즘이 많은 중복 계산을 포함한다면, 동적 계획법으로 최적화 가능
• 백트래킹 문제 중 일부는 동적 계획법으로 더 효율적으로 해결할 수 있음

---

백트래킹? 동적 계획법?

나는 이 둘이 헷갈릴때가 있다... 오마이깟

 

두 기법 모두 복잡한 문제를 더 작은 부분 문제로 나누어 해결하지만, 접근 방식·사용 목적이 다르다.

 

주요 차이점

백트래킹	동적 계획법
모든 가능한 해를 탐색	"최적의 해'를 찾는데에 중점
가능한 모든 경우를 탐색하며 필요없는 경우를 제거	부분 문제의 결과를 저장하여 재사용
주로 결정 문제, 모든 해를 찾는 문제에 사용	주로 최적화 문제

 

또한 백트래킹은 주로 재귀로 구현된다. 물론 위에 명시했다시피 동적 계획법도 재귀로 구현되는 경우가 있다. 하지만 재귀가 사용되는 빈도를 따져보면 백트래킹 >> 재귀인 듯 싶다.