반응형 마르코프1 #1521 랜덤 소트(dynamic programming) 이번 문제는 꽤 재미있는 주제입니다. 인공지능 마르코프 체인을 이야기하다보면, 기대값을 계산하는 부분이 있습니다. 이 부분을 잘 활용하고, 그리고 잦은 중복 호출이 발생하니 동적 계획법도 이용해야 합니다. 문제는 아래와 같습니다. https://www.acmicpc.net/problem/1521 1521번: 랜덤 소트 첫째 줄에 순열의 크기 N이 주어진다. 둘째 줄에 순열에 들어있는 수 N개가 주어진다. 이 수는 모두 1보다 크거나 같고, N보나 작거나 같으며, 같은 수는 2번 이상 주어지지 않는다. 또, N은 8보다 www.acmicpc.net 마르코프 프로세스에 의하면 우리가 현재 상태(\(S_c\))의 기대값은 다음과 같이 구할 수 있습니다. \[ E(S_c) = \sum_{p} P_{c, p} \.. 2022. 8. 31. 이전 1 다음 728x90