ctrl+k, o : .cpp 파일에서 매칭되는 .h(header)파일로 이동
반응형
'Programming > Visual studio' 카테고리의 다른 글
| occcont.cpp line 925 (ocx loading 오류) (0) | 2017.12.17 |
|---|
visual studio 단축키
2017. 11. 12. 09:55
tistory에서 latex 쓰기
2017. 11. 8. 13:02
tistory 설정
다음 스크립트를 <head>와 </head> 사이에 넣어주면 됨
적용후 사용법
실제 사용하는 방법은 다음처럼 $로 시작하고 $로 끝나도록 해주면 됨
$_{n}C_{k}$
$_{n}C_{k}$
새로운 줄에 가운데 정렬해서 표현하고 싶으면 $대신 $$로 감싸주면 됨, 그러면 다음처럼 렌더링 됨
$$_{n}C_{k}$$
주의할점
tistory 관리 > 꾸미기 > 모바일에서 "티스토리 모바일웹 자동 연결을 사용하지 않습니다"로 바꾸어야 한다. 그렇지 않으면 모바일에서는 렌더링이 제대로 되지 않을 수 있다.
반응형
'tistory' 카테고리의 다른 글
| 티스토리에 소스코드 붙여넣기(syntax higlight, Color Scripter) (0) | 2019.03.18 |
|---|---|
| 티스토리에서 클립보드 이미지 붙여넣기(맥, 크롬환경) (1) | 2017.11.14 |
조합
2017. 11. 8. 12:58
머릿말
조합은 고등학교 때 정석으로 배울때는 이런거 배워서 뭐하나 싶지만, 나중에 알고리즘 공부를 하거나, 머신러닝 공부를 하거나, 실생활(?)에 있어서도 익혀두면 쓸모가 많은 개념이라는 생각이 듭니다. 고등학교때는 대충 넘어갔다가 나중에 다시 공부하게 되는 대표적인 수학 분야인 것 같아요.
조합의 기본
n개중 순서에 상관없이 k개를 고르는 경우의 수를 조합이라고 하고, $_{n}C_{k}$로 표현
기본 계산식은 다음과 같다.
$$_{n}C_{k} = {n\choose k} = {{n!}\over{k!(n-k)!}}$$
집합 분할하기
예시문제) 10명의 학생을 2명, 2명, 2명, 4명으로 분할하는 경우의 수는?
풀이) 10명중 2명을 순서에 상관없이 고르고 ($_{10}C_{2}$), 나머지 8명중 2명을 순서에 상관없이 고르고, ($_{8}C_{2}$), 나머지 6명중 2명을 순서에 상관없이 고르고, ($_{6}C_{2}$), 나머지 4명중 4명을 순서에 상관없이 고르고($_{4}C_{4}$).
이렇게 하면 $_{10}C_{2} \times _{8}C_{2} \times _{6}C_{2} \times _{4}C_{4} = 18900$이 답인 것 같지만,
2명씩 나눈 저 세 집단은 간에는 순서가 없다고 봐야한다.
따라서 결과를 $3!$로 나눈 3150이 답이 된다.
외부 링크
조합 계산기: http://ko.numberempire.com/combinatorialcalculator.php
n, k만 입력하면 계산해준다.
나이브 구현
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
#include <stdio.h>
int factorial(int n)
{
if (n == 0) return 1;
return n * factorial(n - 1);
}
int combination(int n, int c)
{
if (n < c) return 0;
return factorial(n) / factorial(c) / factorial(n - c);
}
int main(void)
{
printf("%d\n", combination(10, 2));
return 0;
}
|
cs |
DP구현
C(n,k) = C(n-1,k-1) + C(n-1,k)라는 성질 이용
|
1
2
3
4
5
6
7
8
9
10
11
12
|
typedef long long LL;
LL combination(int n, int k)
{
const int MAX_N = 51;
static LL dp[MAX_N][MAX_N] = { 0 };
LL& res = dp[n][k];
if (res) return res;
if (n == k || k == 0)
return res = 1;
return res = combination(n - 1, k - 1) + combination(n - 1, k);
}
|
cs |
위에건 C(n,k)하나만 구하는거고 전체를 구해두려면 다음소스 사용
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
#include <stdio.h>
int main(void)
{
const int n = 10;
long long c[n + 1][n + 1] = { 0 };
c[0][0] = 1;
for(int i=1;i<=n;i++)
{
c[i][0] = 1;
for(int j=1;j<=n;j++)
{
c[i][j] = c[i - 1][j - 1] + c[i - 1][j];
}
}
printf("%d\n", c[10][2]);
return 0;
}
|
cs |
N, K가 매우 클때 약분을 이용해서 구하는 방법
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
#include <stdio.h>
typedef long long LL;
LL combination(LL n, LL kk) {
LL C[2];
C[0] = 1;
LL r = -1;
for (LL k = 0; k <= kk + 1; ++k)
{
LL n0 = k % 2;
LL n1 = (k + 1) % 2;
C[n1] = (C[n0] * (n - k)) / (k + 1);
if (k + 1 == kk) r = C[n1];
}
return r;
}
int main(void)
{
printf("%d\n", combination(25, 12));
return 0;
}
|
cs |
반응형
'수학' 카테고리의 다른 글
| likelihood(가능도 = 우도) (0) | 2018.10.02 |
|---|---|
| MLE, 최대우도추정(Maximum Likelihood Estimation) (0) | 2018.09.27 |
| 베이즈 정리(Bayes' theorem) (0) | 2018.09.27 |
| 독립사건, 독립시행 (0) | 2018.09.27 |
| 조건부 확률 (0) | 2018.09.27 |