문제 해결 패턴 기반 알고리즘

1. 개요

문제를 해결하는 다양한 접근 방식이 존재하며, 특정 패턴을 활용하면 보다 효율적으로 문제를 해결할 수 있다. 여기서는 대표적인 문제 해결 패턴을 소개하고, 각각의 알고리즘과 구현 방법을 설명한다.

---

2. 재귀 (Recursion)

2.1 개념

재귀(Recursion)는 함수가 자기 자신을 호출하는 방식으로 동작하는 알고리즘이다. 주로 분할 정복이나 탐색 문제에서 활용된다.

2.2 피보나치 수열 (Fibonacci Sequence)

수식

Python 코드

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

print(fibonacci(10))  # 출력: 55

2.3 팩토리얼 (Factorial)

수식

Python 코드

def factorial(n):
    if n == 0:
        return 1
    return n * factorial(n - 1)

print(factorial(5))  # 출력: 120

---

3. 분할 정복 (Divide and Conquer)

3.1 개념

분할 정복(Divide and Conquer)은 문제를 작은 부분으로 나누고, 이를 해결한 후 합치는 방식으로 동작한다.

3.2 이진 탐색 (Binary Search)

수식

Python 코드

def binary_search(arr, target, left, right):
    if left > right:
        return -1
    mid = (left + right) // 2
    if arr[mid] == target:
        return mid
    elif arr[mid] > target:
        return binary_search(arr, target, left, mid - 1)
    else:
        return binary_search(arr, target, mid + 1, right)

arr = [1, 3, 5, 7, 9, 11]
print(binary_search(arr, 7, 0, len(arr)-1))  # 출력: 3

3.3 퀵 정렬 (Quick Sort)

Python 코드

def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[len(arr) // 2]
    left = [x for x in arr if x < pivot]
    middle = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]
    return quick_sort(left) + middle + quick_sort(right)

arr = [3, 6, 8, 10, 1, 2, 1]
print(quick_sort(arr))  # 출력: [1, 1, 2, 3, 6, 8, 10]

---

4. 그리디 알고리즘 (Greedy Algorithm)

4.1 개념

그리디 알고리즘은 각 단계에서 최적이라고 생각되는 선택을 하는 방식이다.

4.2 거스름돈 문제 (Coin Change Problem)

Python 코드

def coin_change(coins, amount):
    coins.sort(reverse=True)
    count = 0
    for coin in coins:
        while amount >= coin:
            amount -= coin
            count += 1
    return count

print(coin_change([1, 5, 10, 50, 100, 500], 1260))  # 출력: 6

---

5. 동적 계획법 (Dynamic Programming)

5.1 개념

동적 계획법(DP)은 작은 부분 문제를 해결하고 그 결과를 저장하여 동일한 문제를 다시 계산하지 않도록 하는 방식이다.

5.2 최장 공통 부분 수열 (LCS)

Python 코드

def lcs(X, Y):
    m = len(X)
    n = 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]

print(lcs("AGGTAB", "GXTXAYB"))  # 출력: 4

---

6. 백트래킹 (Backtracking)

6.1 개념

백트래킹은 가능한 모든 경우를 탐색하면서 불가능한 경우를 조기에 포기하는 방식이다.

6.2 N-Queens 문제

Python 코드

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 solve(row):
        if row == n:
            result.append(board[:])
            return
        for col in range(n):
            if is_safe(board, row, col):
                board[row] = col
                solve(row + 1)
                board[row] = -1
    
    result = []
    board = [-1] * n
    solve(0)
    return result

print(solve_n_queens(4))  # 4-Queens 해법 출력

---

7. 마무리

문제 해결 패턴 기반 알고리즘은 다양한 문제를 효과적으로 해결하는 데 중요한 역할을 한다. 각각의 접근 방식을 잘 이해하고 활용하면 알고리즘 문제 해결 능력을 향상시킬 수 있다.