자료구조와 알고리즘
동적계획법 ( DP , Dynamic Programming)
⚡DP란? 메모리를 적절히 사용하여 수행 시간 효율성을 비약적으로 상승시키는 방법입니다. 이미 계산 된 결과(작은 결과)를 별도의 메모리공간에 저장해두고 그 결과가 필요할때 꺼내서 사용하여 다시 계산하지 않도록 하며 일반적으로 탑다운 방식과 바텀업 방식 두가지 방식으로 구현됩니다. ⚡동적계획법이면 자료구조에서 말하는 동적 할당이랑 비슷한거임? 아니오 자료구조에서의 동적할당은 프로그램이 실행되는 도중 실행에 필요한 메모리를 할당하는 기법 을 말합니다. 하지만 동적계획법에서 동적(Dynamic)은 그냥 별 의미 없이 사용된 단어입니다. ⚡DP 이거 언제 쓸 수 있음? 1. 최적 부분 구조(Optimal Substructure)와 2. 중복되는 부분 문제(Overlapping Subpromblem) 두 조건이..
