본문 바로가기

728x90

memoization2

[DP 개념] #2_동적계획법(1) 인프런 사이트의 영리한 프로그래밍을 위한 알고리즘 강좌를 참고하여 글을 작성하였습니다. https://www.inflearn.com/course/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EA%B0%95%EC%A2%8C/lecture/4126?tab=note 영리한 프로그래밍을 위한 알고리즘 강좌 - 인프런 | 학습 페이지 지식을 나누면 반드시 나에게 돌아옵니다. 인프런을 통해 나의 지식에 가치를 부여하세요.... www.inflearn.com 동적계획법 순환식을 계산의 중복없이 효과적으로 푸는 방법 동적계획법의 특징 - 일반적으로 최적화 문제 혹은 카운팅 문제에 적용됨 - 주어진 문제에 대한 순환식을 정의한다. - 순환식을 memoization 혹은 bottom-up 방식으로 .. 2021. 7. 28.

[DP 개념] Dynamic Programming#1_피보나치 수열,Memoization,Bottom-up 방식 피보나치 수열 f(n) = f(n-1) + f(n-2) (단, n>2) 이것을 자바 코드로 구현해 보면, fib(3)이면 결과는 2일 것이다. f(1)=1이고,f(2)=1이기 때문에 f(3)은 2가 된다. Memoization 피보나치 수열은 이미 계산한 수를 중복으로 계산하는 경우가 발생하기 때문에 굉장히 비효율적이다. 계산의 중복을 피하기 위해 이미 계산된 값을 기억해두는 것. Memoization에서 저장해 놓은 배열을 cache 라고 부른다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 public class DP { static int[] f = new int[10000]; static int fib(int n) { if (n == 1 || n == 2) { ret.. 2021. 7. 26.

이전 1 다음

728x90

티스토리툴바