Algorithm/Study
2021. 9. 24.
다이나믹 프로그래밍
다이나믹 프로그래밍(동적 계획법) 개념 - 한 번 계산한 문제는 다시 계산하지 않도록 하는 알고리즘 - 연산속도와 메모리 공간을 최대한으로 활용할 수 있는 효율적인 알고리즘 - 큰 문제를 작게 나누고, 같은 문제라면 한 번씩만 풀어 문제를 효율적으로 해결한다. - 다이나믹 프로그래밍 vs 분할정복(ex. 퀵 정렬) 더보기 동적 계획법의 접근 방식은 기본적으로 분할 정복 알고리즘과 비슷하다. 위에서도 설명했지만 동적 계획법을 사용하는 알고리즘 역시 주어진 문제를 부분 문제로 나누어 각 부분 문제의 답을 계산하고, 이 계산한 결과값을 이용해 원래 문제의 답을 산출하기 때문이다. 여기서 분할정복과 차이가 생기는 부분은 원래의 문제를 부분 문제로 나누는 방식에 있다. 동적 계획법의 경우 주어진 문제를 나눌 때 ..
