백트래킹 알고리즘

백트래킹은 해결 가능한 모든 경로를 탐색하는 알고리즘으로, 재귀 호출을 통해 결정 트리를 탐색하며 실패 시 이전 상태로 돌아가는 방식을 사용합니다.

def backtrack(current_path, choices):
    if is_solution(current_path):
        add_to_result(current_path)
        return
    
    for choice in choices:
        if not is_valid(choice):
            continue
        current_path.append(choice)
        backtrack(current_path, updated_choices)
        current_path.pop()

주요 특징

• 결정 트리의 깊이 우선 탐색
• 중단된 경로는 복구 후 다른 선택지를 시도
• 순열/조합 문제 및 N-queen 문제에 적합
• 시간 복잡도는 O(N!)으로 높음

그리디 알고리즘

각 단계에서 최선의 선택을 즉시 수행하여 전체적으로 최적해를 얻으려는 전략입니다. 그러나 항상 최적해를 보장하지 않습니다.

public List<Choice> greedyAlgorithm(Problem problem) {
    List<Choice> solution = new ArrayList<>();
    while (!problem.isSolved()) {
        Choice bestChoice = selectBestChoice(problem.getChoices());
        if (isValid(bestChoice)) {
            solution.add(bestChoice);
            problem.applyChoice(bestChoice);
        }
    }
    return solution;
}

특징 요약

• 현재 상태 기반 최적 선택
• 한 번 선택된 항목은 수정 불가
• 활동 선택 문제, 해밍 코드 생성 등 적용 가능
• 평균 시간 복잡도는 O(N log N)

분할정복 알고리즘

문제를 유사한 작은 하위 문제로 나누고, 각 하위 문제를 해결한 결과를 결합하여 원래 문제를 해결하는 방법입니다.

template <typename T>
T divideAndConquer(T problem) {
    if (problem.size() < threshold) {
        return solveDirectly(problem);
    }
    
    vector<T> subproblems = split(problem);
    vector<T> results;
    
    for (auto sub : subproblems) {
        results.push_back(divideAndConquer(sub));
    }
    
    return merge(results);
}

핵심 구조

1. 문제 분할
2. 하위 문제 해결
3. 결과 통합

동적계획법

재사용 가능한 하위 문제를 저장하여 계산 효율성을 높이는 방법입니다. 최적 부분 구조를 가진 문제에 효과적입니다.

function dynamicProgramming(n) {
    let dp = Array(n+1).fill(0);
    
    dp[0] = baseCase();
    dp[1] = baseCase();
    
    for (let i=2; i<=n; i++) {
        dp[i] = Math.max(dp[i-1], dp[i-2] + ...);
    }
    
    return dp[n];
}

구현 방식

대비표