Memoizagion?
기억되어야 할 것 이라는 뜻의 라틴어에서 파생된 단어로, 컴퓨터 프로그램이 동일한 계산을 반복적으로 해야 할때, 이전에 계산한 값을 메모리에 저장하여 중복적인 계산을 제거하여 전체적인 실행 속돌르 빠르게 해주는 기법으로 동적 계획법(DP; Dynamic Programmin)의 핵심이 되는 기술이다.
피보나치수열로 알아보는 재귀(Recursion)와 remoization
특히 함수 내에서 자기 자신을 다시 호출하여 작업을 수행하는 재귀 함수를 구현할 때 동일한 계산을 반복해야 할 경우가 많습니다. 그래서 재귀 함수의 대표적인 예제인 피보나치수열 알고리즘을 예시로 memoization이 있다. 피보나치수열은 첫째 및 둘째 항이 1이고, 그 뒤의 모든 항은 바로 앞 뒤의 합인 수열이다. 피보나치 수를 구하는 재귀 함수 알고리즘의 문제점은 엄청난 중복 호출이 발생한다는 점이다.
이러한 단점을 보완할 수 있는 프로그래밍 기법이 바로 memoization 기법이다. 피보나치 수를 구하는 알고리즘에서 fibo(n)의 값을 계산하고 저장해 놓으면 계산에서 필요할 때 값만 가져와서 사용하면 되므로 실행 시간을 줄일 수 있다.
재귀 함수를 사용한 피보나치수열 알고리즘
재귀적 구조로 인한 중복 호출 발생
메모이제이션 기법을 사용한 피보나치수열 알고리즘
메모이제이션 리스트에 값이 저장되어있으면 다시 계산하지 않는 알고리즘 fibo-memo(n)의 결과 값이 memo[n]에 저장된다.
DP; Dynamic Programming 동적 계획법이란?
동적계획법 Dynamic Programming 알고리즘::
크기가 크거나 복잡한 문제를 효율적으로 풀기 위해 작거나 간단한 여러 개의 문제로 나눠서 푸는 방법으로, 그리디 알고리즘과 같이 최적화 문제를 해결하는 알고리즘이다.
입력 크기가 작은 부분 문제들을 해결한 후에 그 해 들을 이용하여 보다 큰 크기의 부분 문제들을 해결하고, 최종적으로 원래 주어진 입력의 문제를 해결하는 알고리즘 설계 기법으로 프로그램 성능의 향상을 기대할 수 있다.
Array.prototype.flat()
:flat() 메서드는 모든 하위 배열 요소를 지정한 깊이까지 재귀적으로 이어붙인 새로운 배열을 생성합니다.
