[Algorithm] DP(Dynamic Programming), 동적 계획법 (Bottom-Up, Top-Down)
#. 동적 계획법? ㅇ 동적계획법 = 다이나믹 프로그래밍(Dynamic Programming), DP- 벨만-포드 알고리즘을 개발한 벨만이 만들어낸 알고리즘- 알고리즘 이름을 어떻게 지으면 기억에 잘 남고, 간지(?)가 날지 생각하다가 다이나믹이라는 단어가 좋아서 이렇게 되었다는.. ㅇ 특징- 다음 상태를 구하기 위해, 이전 상태를 저장하고, 사용(Memoization)- 무엇을 어떻게 저장할지 정하는 것이 중요- 많이 풀어보고, 생각 과정을 연습하는 것이 중요.. ㅇ 적용 순서1. 상태 정의- dp배열을 만들었을 때, index값이 의미하는 상태- 문제의 초기상태를 정의(직관적인 작은 문제의 해)2. 점화식 구하기- 다음 상태를 나타내기 위한 표현식3. 시간복잡도 계산4. 구현 ㅇ 적용 방법1. Top..
https://data-make.tistory.com/384