#1521 랜덤 소트(dynamic programming)

이번 문제는 꽤 재미있는 주제입니다.

 

인공지능 마르코프 체인을 이야기하다보면, 기대값을 계산하는 부분이 있습니다.  이 부분을 잘 활용하고, 그리고 잦은 중복 호출이 발생하니 동적 계획법도 이용해야 합니다.

 

문제는 아래와 같습니다.

https://www.acmicpc.net/problem/1521

1521번: 랜덤 소트

 

마르코프 프로세스에 의하면 우리가 현재 상태($S_c$)의 기대값은 다음과 같이 구할 수 있습니다.

 

$$E(S_c)=\sum _p{P}_{c,p}\cdot E(S_p)$$

 

위의 식을 염두에 두고 프로그램을 해주시면 됩니다.

 

동적 계획법은 일반적으로 메모리를 할당하고, 그 안에서 처리하고 있지만, 제 경우에는 그냥 해시맵(Hash Map)을 사용했습니다.  파이썬을 이용했기 때문에 딕셔너리(dictionary) 자료구조를 이용했고요.

 

일단 주어진 수열을 정렬하고, 그 수열인 경우에 대해서는 기대값을 0으로 설정했습니다.

 

$$d_{sorted(v)}=0.0$$

 

그리고 자기 자신으로 가는 경우도 있겠죠.  $v_i\le v_j$인 경우에는 스왑횟수가 늘지 않고 자기 자신으로 갑니다.  이런 경우를 포함해서 기대값을 계산하셔야 합니다.  왜냐하면 무작위로 i, j를 선택하고, $v_i>v_j$인 경우에만 선택이 바뀌니까요.  그것을 염두에 둔다면 동적계획법을 적절하게 이용해서 현재 상태의 기대값을 계산할 수 있습니다.

 

메모리 제한이 128MB이므로 모든 상태의 경우를 생각하더라도 8! 자체가 그렇게 크지 않기 때문에 충분합니다.  그리고 실제 역순으로 되어 있다고 해도 실제 경우의 수가 8!에 해당하지는 않습니다.

 

4321의 경우를 보더라도 나올 수 있는 경우의 수는 3421, 2341, 1324, ..., 1234 형태가 되고 그 수가 8!만큼 많지는 않습니다.  그러므로 메모리 걱정은 안 하셔도 괜찮습니다.