[알고리즘] Two-Way Optimal Merge Patterns

문제

2개 이상의 정렬된 파일들을 하나의 파일로 합병한다. 이 때 비교 횟수를 최소로 한다.

⇒ 비교 횟수 최소 : Greedy 방식

해결 방안 찾기

• 앞에서 부터, 혹은 뒤에서 부터의 방식은 무조건 맞지 않다.
• 그 때, 그 때 원소의 갯수를 비교하여 가장 적은 원소를 가진 배열을 합친다 (Greedy)
• 예시 ) x1 ~ x4 : 길이가 다른 배열들. 이미 정렬이 된 상태. ⇒ 배열의 원소 갯수가 작은 배열을 먼저 합병한다.

예제

• 배열을 원소의 크기대로 오름차순 정렬을 한다
• 원소가 제일 적은 배열끼리 합병을 진행한다
• 배열이 합쳐지며 길이가 달라졌을 때 새롭게 sort를 한 후 합병을 진행한다

• 

예제 : 트리 모형

• 예제의 결과를 뒤집어 만들어진 트리 형태의 노드
• 합쳐진 배열의 원소 합을 모두 더하여도 되지만, 기존의 배열이 몇 번 읽혔는지로도 계산을 할 수 있다 (원소 수 * 깊이)
• 최상위에 존재하는 95 노드를 root라고 한다

5*3 = 5개 원소가 3번 읽혔다는 의미 (깊이 3)

10*3 = 10개 원소가 3번 읽혔다는 의미 *깊이 3)

⇒ 깊이가 깊을수록 많이 비교된다

시간 복잡도

주어진 m개의 파일 F={x1, x2, x3, x4, … , xm} ⇒ O(m^2)