문제
마르코프 체인은 상태 사이를 무작위로 이동하며, 다음 상태는 현재 상태에만 의존합니다. transition[i][j]는 상태 i에서 상태 j로 이동할 확률이므로 각 행의 합은 1입니다.
p가 지금 각 상태에 있을 확률이라면, 한 단계 후의 분포는 다음과 같습니다.
p_next[j] = i에 대한 p[i] × transition[i][j]의 합 Σ
markov_distribution(transition, start, steps)를 구현하고 이 업데이트를 steps번 적용하세요.
입력
transition: 각 행의 합이 1인 n × n 행렬.
start: 시작 분포 (합이 1인 n개의 값).
steps: 진행할 단계 수.
출력
steps 단계 후의 분포를 반환합니다.
제약 조건
1 ≤ n ≤ 50, 0 ≤ steps ≤ 1,000
0 ≤ 각 확률 ≤ 1
예시
입력:
start = [1.0, 0.0]
steps = 2
transition = [
[0.9, 0.1],
[0.5, 0.5]
]
예상 출력:
expected = [0.86, 0.14]입력:
std::vector<double> start = {1.0, 0.0};
long long steps = 2;
std::vector<std::vector<double>> transition = {
{0.9, 0.1},
{0.5, 0.5}
};
예상 출력:
std::vector<double> expected = {0.86, 0.14};입력:
double[] start = new double[] {1.0, 0.0};
long steps = 2;
double[][] transition = new double[][] {
new double[] {0.9, 0.1},
new double[] {0.5, 0.5}
};
예상 출력:
double[] expected = new double[] {0.86, 0.14};설명
맑은 날 (0)과 비 오는 날 (1)을 생각하고 맑은 날에서 시작합니다. 한 단계 후: [0.9, 0.1]. 두 단계 후: 맑음 = 0.9 × 0.9 + 0.1 × 0.5 = 0.86, 비 = 0.9 × 0.1 + 0.1 × 0.5 = 0.14.
입력:
start = [0.25, 0.75]
steps = 3
transition = [
[0.0, 1.0],
[1.0, 0.0]
]
예상 출력:
expected = [0.75, 0.25]입력:
std::vector<double> start = {0.25, 0.75};
long long steps = 3;
std::vector<std::vector<double>> transition = {
{0.0, 1.0},
{1.0, 0.0}
};
예상 출력:
std::vector<double> expected = {0.75, 0.25};입력:
double[] start = new double[] {0.25, 0.75};
long steps = 3;
double[][] transition = new double[][] {
new double[] {0.0, 1.0},
new double[] {1.0, 0.0}
};
예상 출력:
double[] expected = new double[] {0.75, 0.25};설명
이 체인은 항상 상태를 바꾸므로 매 단계 두 확률이 서로 바뀝니다. 3번 바뀐 뒤: [0.75, 0.25].
접근 방법
먼저 스스로 풀어 본 뒤 힌트를 하나씩 열어 보세요.
힌트 1
다음 분포는 현재 분포의 확률 질량을 모든 전이로 흘려보내서 구합니다.
힌트 2
한 번에 한 단계씩 반복하는 행렬-벡터 곱이라고 생각하세요.
힌트 3
steps가 0이면 시작 분포를 그대로 반환해야 합니다.
예상 복잡도
시간 O(steps * n^2), 추가 공간 O(n)
참고 자료
이 문제는 CodeUtility에 맞게 수정되었습니다. 위의 설명과 제한 조건을 따르세요.