23.01.18 TIL 다이나믹 프로그래밍(DP)
오늘 한 일 백준 3문제 풀기 자바 강의 듣기 공부하면서 궁금한 점 다이나믹 프로그래밍(Dynamic Programing) 다이나믹 프로그래밍은 큰 문제를 작게 나누어 푸는 기법이다. 가장 큰 특징은 나누어 둔 작은 문제들을 한번씩만 풀어야 한다는 것이다. 즉, 작은 문제들의 결과를 배열에 저장시키고 그 결과를 사용하는 것이다. 접근 방법 접근 방법으로는 크게 두가지가 있는데 1. Bottom-up방식 (상향식) -작은 문제부터 구해 나가며 큰 문제를 푸는 방식 -보통 for문을 많이 사용 2. Top-down방식 (하향식) -큰 문제에서 필요할 때 작은 문제를 해결해 푸는 방식 -보통 재귀를 많이 사용 대표적으로 피보나치 수열이 있다 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ... ..