알고리즘 설계 기법 ②

1. 분할정복 (Divide-and-Conquer)

• 크기를 줄여가며 문제를 해결하는 기법 (recursion 기반)

🔹 Merge Sort

1. 주어진 배열을 둘로 나눈다.
2. 두 subarray를 각각 정렬 (recursion)
3. 정렬된 두 subarray를 합쳐 하나의 정렬된 배열로 만든다.

🔹 분할정복의 패턴

• Divide : 문제를 더 작은 문제로 나눔.
• Delegate : 재귀 호출을 통해 작은 문제 해결.
• Combine : 부분 문제의 해를 합쳐 최종 결과 생성.

🔹 Binary Search

• 정렬된 배열에서 O(log n) 시간 복잡도로 탐색.
• 중간값을 기준으로 왼쪽 또는 오른쪽에서 재귀적으로 탐색.

🔹 Fast Multiplication (Karatsuba Algorithm)

• 일반적인 O(n²) 곱셈보다 빠른 O(n^1.584) 알고리즘.
• bc + ad = (a-b)(c-d) + ac + bd 패턴을 이용하여 재귀 호출 횟수를 4회 → 3회로 줄임.

---

2. 백트래킹 (Backtracking)

• 모든 가능한 경우를 탐색하며 최적해를 찾는 기법.
• 필요 없는 경우의 수는 가지치기(pruning)를 하여 탐색량을 줄임.

🔹 N-Queen 문제

• 체스판 위에서 N개의 퀸이 서로 공격하지 않도록 배치하는 문제.

🔹 Longest Increasing Subsequence (LIS)

1. 어떤 수열에서 가장 긴 증가 부분 수열을 찾는 문제.
2. 각 원소를 포함할지 말지를 결정하는 방식으로 재귀적으로 해결.
3. 시간 복잡도: O(2^n)

LISBigger(i, j):
    if j > n:
        return 0
    elif A[i] >= A[j]:
        return LISBigger(i, j+1)
    else:
        skip = LISBigger(i, j+1)
        take = LISBigger(j, j+1)+1
        return max(skip, take)
LIS(A):
    A[0] = float("-inf")
    return LISBigger(0, 1)

---

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

• 한 번 계산한 값을 저장하여 중복 계산을 피하는 기법.
• "반복 없는 재귀" 또는 "재귀 없는 백트래킹"이라고도 볼 수 있음.

🔹 피보나치 수열

• 재귀 호출을 직접 사용하면 O(2^n) 시간복잡도.
• DP를 이용하면 O(n)으로 개선 가능.

def iterFibo(n):
    F = [0] * (n + 1)
    F[0], F[1] = 0, 1
    for i in range(2, n + 1):
        F[i] = F[i - 1] + F[i - 2]
    return F[n]

🔹 Longest Common Subsequence (LCS)

• 두 문자열에서 가장 긴 공통 부분 수열을 찾는 문제.
• 점화식:
  • A[i] == B[j] → L(i, j) = L(i-1, j-1) + 1
  • A[i] ≠ B[j] → L(i, j) = max(L(i-1, j), L(i, j-1))

def LCS(i, j):
    if i == 0 or j == 0:
        return 0
    if A[i] == B[j]:
        return LCS(i-1, j-1) + 1
    else:
        return max(LCS(i-1, j), LCS(i, j-1))

🔹 DP의 핵심

1. 부분 문제 정의: 무엇을 계산할 것인가?
2. 점화식 설정: 어떻게 계산할 것인가?
3. 반복적 구현: 테이블을 채우는 방식으로 최적해를 구함.

4. 그리디 (Greedy Algorithm)

• 매 단계에서 최적의 선택을 하면서 최종 최적해를 찾는 방법.
• 일반적으로 최적해를 보장하지 않으나, 특정 문제에서는 효과적.

정리

• 분할정복 : 문제를 작게 쪼개서 해결하기
• 백트래킹 : 모든 경우를 탐색하되, 가지치기를 이용해 탐색량을 줄이기
• DP : 중복 계산을 없애고 효율적으로 최적해를 찾기
• 그리디 : 현재에서의 최선의 선택을 하면서 해결하기