복습노트 복습노트

probability dp(확률 dp) 확률과 기댓값은 다르다. ex) 1. 정육면체 주사위를 던질 때 1이 나올 확률? 1/6 2. 정육면체 주사위를 던질 때 1이 나올 때까지 던지는 횟수의 기댓값은? = 6 1번 던졌을 때 1이 나올 확률(1/6) + 2번 던졌을 때 1이 나올 확률(5/6(1이 처음에 안나올 확률) * 1/6(1이 그다음에 나올 확률) * 2) + 3번 던졌을 때 1이 나올 확률 (5/6(1이 처음에 안나올 확률) * 5/6(1이 두번째 던졌을때도 안나올 확률) * 1/6(1이 나올 확률) * 3) + ...... 다음과 같은 식으로 표현할 수 있다. 3. 정육면제 주사위를 던질 때 나온 수의 기댓값은? (1/6 * 1) + (1/6 * 2) + (1/6 * 3) + (1/6 * 4..

소수 1. 모든 자연수는 소인수들의 곱으로 표현 가능 2. 소수는 무한하다 (p1 * p2 * p3 ....* pn + 1) 소수인지 알아보는 방법 n이 합성수라고 가정하면, a * b = n 을 만족하는 (min(a,b) > 1) 인 (a, b)가 존재하므로 min(a, b) HTML 삽입 미리보기할 수 없는 소스 에라토스테네스의 체를 이용 시간 복잡도 : (O(nloglogn)) / 공간 복잡도 : O(n) 앞에서 부터 소수의 배수가 되는 수들을 전부 지워 가가는 것 HTML 삽입 미리보기할 수 없는 소스 최대공약수를 구해주는 유클리드 알고리즘 HTML 삽입 미리보기할 수 없는 소스 gcd(a, b)를 구하는 과정에서 max(a, b)가 절반이하가 되므로 시간복잡도는 O(log n) " 문제 크기가 ..