👀 Week03 요약
알고리즘 마지막 주차! 이번 주에는 아래 내용들을 살펴보았다.
1) 동적 프로그래밍
2) 그리디 알고리즘
🧐 다이나믹 프로그래밍이란?
다이나믹 프로그래밍이란 문제를 효율적으로 풀기 위해 복잡한 큰 문제를 더 작은 하위 문제로 나누어 푸는 방법이다.
이 방법은 동일한 하위 문제를 반복해서 풀지 않고, 중복되는 계산을 제거하여 효율적으로 문제를 풀 수 있다.
다이나믹 프로그래밍 구현 방법은 크게 top-down 방식과 bottom-up 방식으로 나누어 살펴볼 수 있다.
⬇️ top-down 방식
top-down 방식은 큰 문제를 작은 하위 문제로 나누고, 각 하위 문제의 해결을 위해 재귀 함수를 호출한다.
이 때 중복 계산을 피하기 위해 메모이제이션 기법을 사용하여 계산한 결과를 메모리 공간에 메모 해놓고, 같은 문제를 다시 호출하면 메모했던 결과를 그대로 가져온다.
⬆️ bottom-up 방식
bottom-up 방식은 작은 하위 문제부터 시작해서 큰 문제까지 순차적으로 해결해나가는 방법인데, 계산한 값을 dp 테이블에 저장해나가는 방식을 사용한다.
일반적으로 재귀보다 반복문이 속도가 더 빠르므로, top-down 방식을 bottom-up 방식으로 바꾸려고 시도하는 경우가 많다.
📝 관련 문제 풀이
