목록2024/10/06 (1)

매일 조금씩

DP의 개념과 특징

dp란?문제를 작은 부분 문제들로 나누어 해결하고, 그 해답을 재활용하여 전체 문제를 해결하는 알고리즘.중복되는 부분문제, 최적 부분 구조 문제에 적용된다. 메모이제이션과 타뷸레이션 방식을 통해 시간 복잡도를 크게 줄일수 있다. dp를 구성하는 핵심 개념메모이제이션 (Memoization)주로 재귀 호출과 함께 사용필요한 부분 문제를 만나면 그때 계산하며, 계산된 결과는 캐시에 저장함.탑다운(Top-down) 방식이라고 부름. 메모리 사용량이 더 많을 수 있지만, 불필요한 부분은 계산하지 않기 때문에 효율적임각 부분 문제는 최대 한 번만 계산됨.타뷸레이션 (Tabulation)주로 반복문을 사용하여, 작은 문제부터 순차적으로 해답을 구해가는 방식모든 부분 문제를 미리 계산해 테이블에 저장함.바텀업(Bot..
알고리즘/** 개념 ** 2024. 10. 6. 15:55
이전 Prev 1 Next 다음