본문 바로가기
반응형

memoization3

[알고리즘] 동적 계획법(Dynamic Programming, DP), 분할 정복(Divide and Conquer) 동적 계획법(Dynamic Programming, DP), 분할 정복(Divide and Conquer)의 차이와 정의 1. 정의 및 특징 1) 분할 정복(Divide and Conquer) 정의: 상위 문제를 나눌 수 없을 때까지 분할하여 각 하위 문제를 풀고 다시 합병하여 상위 문제의 답을 얻는 방식의 알고리즘이다. 특징 - 하향식 접근법: 상위 문제의 답을 구하기 위해, 아래로 내려가면서 하위의 해답을 구하는 방식. 즉, 상위 문제의 답을 구하기 위해 이전에 수행해야 하는 절차를 수행하는 방식이다.(재귀함수로 구현) - 문제를 쪼갤 때, 부분 문제의 중복이 없다. 예: 병합 정렬, 퀵 정렬 등 1) 동적 계획법(Dynamic Programming, DP) 정의: 하나의 큰 문제를 해결하기 위해, 큰.. 2023. 6. 17.
[알고리즘] 타뷸레이션(Tabulation) 타뷸레이션(Tabulation)의 정의와 메모이제이션(Memoization)과의 차이 타뷸레이션(Tabulation)이란? 1. 동일한 계산을 반복해야 할 경우 한 번 계산한 결과를 메모리에 저장해 두었다가 재사용하여 중복 계산을 방지할 수 있게 하는 기법이다. 2. 중복 계산을 방지하여 전체 실행 속도를 빠르게 한다. 3. 앞으로 계산할 모든 값에 대해 저장하여 초기화 오버헤드가 크다. 4. 초기화 이후에 계산해둔 값을 사용할 때 더 이상의 계산이 필요하지 않다. 5. Table + ulation으로 테이블에 미리 값을 적어놓는다고 생각하자. 차이점 1. 메모이제이션과 비슷하지만, 값을 미리 계산해둔다는 차이점이 있다. 2. 메모이제이션 결과가 필요해질 때 계산한다.(Lazy-Evaluation) - .. 2023. 6. 17.
[알고리즘] 메모이제이션(memoization) 메모이제이션(memoization)이란? 1. 동적 프로그래밍(DP: Dynamic Programing)의 핵심이 되는 기술이다. 2. 동일한 계산을 반복해야 할 경우 한 번 계산한 결과를 메모리에 저장해 두었다가 재사용하여 중복 계산을 방지할 수 있게 하는 기법이다. 3. 중복 계산을 방지하여 전체 실행 속도를 빠르게 한다. 4. 이론적인 용어라 코딩 테스트, 알고리즘에서만 사용하는 용어이고 실제 현장에서는 캐싱(caching)이라는 단어를 더 많이 사용한다. 예) - 피보나치 수열: f(n-1), f(n-2)의 값을 메모이제이션하여 f(n)을 계산한다. - 팩토리얼을: f(n-1), f(n-2) .... 1의 값을 메모이제이션하여 f(n)을 계산한다. 2023. 6. 13.
반응형

티스토리툴바