[Inflearn] 이항계수(메모이제이션)(c/c++)

#. Problem

https://www.inflearn.com/course/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

* The copyright in this matter is in Inflearn

#. Resolution Process

  1. Read and understand problem

  2. Redefine the problem + abstract

  3. Create solution plan (select Algorithm, Data structure)

  4. Prove the plan (check performance time and usage memory)

  5. Carry out the plan

  6. Look back on the plan and find a way to improve it

#. Solve

문제에 메모이제이션이라고 쓰여져있으니,

메모이제이션으로 풀어보자.

ㅇ이항계수

  - N개의 원소를 가지는 집합에서 R개의 원소를 뽑아 부분집합을 만드는 경우의 수

  - nCr

nCr 은 이렇게 쓰일 수도 있다.

n! / (r! x (n-r)!)

n=5, r=3 이 입력되었다면

5! / (3! x 2!) 가 될 것이다.

연산하는 과정에서 

5x4x3x2x1

     3x2x1

        2x1

중복 연산이 발생한다.

1 ~ n 까지의 곱을 미리 저장해놓으면

a[]

1

2

6

24

120

메모리제이션을 이용해서

5! / (3! x 2!) 를 

a[5] / a[3] x a[2] 로 순식간에 연산할 수 있다.

#. Code

#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
 
int a[21];
 
int main(void)
{
    freopen("input.txt", "rt", stdin);
 
    int n, r, i;
    a[1] = 1;
 
    scanf("%d %d", &n, &r);
    for (i = 2; i <= n; i++)
        a[i] = a[i - 1] * i;
 
    printf("%d\n", a[n] / (a[r] * a[n - r]));
 
    return 0;
}

#. Other code

#include<stdio.h>
using namespace std;
 
int dy[21][21];
 
int C(int n, int r){
    if(dy[n][r]>0) return dy[n][r];
    if(n==r || r==0) return 1;
    else return dy[n][r]=C(n-1, r)+C(n-1, r-1);
}
 
int main(){
    int n, r;
    scanf("%d %d", &n, &r);
    printf("%d\n", C(n, r));
    return 0;
}

내가 생각한 메모리제이션이 아니었다..

내가 잘못 알고있던건지.. 허헣..

강사님은 재귀함수를 사용하여 메모이제이션을 구현하셨다.

이항계수가 DFS 로 나뉘어지는 것을 그려보았다.

트리를 하단을 보면 r == 0 이거나 n == r 인 경우 1이 된다.

그리고 동그라미로 표시해놓은 부분을 보면 중복이 생긴다.

이 경우도 미리 연산한 결과를 재사용할 수 있도록 하면 속도가 더 상승할 수 있을 것이다.

5C3 이 어떻게 4C2 + 4C3 으로 분리될 수 있는지 가물가물할 수도 있다.

5C3 은 5명 중 무작위로 3명을 뽑는 경우인데, 

이 경우의 수에 3번이 포함된 경우와 3번이 포함되지 않은 경우가 있다.

말 그대로 

3번이 포함된 경우(4C2 - 3번이 이미 포함되어있으므로 4명 중 2명만 더 뽑으라)

+ 3번이 포함되지 않은 경우(4C3 - 3번이 포함되지 않았으므로 4명 중 3명을 뽑으라)

이렇게 나뉠 수 있다.

재귀함수에 들어가는 매개변수는 아래 그림과 같을 것이다.

line 4) 우선, 메모이제이션 공간을 이차원 배열로 생성한다.

line 6~10) 위에서 보았듯이 n == 0 이거나  n == r 인 경우 1을 return 해준다.

line 9) 재귀함수의 결과를 메모이제이션에 저장한 후 return 해준다.

line 7) 메모이제이션에 미리 연산한 결과가 있다면 재사용을 위해 해당 값을 바로 return 해준다.

#. Result

  - Input --------------------------------------------------------

5 3

------------------------------------------------------------------

  - Output --------------------------------------------------------

10

------------------------------------------------------------------