⚔️ Técnicas de Diseño de Algoritmos

1.1 Divide y Vencerás

Divide y Vencerás (D&C) es una técnica que resuelve problemas dividiéndolos en subproblemas más pequeños del mismo tipo, resolviéndolos recursivamente y combinando sus soluciones.

Estructura General

1. Dividir: Partir el problema en subproblemas más pequeños
2. Conquistar: Resolver los subproblemas recursivamente (caso base si es trivial)
3. Combinar: Unir las soluciones de los subproblemas

Master Theorem

Para recurrencias de la forma T(n) = aT(n/b) + f(n):

Ejemplo: Merge Sort

Implementación

// Merge Sort - C++
void merge(vector<int>& arr, int l, int m, int r) {
    vector<int> L(arr.begin()+l, arr.begin()+m+1);
    vector<int> R(arr.begin()+m+1, arr.begin()+r+1);
    int i = 0, j = 0, k = l;
    while (i < L.size() && j < R.size())
        arr[k++] = (L[i] <= R[j]) ? L[i++] : R[j++];
    while (i < L.size()) arr[k++] = L[i++];
    while (j < R.size()) arr[k++] = R[j++];
}

void mergeSort(vector<int>& arr, int l, int r) {
    if (l < r) {
        int m = l + (r - l) / 2;
        mergeSort(arr, l, m);      // Divide izquierda
        mergeSort(arr, m + 1, r);  // Divide derecha
        merge(arr, l, m, r);       // Combina
    }
}

# Merge Sort - Python
def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])    # Divide izquierda
    right = merge_sort(arr[mid:])   # Divide derecha
    return merge(left, right)       # Combina

def merge(left, right):
    result = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i]); i += 1
        else:
            result.append(right[j]); j += 1
    return result + left[i:] + right[j:]

Otros Ejemplos de D&C

1.2 Programación Dinámica

Programación Dinámica (DP) resuelve problemas combinando soluciones de subproblemas superpuestos, almacenando resultados para evitar recálculos.

Condiciones para usar DP

1. Subestructura Óptima: La solución óptima contiene soluciones óptimas de subproblemas
2. Subproblemas Superpuestos: Los mismos subproblemas se resuelven múltiples veces

Enfoques

Ejemplo: Fibonacci

// Fibonacci con DP - C++
// Top-Down (Memoización)
int memo[1001];
int fib(int n) {
    if (n <= 1) return n;
    if (memo[n] != -1) return memo[n];
    return memo[n] = fib(n-1) + fib(n-2);
}

// Bottom-Up (Tabulación)
int fibBottomUp(int n) {
    if (n <= 1) return n;
    int dp[n+1];
    dp[0] = 0; dp[1] = 1;
    for (int i = 2; i <= n; i++)
        dp[i] = dp[i-1] + dp[i-2];
    return dp[n];
}

// Optimizado O(1) espacio
int fibOptimized(int n) {
    if (n <= 1) return n;
    int a = 0, b = 1;
    for (int i = 2; i <= n; i++) {
        int c = a + b;
        a = b; b = c;
    }
    return b;
}

Ejemplo Clásico: Longest Common Subsequence (LCS)

Dadas dos cadenas X e Y, encontrar la subsecuencia común más larga.

# LCS - Python
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]

# Ejemplo: lcs("ABCDGH", "AEDFHR") = 3 ("ADH")
# Complejidad: O(mn) tiempo, O(mn) espacio

Problemas Clásicos de DP

1.3 Algoritmos Avaros (Greedy)

Greedy toma la decisión localmente óptima en cada paso, esperando que lleve a una solución global óptima.

Cuándo usar Greedy

1. Propiedad Greedy: Una solución global óptima se puede alcanzar eligiendo óptimos locales
2. Subestructura Óptima: Un problema tiene solución óptima que contiene soluciones óptimas de subproblemas

Ejemplo: Activity Selection

Seleccionar el máximo número de actividades que no se solapan.

// Activity Selection - C++
// Greedy: siempre elegir la actividad que termina primero
struct Activity { int start, end; };

int activitySelection(vector<Activity>& acts) {
    // Ordenar por tiempo de fin
    sort(acts.begin(), acts.end(), 
         [](auto& a, auto& b) { return a.end < b.end; });
    
    int count = 1;
    int lastEnd = acts[0].end;
    
    for (int i = 1; i < acts.size(); i++) {
        if (acts[i].start >= lastEnd) {
            count++;
            lastEnd = acts[i].end;
        }
    }
    return count;
}
// Complejidad: O(n log n) por el sort

# Activity Selection - Python
def activity_selection(activities):
    # Ordenar por tiempo de fin
    activities.sort(key=lambda x: x[1])
    
    selected = [activities[0]]
    last_end = activities[0][1]
    
    for start, end in activities[1:]:
        if start >= last_end:
            selected.append((start, end))
            last_end = end
    
    return selected

Greedy vs DP

