.png)
오늘은 프로그래머스 동적계획법 알고리즘테스트에 있는 N으로 표현 문제를 풀려고 하였으나, 모든 블로그를 찾아보고 코드를 보아도 해석이 안되어서 동적계획법 개념이 어떤건지 이해가 우선이 되어야 하겠다는 생각으로 동적계획법 개념을 정리하였습니다.
출저 : https://coding-all.tistory.com/2
동적계획법의 이해
우선 동적계획법 (Dynamic Programming) 이라는 말을 사용한 '벨만'이라는 사람은 Dynamic이라는 단어가 멋있어서 선택하였다고 한다.
그래서 동적 계획법을 말한다면 '큰 문제를 작은 문제로 나눠서 푸는 알고리즘'이라고 단어를 이해할 수 없기에 알고 있으면 된다.
메모이제이션
동적계획법을 이해하기에 대표적인 예 중 하나는 이항계수계산이다.
예를 들어 binary(4,2) 호출했을때 아래와 같이 함수가 재귀적으로 호출된다.
| binary(4,2) 중복 제거 전 | binary(4,2) 메모이제이션 |
|---|---|
 출저 : https://coding-all.tistory.com/2 |
 출저 : https://coding-all.tistory.com/2 |
그림을 비교하였을 때 메모이제이션 기법은 저장된 결과를 배열에 저장한뒤, 다음에 계산이 필요할 때는 저장된 값을 불러와서 시간 복잡도도 훨씬 줄어들게 된다. 이러한 기법을 메모이제이션라고 한다.
Top-Down
위에서 아래로 내려오는 방식이다. 기존 재귀와 비슷하므로 비교해보자
기본 재귀 피보나치
점화식을 그대로 사용가능하다
Top-Down 메모이제이션 방식
기억해둘 행렬을 선언하는게 포인트!
Bottom-up
for문을 이용해서 처음값부터 다음값을 계산해 나가는 방식이다.
성능테스트
아래 그림과 같이 시간적으로 동적계획법이 유리하다.
동적계획법 이용
동적계획법은 최적값을 구할때 주로 사용한다.
1. 큰문제를 작은 부분문제로 나눈다.
2. 범위를 정해 초기값이 중요하다.
참고
https://coding-all.tistory.com/2
https://velog.io/@godori/banner-maker-update GODORI
https://banner.godori.dev/ 배너생성기
