왜 필요할까?
동적 계획법은 이미 진행되었던 연산이 불필요하게 다시 반복되는 비효율성을 보완하기 위해 만들어졌다
새로운 연산을 기록하고, 이미 진행되었던 연산은 기록에서 불러오는 식이라고 이해하면 된다
개념
이때 기록에 사용되는 개념이 '메모이제이션(Memoization)' 인데, 연산의 결과를 저장해두고 필요할 때 꺼내쓰는
공간이라고 이해하면 된다
동적 계획법은 Top-Down 과 Bottom-Up 두 가지 진행 방법이 있는데,
Top-Down 은 문제를 해결하는 진행 과정이 위에서 아래로 진행되는 것을 의미하고
Bottom-Up 은 그 방향이 아래에서 위로 진행되는 것을 의미한다
예시
아래는 동적 계획법을 이용한 알고리즘 문제 풀이 예시이다
2021.10.19 - [백준 풀이] - [백준 풀이_Java] 1463 1로 만들기
[백준 풀이_Java] 1463 1로 만들기
나의 처음 생각 3으로 나누었을 때 나머지가 0인지, 그리고 0이 아닐 때 홀수인지 짝수인지로 구분해서 어떤 규칙을 찾아내려고 했었다 그런데 규칙 찾기에는 실패했고 숫자를 키워가면서 경우
programming-hyerim.tistory.com
장점 및 단점
동적 계획법은 그리디 알고리즘과는 반대되는 기법이다.
그리디 알고리즘은 모든 해를 구하지 않고 그 순간에 최적의 해를 찾는 방식인 반면,
동적 계획법은 모든 방법을 진행해 모든 해를 구하면서 최적의 해를 찾아내는 방식이다
그리디 알고리즘의 해는 도출된 값이 항상 최적이라고 단정지을 수는 없지만,
동적 계획법을 이용한다면 그 해는 최적이라고 할 수 있을 것이다
물론 동적 계획법이 그리디 알고리즘보다 시간이 더 오래 걸린다는 단점은 있다