리버소트 timer 10s memory 1024MB

참고: "Reversort"와 "Reversort Engineering" 문제의 설명은 마지막 문단을 제외하면 주요 부분이 동일하다. 그 외에는 두 문제를 서로 독립적으로 풀 수 있다.

Reversort는 서로 다른 정수로 이루어진 리스트를 오름차순으로 정렬하는 알고리즘이다. 이 알고리즘은 "Reverse" 연산을 기반으로 한다. 이 연산을 한 번 적용하면 리스트의 어떤 연속 구간(contiguous part)의 순서를 뒤집는다.

알고리즘의 의사코드는 다음과 같다:

Reversort(L):
  for i := 1 to length(L) - 1
    j := position with the minimum value in L between i and length(L), inclusive
    Reverse(L[i..j])

i-1번의 반복이 끝나면, 리스트의 1,\;2,\;\dots,\;i-1번째 위치에는 L에서 가장 작은 i-1개의 원소가 오름차순으로 들어 있다. i번째 반복에서는, i번째 위치부터 현재 i번째로 작은 원소가 있는 위치까지의 부분 리스트를 뒤집는다. 그 결과 i번째로 작은 원소가 i번째 위치로 오게 된다.

예를 들어 원소가 4개인 리스트라면 알고리즘은 3번 반복을 수행한다. L = [4, 2, 1, 3]을 처리하는 과정은 다음과 같다:

1. i = 1,~ j = 3 \longrightarrow L = [1, 2, 4, 3]
2. i = 2,~ j = 2 \longrightarrow L = [1, 2, 4, 3]
3. i = 3,~ j = 4 \longrightarrow L = [1, 2, 3, 4]

우리의 아키텍처에서 알고리즘을 실행할 때 가장 비용이 큰 부분은 Reverse 연산이다. 따라서 각 반복의 비용은 Reverse에 넘기는 부분 리스트의 길이, 즉 j - i + 1로 정의한다. 전체 알고리즘의 비용은 각 반복의 비용을 모두 더한 값이다.

위 예시에서 각 반복의 비용은 순서대로 3, 1, 2이므로 총 비용은 6이다.

초기 리스트가 주어졌을 때, 그 리스트에 Reversort를 적용하는 데 드는 비용을 구하라.