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 를 양수로 만들어주는 함수..
Combination 조합 C++ 로 구현하기
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! 구한것에서 3!..
이 문제는 영어로 이루어져 있으니 간략하게 한국어로 설명하겟다. 요뜨가 사다리를 타고 내려오고 있다. 사다리에서는 지렁이가 a[i]개씩 살고 있고 b[i]일이 지나면 그 가로 사다리는 갉아 먹혀서 없어진다. 요뜨는 사다리의 피해를 막기 위해 내려오면서 살충제를 뿌리려고 한다. 각 높이 에서는 최대 한번만 뿌릴 수 있다. 이때 갉아 먹히는 가로 사다리의 개수를 구하고, 무엇인지를 출력한다. 이런 문제다. 그래서 풀이는? 이 문제는 버블 소트로 풀수가 있다. 그래서 자세한 풀이는?? n이 매우 작은 탓에 안심하고 풀 수 가 있다. 그래서 어떻게 푸냐고?? 모두 함께 꿀다이아 문제를 풀어보도록 하자. 그래... 그러면 코드나 줘 코드를 첨부하겠다. #include using namespace std; int ..