C++ 로 조합을 구현하는 방법을 알려주겠다. nCr = n-1Cr-1 + n-1Cr 라는 식을 이용하여 O(nr) 만에 구하는 방법도 있지만, n,r 이 10만정도 된다면 메모리도 시간도 펑펑 터질 것이다. 그래서 이번 글에는 조합을 빨리 구하는 방법을 알려주겠다. (와아앙아앙아아 짝짝짝짝) 순서는 STL내장함수인 next_permutation 을 사용해서 출력하면된다. (이 글은 나중에 추가될 예정이다) 조합을 구할려면 일단 식을 보자 조합 식 이제 이 식을 직접 구하면 되는데 n! 을 구하고 r! 을 구하려고 하면 mod 값에 나눠버리는 경우가 있어서 매우 까다롭다. 예를 들어보자. mod = 7, 구하려고 하는 수는 5C3 이다. 그러면 5! 을 구하고 3! 을 구하고 2! 을 구하고 5! 구한것..
5분안에 마스터 하는것이기 때문에 아주 간결하고 핵심 요약만 말할것이다. 준비물 : hash에 대한 기본 지식, 이분탐색에 대한 기본 지식 1. 이분탐색을 돌린다. 길이가 i인 문자열이 반복으로 나온다면 그 아래는 볼 필요가 없다. 즉 이분탐색이 가능하다. 2. hash테이블을 이용하여 같은 문자열이 있는지 검사한다. hash테이블을 써서 길이 i인 것들중 같은것이 있는지 체크해준다. (hash에 대한 기본지식은 알고 있기 바란다.) 시간 복잡도는 O(NlogN) 이다 아래의 코드는 3033 번 문제이다. 바로 코드를 보겠다. #include using namespace std; const int mod = 100003; int f(long long x) { // x % mod 를 양수로 만들어주는 함수..
- Total
- Today
- Yesterday
- 앳코더
- AtCoder
- 간단한 풀이
- BOJ
- 비요뜨
- 비요뜨 존맛
- 세그먼트 트리
- gunwookim
- 김춘배
- Rabin-Karp
- 냄새 싫어
- DP
- combination
- 정렬
- 하이퍼
- 스택
- hyper
- 쿼리
- codeforces
- Constructive
- 알고리즘 문제 풀이
- 누적 합
- 1909
- 수열과 쿼리
- ABC
- PS
- Offline Dynamic Connectivity
- 오일러 경로
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 | 29 | 30 | 31 |