다단계 합병에서 런의 분포

 

 

다단계 합병의 개념을 알았다면, 런의 분포를 나타낸 위의 표를 이해할 수 있어야 한다.

더 나아가 다음의 합병은 어떻게 되는지를 스스로 적어볼 수 있어야 한다.

 

들어가기에 앞서서 개념을 잘 정리했는지 알아보기 위해 몇가지를 점검해야 한다.

1. 어떤 파일에 합병할 것인지

2. 합병된 파일에는 몇개의 런이 합병된 것인지

3. 합병 결과, 파일들의 런의 개수는 어떻게 되는 것인지

4. 최종 위치는 어느 파일에 합병되는 것인지

 

기본적으로 다단계 합병에서는 0보다 큰 런의 개수 중, 가장 작은 런의 개수가 있는 것을 눈여겨봐야 한다.

런의 개수가 0보다 큰 파일 중, 가장 작은 런의 개수를 가진 파일의 런의 개수를 0으로 만들어줘야 하는것이 목표다.

 

 

파일 3의 내부 정렬 단계가 2인 것이 가장 작은 런의 개수이다.

그리고 이제는 파일 1,2와 4를 구분해서 확인해야 한다.

 

 

파일1의 런의 개수는 4, 파일2의 런의 개수는 3이다. 

파일3의 런의 개수인 2보다 많은 개수의 런을 가지고 있다.

이와는 반대로 파일4의 런의 개수는 0이다.

 

 

이제는

런의 개수가 0보다 큰 파일 중,

가장 작은 런의 개수를 가진 파일의 런의 개수를 0으로 만들어야 하기 때문에

파일3의 런의 개수인 2가 가장 작은 런의 개수이기 때문에, 2를 기준으로 생각해야 한다.

파일1과 파일2의 런의 개수에서 -2를 해줘야 하고

파일4에서는 런의 개수  +2를 해줘야 한다. 즉, 0 + 2

물론, 파일3에서의 런의 개수에서 -2도 해줘야 한다.

그 결과는 다음과 같다.

 

합병1의 결과

 

합병1을 실행한 결과 0보다 큰 런의 개수 중에, 가장 작은 런의 개수가 있는 것은 파일 2, 런의 개수는 1이다.

그리고 

파일1의 런의 개수는 2, 파일4의 런의 개수는 2이다.

파일2의 런의 개수인 1보다 많은 개수의 런을 가지고 있다.

이와는 반대로 파일3의 런의 개수는 0이다.

 

그리고 과정을 다시 반복한다.

런의 개수가 0보다 큰 파일 중,

가장 작은 런의 개수를 가진 파일의 런의 개수를 0으로 만들어야 하기 때문에

합병 1에서 이제는 가장 작은 런의 개수를 갖는 파일2의 런의 개수인 1를 기준으로,

파일1과 파일4의 런의 개수에서 -1를 해줘야 하고

파일3에서는 런의 개수  +1를 해줘야 한다. 즉, 0 + 1

물론, 파일2에서의 런의 개수에서 -1 해줘야 한다.

그 결과는 다음과 같다.

 

합병 2의 결과

 

마지막으로 살펴보면 이제는 파일2를 제외한 모든 파일의 개수가 1로 동일하다.

이제는 런을 옮길 수 있는 비어있는 파일이 파일2밖에 없기 때문에 파일2로 이동해야 한다.

 

이제는 파일2에 합병하기 위해

파일1과 파일3, 파일4의 런의 개수에서 -1를 해줘야 하고

파일2에서는 런의 개수  +1를 해줘야 한다. 즉, 0 + 1

 

그 결과는 다음과 같다.

 

합병 3의 결과

 

그러면 이와는 반대로, 합병3에서부터 내부 정렬 단계까지 런 어떻게 분포하는지도 검토할 수 있어야 한다.

이것은 위의 방법과는 반대로 찾아가야 한다.

가장 마지막 합병 단계의 파일중 런의 개수가 1인 것을 찾아보면 파일2인 것을 확인할 수 있다.

 

 

이제는 런의 개수가 1인 것을 기준으로 생각한다.

런의 개수가 0인 파일1과 파일3, 파일4에 +1을 해주고,

런의 개수가 1인 파일2에는 -1을 해준다.

 

 

합병2에서 합병1로 갈때,

확인해야 할 것은 런의 개수가 0인 파일의 위치이다.

합병1에서 런의 개수가 0인 곳은 파일3이다. [그림1]

 

[그림1]

 

그리고 다음 단계인 합병2에서의 파일3의 런의 개수를 확인한다. [그림2]

 

[그림2]

 

파일1과 파일2, 파일4는 합병2에서의 파일3의 위치에 있는 런의 개수를 더해준다. [그림3], [그림4]

 

[그림4]

 

일반화 한다면, 합병 단계가 낮은 곳(예시에서 합병1)에서 런이 0이 되는 곳의 파일을 찾아주고,

그 파일의 다음 단계(합병2)의 런의 개수(예시에서 1)를 확인한다.

그리고 확인한 런의 개수(예시에서 1)를

합병 단계가 낮은 곳(예시에서 합병1)에서 런이 0이 아닌 파일들에 각각 더해준다.

그리고 최종 단계를 검토하기 위해서 이 과정을 반복한다.

 

 

다음 게시글에서는 파일의 개수가 더 많고, 합병 단계가 더 많은 다단계 합병 문제를 풀면서 확인해보자.