Please enable JavaScript.
Coggle requires JavaScript to display documents.
Capítulo 3 Parte 1: Problem Solving Paradigms - Coggle Diagram
Capítulo 3 Parte 1: Problem Solving Paradigms
3.1 Overview and Motivation
Quatro paradigmas principais:
Complete Search (Brute Force)
Divide and Conquer
Greedy
Dynamic Programming (DP)
Importância: cada problema precisa da “ferramenta” certa
Exemplo com 4 tarefas simples (máximo, k-ésimo, maior gap, subsequência crescente)
Relação:
Complete Search → tentativas exaustivas
Divide & Conquer → separa em subproblemas menores
Greedy → escolhas locais
DP → resolve subproblemas com memorização e otimização global
3.2 Complete Search (Brute Force)
Definição: Explorar todas as possibilidades (enumerar ou backtracking)
Uso: Quando não há outra solução viável / problema pequeno
Técnicas:
Iterative Complete Search (loops aninhados)
Recursive Complete Search (backtracking)
Otimizações:
Filtrar vs. Gerar (Filter vs Generate)
Podar ramos inviáveis cedo (Prune early)
Usar simetrias
Pré-cálculos (Precomputation)
Resolver de trás pra frente (Backward solving)
Otimizar código e uso de memória
Aplicações: pequenas instâncias, verificação de hipóteses, base para algoritmos melhores
3.3 Divide and Conquer
Ideia: dividir o problema → resolver partes menores → combinar
Etapas:
Dividir o problema
Resolver subproblemas
Combinar soluções
Exemplos de uso:
Ordenação (MergeSort, QuickSort)
Pesquisa Binária
Fenwick Tree, Segment Tree
Usos criativos:
Binary Search in dynamic contexts
“Binary Search the answer” (busca sobre respostas contínuas)
Bisection Method
Complexidade típica: O(log N) para busca; O(N log N) para ordenação
3.4 Greedy
Ideia: escolher sempre a melhor opção local esperando ótimo global
Condições necessárias:
Subestruturas ótimas
Propriedade gananciosa (Greedy property)
Vantagens: simples, rápido
Desvantagens: nem sempre ótimo
Técnicas:
Ordenar e tomar escolhas “locais”
Interval Covering → escolher o que cobre mais área
Station Balance → balanceamento com sorting
Aplicações em ICPC: normalmente problemas com escolhas sequenciais e restrições simples
3.5 Dynamic Programming (DP)
Definição: Resolver problemas de otimização contando com sobreposição de subproblemas
Habilidades-chave:
Definir estados (states)
Definir transições entre subproblemas
Armazenar e reutilizar resultados (memoization/tabulação)
Tipos:
Top-Down (recursivo com memorização)
Bottom-Up (iterativo com tabela)
Vantagens: resolve muitos problemas de otimização
Quando usar: se há subproblemas repetidos e sobreposição de soluções