fibonacci (2) 썸네일형 리스트형 메모이제이션 : 중복 연산 해결 (러시안 페인트공 알고리듬) 이 포스팅에서는 메모이제이션을 논하려고 합니다. 메모이제이션은 중복되는 연산의 결과를 저장하여, 연산 횟수를 줄이는 소프트웨어 엔지니어링 기술입니다. 소프트웨어 개발 중에는 항상 하게 되는 선택이 cpu를 사용하는가 메모리를 사용하는가입니다. 이 기술은 컴퓨팅 리소스 중 cpu의 사용량을 줄이는 대신 메모리의 사용량을 늘려줍니다. 메모이제이션을 잘 사용하면 다양한 알고리듬을 가속화할 수 있는 아주 중요한 기술입니다. 긴 글과 개념적인 설명은 여기서 마치겠습니다. 자세한 설명을 원하시면... 전공서적이나 위키피디아를 참고하세요. 여기선 간단한 예제로 설명하겠습니다. 사용하는 예제는 피보나치수열입니다. 피보나치 수열의 알고리듬 구조상 설계는 자연스럽게 재귀 호출이 되고, 메모이제이션을 이용하면 구동 시간을 .. C++를 이용한 피보나치 수열 구현 (fibonacci) 이 포스트의 목적은 가끔 예제로 이용하는 피보나치 수열을 구현하는 방법에 대한 포스트입니다. 만들어 보니 7가지가 나왔으며, 버전에 따라 재귀 호출, 메모리제이션 등을 이용해 최적화하는 방식으로 구현됩니다. 먼저 피보나치수열을 알아봐야죠. 피보나치수열은 아래 규칙을 따르는 수열입니다. $$f_0 = 0$$ $$f_1 = 1$$ $$f_n = f_{n-1} + f_{n-2} \quad ( n \in\left \{2,3,4,\cdots\right\} )$$ 구조는 단순하지만 구현 시 오버플로우와 중복 연산에 주의해야 합니다. 그럼 먼저 간단히 구현해 보겠습니다. 별다른 소프트웨어 공학의 기술이 들어 가진 않지만 설계 시엔 약간 두통을 유발합니다. #include #include using namespace .. 이전 1 다음
