알고리즘

[Algorithm/Swift] 동적계획법(DP)

📚 알고리즘 문제를 풀다가 기록해둬야 할 것 같아서 오랜만에 글 끄적끄적 📝 동적 계획법(DP; Dynamic Programming)이란 ? 큰 문제를 작은 하위 문제로 나누어 해결하는 알고리즘 설계 기법으로, 주어진 문제를 여러 개의 하위 문제로 분할하고 각 하위 문제의 결과를 저장하여 저장한 값을 이용해 상위 문제를 점진적으로 해결하는 방식을 사용한다. DP는 중복되는 하위 문제들이 존재할 때 효과적으로 사용된다. 동일한 하위 문제가 여러 번 반복해서 계산되는 경우, DP는 이전에 계산한 값을 저장해 두었다가 재사용함으로써 중복 계산을 피할 수 있다. 이를 "Memoization"이라고도 부른다. 💡 메모이제이션(Memoization)은 이전에 계산한 값을 메모리에 저장하는 방식으로 중복 수행을 제거..