Ejemplos de Greedy

1.4 Backtracking

Backtracking es una técnica de búsqueda exhaustiva que construye soluciones incrementalmente, abandonando candidatos ("backtrack") cuando detecta que no pueden llevar a una solución válida.

Estructura General

// Plantilla de Backtracking
void backtrack(estado, solución_parcial) {
    if (es_solución(estado)) {
        guardar_solución(solución_parcial);
        return;
    }
    
    for (cada opción válida) {
        hacer_elección(opción);          // Elegir
        backtrack(nuevo_estado, ...);    // Explorar
        deshacer_elección(opción);       // Backtrack
    }
}

// N-Queens - C++
class NQueens {
    int n;
    vector<int> col, diag1, diag2;  // Para verificar ataques O(1)
    
    bool isSafe(int row, int c) {
        return !col[c] && !diag1[row+c] && !diag2[row-c+n-1];
    }
    
    void solve(int row, vector<string>& board, vector<vector<string>>& res) {
        if (row == n) { res.push_back(board); return; }
        
        for (int c = 0; c < n; c++) {
            if (isSafe(row, c)) {
                board[row][c] = 'Q';
                col[c] = diag1[row+c] = diag2[row-c+n-1] = 1;
                
                solve(row + 1, board, res);  // Recursión
                
                board[row][c] = '.';         // Backtrack
                col[c] = diag1[row+c] = diag2[row-c+n-1] = 0;
            }
        }
    }
public:
    vector<vector<string>> solveNQueens(int n) {
        this->n = n;
        col.assign(n, 0);
        diag1.assign(2*n, 0);
        diag2.assign(2*n, 0);
        vector<string> board(n, string(n, '.'));
        vector<vector<string>> res;
        solve(0, board, res);
        return res;
    }
};

# N-Queens - Python
def solve_n_queens(n):
    def backtrack(row, cols, diag1, diag2, board):
        if row == n:
            result.append(["".join(r) for r in board])
            return
        
        for col in range(n):
            if col in cols or (row+col) in diag1 or (row-col) in diag2:
                continue
            
            board[row][col] = 'Q'
            backtrack(row+1, cols|{col}, diag1|{row+col}, diag2|{row-col}, board)
            board[row][col] = '.'  # Backtrack
    
    result = []
    backtrack(0, set(), set(), set(), [['.']*n for _ in range(n)])
    return result

1.5 Ramificación y Poda (Branch & Bound)

Branch and Bound es una extensión de backtracking para problemas de optimización. Usa cotas (bounds) para podar ramas que no pueden mejorar la mejor solución encontrada.

Diferencia con Backtracking

Componentes Clave

1. Branching: Dividir el problema en subproblemas
2. Bounding: Calcular cotas inferior/superior para podar
3. Pruning: Descartar ramas que no pueden mejorar la solución actual

Ejemplo: 0/1 Knapsack con B&B

// 0/1 Knapsack con Branch and Bound - C++
struct Item { int weight, value; double ratio; };
struct Node { int level, profit, weight; double bound; };

double bound(Node u, int n, int W, vector<Item>& items) {
    if (u.weight >= W) return 0.0;

    double profit_bound = u.profit;
    int j = u.level + 1;
    int totweight = u.weight;

    // Greedy: agregar items completos mientras quepa
    while (j < n && totweight + items[j].weight <= W) {
        totweight += items[j].weight;
        profit_bound += items[j].value;
        j++;
    }
    // Agregar fracción del siguiente item (relajación fraccionaria)
    if (j < n)
        profit_bound += (W - totweight) * items[j].ratio;

    return profit_bound;
}

int knapsackBB(int W, vector<Item>& items) {
    int n = items.size();
    for (auto &it : items)
        it.ratio = (double)it.value / it.weight;

    sort(items.begin(), items.end(),
         [](const Item& a, const Item& b){ return a.ratio > b.ratio; });

    queue<Node> Q;
    Node u, v;
    u.level = -1; u.profit = 0; u.weight = 0;
    u.bound = bound(u, n, W, items);
    Q.push(u);

    int maxProfit = 0;

    while (!Q.empty()) {
        u = Q.front(); Q.pop();

        if (u.level == n-1) continue;        // ya no hay más items
        if (u.bound <= maxProfit) continue;  // poda por bound

        // Rama 1: incluir siguiente item
        v.level = u.level + 1;
        v.weight = u.weight + items[v.level].weight;
        v.profit = u.profit + items[v.level].value;

        if (v.weight <= W && v.profit > maxProfit)
            maxProfit = v.profit;

        v.bound = bound(v, n, W, items);
        if (v.bound > maxProfit)
            Q.push(v);

        // Rama 2: NO incluir siguiente item
        v.weight = u.weight;
        v.profit = u.profit;
        v.bound = bound(v, n, W, items);
        if (v.bound > maxProfit)
            Q.push(v);
    }

    return maxProfit;
}

Aplicaciones de B&B