백트래킹(BackTracking)은 현재 상태에서 가능한 모든 후보군을 따라 들어가며 해결책에 대한 후보를 구축해 나아가다 가능성이 없다고 판단되면 즉시 후보를 포기하면서 정답을 찾아가는 범용적인 알고리즘이다. BackTracking vs Dynamic Programming 백트래킹과 동적 계획법은 재귀를 통해 문제를 해결한다는 공통점이 있지만, 근본적인 차이점을 가지고 있다. 백트래킹(Backtracking) 백트래킹은 현재 상태에서 가능한 모든 후보군(Decision Space)를 하나씩 살펴가면서 해가 될 가능성이 있으면 후보를 구축하고, 해가 될 가능성이 없다면 즉시 후보를 포기하면서 해를 찾아나가는 방식이다. 이때, 해가 될 가능성이 있으면 유망하다(promising)고 하며, 유망하지 않은 노..

동적 계획법(Dynamic Programming)이란 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법을 말한다. 특정한 알고리즘이 아닌 하나의 문제 해결 패러다임으로 볼 수 있다. Dynamic Programming의 조건 분할 가능 큰 문제를 작은 문제로 나눌 수 있을 때 (Problem → Subproblems) 부분 문제 반복(Overlapping Subproblems) Subproblem들이 겹칠 때 → memoization을 통해 필요한 연산 수를 줄일 수 있음 최적 부분 구조(Optimal Substructure) Subproblems의 Solution으로 더 큰 규모의 Problem의 Solution을 구할 수 있을 때 대표 문제 : 피보나치 수열 Fibonacci 📌 Naive R..