본문 바로가기
<알고리즘 문제풀이&연습>/[C++] 백준

[백준 11050] 이항계수 1 (반복, 재귀)

by 사용자 BlockDMask 2017. 7. 31.
반응형
  • 안녕하세요. BlockDMask 입니다.

  • 비가 추적추적 내리는 월요일이네요. 오늘의 문제를 포스팅 해보겠습니다.

0. 제목

  • BOJ 11050 이항계수 1

  • 백준 11050 이항계수 1 

  • C++ 이용해서 풀었습니다.

1. 문제 설명


자연수 N과 정수 K가 주어졌을때, 이항계수  

를 구하는 문제입니다.


2. 풀이 과정


이항계수( binomial coefficient ) 는 경우의 수를 계산할때 사용하는 것으로 알고있습니다.

n개의 서로다른 것 들 중에서 k 개를 선택하는 것의 조합(combination)의 경우의 수를 구하는 것입니다.



로 나타내고 이는



으로 나타낼 수 있습니다.


팩토리얼(Factorial)은 반복문과 재귀 두가지 방법으로 표현 할 수 있기 때문에


두가지 방법 모두를 사용하여 풀어보았습니다.


3. 함수 설명


T1) 반복문에서의 Factorial 함수

num을 인자로 받아서,

반복문을 통해 num * num-1 * num-2 * . . . . . . . .* 1 을 구합니다.


T2) 재귀함수에서의 Factorial 함수

num을 인자로 받습니다.

재귀 함수에서는 순환부와 종료부로 이루어져있어야하는데, 

종료부는 num이 1 또는 0 인 경우 return 1을 합니다.


그렇지 않으면 순환부로 넘어가서

return Factorial(num-1) * num; 으로 호출하게됩니다.


ex) num이 3일때 재귀함수의 흐름을 보겠습니다.

num = 3; -> 순환부로 갑니다.

return Factorial( 3 - 1 ) * 3;


num = 2; -> 순환부로 갑니다.

return Factorial( 2 - 1 ) * 2;


num = 1; -> 종료부로 갑니다.

return 1;


이제 다시 역순으로 올라가게 되면,


num =1 일때 return 이 1이므로 Factorial (2-1) 의 값은 1 입니다.

num = 2 일때 return 이 1 * 2 이 되므로 Factorial (3-1) 값은 2 입니다.

num = 3일때 resutrn 이 2 * 3 이 되므로


3! = Factorical(3) = 6 이 됩니다.


4. 코드


T1) 반복문을 이용한 이항계수 구하기

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include<iostream>
 
using namespace std;
 
//반복문 이용. 
int Factorial(int num){
    if(num == 0return 1;
    
    int result = 1;
    
    for(int i=num; i>=1 ; i--){
        result *= i;
    }
 
    return result;
}
 
 
int main(void){
    
    int n, k;
 
    cin >> n >> k;
 
    cout << Factorial(n) / (Factorial(k) * Factorial(n-k));
    
    return 0;    
}
cs


T2) 재귀함수를 이용한 이항계수 구하기

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include<iostream>
 
using namespace std;
 
//재귀 이용.
int Factorial(int num){
    if(num == 1 || num == 0){
        return 1;
        
    }else{
        return Factorial(num-1* num;
    }
 
}
 
int main(void){
    
    int n, k;
 
    cin >> n >> k;
 
    cout << Factorial(n) / (Factorial(k) * Factorial(n-k));
    
    return 0;    
}
cs


5. 인증


T1) 반복문 이용


T2) 재귀 함수 이용

출처 : https://www.acmicpc.net/problem/11050

읽어주셔서 감사합니다.


반응형

댓글0