확률론 (11) 썸네일형 리스트형 [Python] 9246번 다트판 https://www.acmicpc.net/problem/9246 24/11/23 정규 분포의 기댓값을 구하는 문제다. 문제 접근 방식: 확률 밀도 함수(Probability density function)이 다음과 같이 정규분포 모양으로 주어진다. $$f(r) = \frac{1}{2\pi\sigma^{2}} e^{-\frac{r^{2}}{2\sigma^{2}}}$$ 이때, $r$은 다트판의 중심으로부터 떨어진 거리를 의미하며, 표준편차 $\sigma$의 값은 문제에서 주어진다. 다트판의 중심으로부터 떨어진 거리 $r$만큼의 위치에 다트가 꽃힐 확률은, 저 확률 밀도 함수에 $2\pi r$을 곱한 값이 된다. 직관적으로, 다트판의 중심으로부터 떨어진 거리 $r$만큼의 위치의 미소 면적들을 모두 모으면.. [Python] 32232번 엉엉이의 저주 탈출 https://www.acmicpc.net/problem/32232 24/09/13 맷코컵 검수 당시 검수했던 문제 중 하나이다. 문제 해석을 잘 한다면 막혔던 부분이 뚫리면서 쉽게 문제를 해결할 수 있을 것이다. 문제 접근 방식: 먼저 많은 관찰을 통해 다음과 같은 두 가지 사실을 발견해야 한다.(물론 오일러 지표를 통해 직접 유도하고 증명해도 충분하다.) 1. 엉엉이와 현철이가 지금까지 뽑은 서로 다른 점의 개수가 짝수 개라면 면이 홀수 개로 분할되고, 홀수 개라면 면이 짝수 개로 분할 된다. 2. 현철이는 자신이 이전에 뽑았던 점을 다시 뽑음으로써 홀짝성을 조정할 수 있다. 내가 이 문제에서 가장 어렵다고 느꼈던 점은 현철이와 엉엉이 모두 동일한 "확률"로 정수를 뽑는 상황, 즉, 게임에 랜덤이.. [Python] 17367번 공교육 도박 https://www.acmicpc.net/problem/17367 24/07/05 살짝 변형된 확률 DP문제이다. 기댓값의 의미를 되살리며 문제를 해결해보자. 문제 접근 방식: 모든 게임의 상태는 마지막 주사위 눈금 3개에 의해 결정되고, 주사위를 몇 번 던질 수 있는 지에 의해 결정이 된다. 따라서 4차원 확률 DP로 문제를 해결할 수 있다. 먼저 마지막 주사위 눈금 3개를 입력받으면 이에 대한 상금을 반환하는 prize(d1, d2, d3)를 구현하자. 수찬이가 받을 수 있는 상금의 기댓값이 최대가 되도록 게임을 한다는 말이 무슨 말일까? 이 말은, 현재 상태에서 수찬이가 주사위를 굴려서 상금의 기댓값이 올라간다면 주사위를 굴리고, 그렇지 않다면 현재 상태에서 얻을 수 있는 상금이 최댓값이 된다.. [Python] 13987번 Six Sides https://www.acmicpc.net/problem/13987 13987번: Six Sides Print, on a single line, a floating-point value representing the probability that the first player wins, rounded and displayed to exactly five decimal places. The value should be printed with one digit before the decimal point and five digits after the dec www.acmicpc.net 24/04/06 간단한 확률론 + 사칙 연산 문제입니다. 저의 경우는 무한 등비 급수를 활용하여 해결했습니다. 문제 접근 방.. [Python] 13249번 공의 충돌 https://www.acmicpc.net/problem/13249 13249번: 공의 충돌 무게가 모두 같고, 크기가 0인 공 N개가 일직선 위에 놓여져 있다. 오른쪽으로 굴러가는 공과 왼쪽으로 굴러가는 공이 같은 속도로 충돌하면, 속도는 변하지 않고 공의 진행 방향만 바뀌게 된다. www.acmicpc.net 23/08/24 매우 유명한 애드혹 문제에 기댓값을 섞은 문제로, 아이디어만 알면 쉽게 구현할 수 있는 문제이다. 첫 번째 접근 방식: 먼저, 이 문제의 아이디어의 원천이 되는 한 문제를 보자. https://www.acmicpc.net/problem/4307 4307번: 개미 첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스의 첫째 줄에는 막대의 길이와 개미의 수 n이 주어진다. .. [Python] 13255번 동전 뒤집기 https://www.acmicpc.net/problem/13255 13255번: 동전 뒤집기 첫째 줄에 동전의 개수 N (1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 K (1 ≤ K ≤ 50)이 주어진다. 셋째 줄에는 A[i] (1 ≤ A[i] ≤ N)가 주어진다. www.acmicpc.net 23/08/23 최근 확률 DP 문제를 계속 공부하고 있다. 이 문제 또한 확률 DP 문제로 쉽게 해결할 수 있다. 또한, 약간의 최적화를 거치면 매우 빠르게 문제를 해결할 수 있다. 첫번째 접근 방식: 첫 번째로 접근한 방식은 나이브한 $3$차원 확률 DP이다. DP테이블은 다음과 같이 정의했다. $$DP[i][j][k] = i번째 \ 뒤집는 \ 행위를 \ 수행했을 \ 때 \ j번째 \ 동전이 \ k번 .. [Python] 12046번 Not So Random (Small) / 12047번 Not So Random (Large) https://www.acmicpc.net/problem/12046 12046번: Not So Random (Small) The first line of the input gives the number of test cases, T. T test cases follow; each consists of one line with six integers N, X, K, A, B, and C. Respectively, these denote the number of machines, the initial input, the fixed number with which www.acmicpc.net https://www.acmicpc.net/problem/12047 12047번: Not So Random (Large.. [Python] 7670번 Game Dice https://www.acmicpc.net/problem/7670 7670번: Game Dice In the game of Dungeons & Dragons, players often roll multi-sided dice to generate random numbers which determine the outcome of actions in the game. These dice come in various flavors and shapes, ranging from a 4-sided tetrahedron to a 20-sided isocahedro www.acmicpc.net 23/08/21 최근 확률 DP문제를 계속 공부하고 있다. 복습하고자 글로 남긴다. 문제 접근 방식: DP로 접근했으며, DP테.. 이전 1 2 다음
