반응형
SMALL
재귀적 프로그래밍(Recursive Programming) 두번째 시간으로
n개의 원소를 가지는 집합에서 크기가 r인 부분집합을 고르는
경우의 수 즉, 이항계수를 작성해보겠다
이항계수를 식으로 나타내면 아래와 같다
위와 같이 재귀적으로 함수를 작성할 때에는
중복 계산이 발생해 효율이 나빠질 수 있으므로 주의해야하고
메모이제이션(memoization) 처리 등을 해줘야한다
위의 코드에서는 keep_result 배열에 처리 결과를 저장하고있다
이제 유명한 피보나치(Fibonacci) 수열을 작성해보자
먼저 피보나치(Fibonacci) 수열은 중복계산이 나타나므로
앞서 이항계수를 구할 때처럼 메모이제이션(memoization) 처리한다
참고로 동적 프로그래밍으로도 작성해보았다
그런데 메모이제이션을 통해서든 동적 프로그래밍을 통해서든
느린 속도는 어느 정도 해결했다.
사실 행렬을 이용하여 더 빠르게 할 수 있다
하지만 n의 값이 200만 되어도 오버플로우(overflow)가 발생한다
이런 경우는 C언어에서 제공하는 연산으로는 처리가 어렵고
무한 자리를 처리할 수 있도록 구현해야한다
반응형
LIST
'Algorithms' 카테고리의 다른 글
[Algorithms] 선형 탐색(Linear Search)과 이진 탐색(Binary Search) (0) | 2020.07.27 |
---|---|
[Algorithms] 유클리드(Euclid) 호제법 (0) | 2020.07.26 |
[Algorithms] 재귀적 프로그래밍(Recursive Programming)_1 (0) | 2019.08.12 |
[Algorithms] 연결리스트(Linked List)를 이용한 큐(Queue) (0) | 2019.07.29 |
[Algorithms] 배열을 이용한 큐(Queue) (0) | 2019.07.18 |