DP 썸네일형 리스트형 Dynamic Programming 2: 재귀(top-down) vs. DP(bottom-up) (백준 11066, 1520, 1937번 파이썬) Dynamic Programming(DP) 개념을 처음 소개할 때 빠지지 않고 등장하는 게 피보나치 수열이다. 설명 글을 요악하면 다음과 같다. 1) 피보나치 수열을 재귀함수를 이용해 구한다. 2) 재귀함수로 구할 때 중복된 계산이 발생한다. 어차피 같은 답을 내놓는 연산을 여러 번 반복하니 불필요하고 비효율적이다. 3) 불필요한 연산을 방지하기 위해 memoization, 즉 DP 개념을 도입한다. 여기에 핵심이 있다. 우리는 같은 DP 문제에 대해 재귀로 풀 수도 있고, DP로도 풀 수 있다. 이유는 애초에 DP 문제가 다음 성질을 지니기 때문이다. 1) 큰 문제(마지막 항, f(n), 구하고자 하는 답, 현재 상태)를 작은 문제(초기값, 이전 상태, 직전 단계)에 의존하는 관계식으로 표현할 수 있다.. 2023. 3. 28. 15:42 ㆍ 알고리즘과 자료구조/Dynamic Programming 이전 1 다음
