pizzaroot

2023년 04월 12일 확률변수 \(X\)를 같은 면이 세 번 연속으로 나올 때까지 동전을 던진 횟수라고 할 때, \(P(X\leq9)\)의 값을 구하시오. 상태 \(i\)가 현재 연속 스트릭을 나타내는 마르코프 체인을 정의하면 상태공간은 \(\{1, 2, 3\}\)이 되고, 전이행렬 \(\mathbf P\)는 다음과 같다. \(\displaystyle\mathbf P=\begin{bmatrix}\frac{1}{2} & \frac{1}{2} & 0 \\ \frac{1}{2} & 0 & \frac{1}{2} \\ 0 & 0 & 1 \end{bmatrix} \) 구하려는 값은 \(\displaystyle\mathrm P_{13}^{(8)}=\frac{201}{256}\)이다.

보호되어 있는 글입니다.

먼저 \(N\)이 \(10\,000\)까지 들어오는 것을 보아서 각 선풍기마다 시간 간격만큼씩 더해가며 시뮬레이션 하는 풀이는 통과하기 힘들것이라는 짐작이 벌써 든다. 각 선풍기 마다 \(O(1)\)만에 가격을 구하는 풀이도 존재할 것 같지만, 일단은 쉽게 구현한다는 생각이 들어서 이분탐색을 떠올리게 된다. 대충 구상을 했으니 이제 코드를 짜기 시작한다. 라고 생각하고 코드를 짜다보니 시간이 이미 주어지므로 이분탐색이 전혀 필요 없다는 사실을 깨닫게 된다. 그렇다면 총 몇번을 추가 결제 해야 하는가를 구할 때 \(\displaystyle\left\lfloor\frac{Q}{K}\right\rfloor\)번인지 \(\displaystyle\left\lceil\frac{Q}{K}\right\rceil\)번인..

시간복잡도의 엄밀한 수학적 정의는 나도 사실 정확하게 모른다. 하지만 알고리즘에서 시간복잡도를 분석하는 것은 매우 중요하다. 합의 합 문제를 통해 시간복잡도를 체감해보자. 문제에서 주어진 식을 의미 그대로 구한다면 코드를 다음과 같이 구현할 수 있다. #include typedef long long ll; int main() { int T; scanf("%d", &T); while (T--) { int N; scanf("%d", &N); ll ans = 0; for (int k = 1; k

이 시리즈는 세종대학교 소프트웨어학과의 전공필수 과목인 자료구조및실습에 도움을 주기 위해 만들어졌다. 이 과목의 특징은 C언어만 사용가능하다는 점이다. 따라서 이 시리즈도 C언어로만 진행된다. 준비물은 백준 계정과 코드포스 계정이 필요하다. 그렇다면 몸풀기로 다음 문제들을 풀어보자. 문제 난이도 태그 인공지능 시계 Bronze IV 수학 나이순 정렬 Silver V 정렬, 문자열, 구조체 합의 합 Silver IV 수학 3문제 모두 풀었다면 준비가 된 것 같다.

D번: 중요한 #include #define INF 0x7fffffff #define SIZE 100001 using namespace std; int seg[SIZE > 1; i > 0; i >>= 1) seg[i][id] = min(seg[i >= 1) { if (l & 1) ret = min(ret, seg[l++][id]); if (~r & 1) ret = min(ret, seg[r--][id]); } return ret; } int pos(int val, int right) { right += SIZE; while (seg[right][0] > val) right = (right - 1) >> 1; while (right k; int v, w; ci..

\(O(n^2)\) #include #include #include int main() { int n, ans = 0; scanf("%d", &n); int *arr = (int *)malloc(n * sizeof(int)); assert(arr != NULL); for (int i = 0; i < n; i++) scanf("%d", arr + i); for (int i = 0; i < n; i++) { int good = 1; for (int j = 0; j < i; j++) { if (arr[j] == arr[i]) good = 0; } ans += good; } printf("%d\n", ans); return 0; } \(O(n\log n)\) #include #include #include vo..

모두 수고하셨습니다!

경과 타임라인 문제 킬 어시스트 10분 [B] Commemorative Dice pizzaroot 적을 처치했습니다! 32분 [C] Dessert Café WA 38분 WA 연속 킬 차단! 48분 [E] Imprecise Computer pizzaroot 더블 킬! 58분 [C] Dessert Café WA 71분 WA 78분 WA 제압 되었습니다! 98분 [J] Switches WA 108분 [C] Dessert Café wlsth1004100 3juhwan 아군이 적을 처치했습니다! 116분 [J] Switches pizzaroot 트리플 킬! 160분 [G] Mobile Robot WA 174분 pizzaroot 3juhwan / wlsth1004100 쿼드라 킬! 풀이 [B] Commemorati..