[Algorithm] DP (다이나믹 프로그래밍) 정리
다이나믹 프로그래밍이란, 한마디로 똑같은 계산을 두번 다시 하지 않도록 하는 알고리즘이다. DP는 메모리 공간을 조금 더 사용하는 대신, 연산 속도를 증가시키는 방법이다. 따라서 한번 구한 결과값을 별도의 메모리 공간에 저장하는 방식을 따른다. 이러한 방식을 Memoization(메모이제이션)이라고 한다. DP에도 두가지 방식이 있는데 하나는 Top-Down(하향식), 하나는 Bottom-Up(상향식)이다. '이것이 코딩테스트다' 교재에도 나와있고 백준에도 나와있는 DP의 가장 베이직한 문제 "1로 만들기"를 다이나믹 프로그래밍으로 푼 코드이다. 이때 Bottom-Up(상향식)을 사용했다. Top-Down 방식으로도 구현해보려고 했는데 찾아보니 메모리 초과가 난다고... https://www.acmicp..
TIL
2022. 3. 1. 14:51