[알고리즘-공부] 3. 분할 정복 알고리즘(1) - 합병정렬

분할 정복(Divide-and-Conquer) 알고리즘 이란 주어진 문제의 입력을 분할하여 문제를 해결(정복)하는 방식의 알고리즘이다. 여기서 분할된 입력에 대한 문제를 부분문제라고 하고, 부분문제의 해를 부분해라고 한다. 부분문제는 더 이상 분할 할 수 없을 때까지 계속 분할한다.

입력의 크기가 n일때, 총 몇번을 분할하여야 더 이상 분할할 수 없는 크기인 1이 될까?

분할 한 총 횟수 = k로 두고, 1번 분할 후 각각의 입력 크기 = 라고 한다면 입력크기는 씩 분할됨을 알 수 있다.

따라서 이라는 식을 세울 수 있고, 결국 분할 총 횟수 임을 알 수 있다.

 

분할 정복 알고리즘은 분할, 정복, 결합의 과정을 거친다. 분할 정복 알고리즘에서 가장 중요한 것은 '문제를 나누는 것'이다. 문제를 제대로 나누기만 한다면 정복은 겁나 쉬워지기 때문이다. 그런데 분할 정복 알고리즘은 문제를 잘게 쪼개면서 얻어진 알고리즘의 효율성을 재귀 호출 비용으로 까먹는 단점이 있다. 

 

 

3.1 합병 정렬(Merge Sort) == 병합 정렬

합병정렬은 입력이 2개의 부분문제로 분할되고, 부분문제의 크기다 1/2로 감소하는 분할 정복 알고리즘이다. 즉, n개의 숫자들을 n/2개씩 2개의 부분문제로 분할하고, 각각의 부분문제를 재귀적으로 합병정렬한 후, 2개의 정렬된 부분을 합병하여 정렬(정복)한다. 즉 나누고 합치라는 소리다.

(1) 정렬할 데이터 집합을 반으로 나눈다.

(2) 나누어진 하위 데이터 집합의 크기가 2이상이면 이 하위 데이터 집합에 대해 (1)번을 반복한다.

(3) 원래 같은 집합에서 나위어져 나온 하위 데이터 집합 둘을 병합하여 하나의 데이터 집합으로 만든다. 단 병합할 때 데이터 집합의 원소는 순서에 맞춰 정렬한다.

(4) 데이터 집합이 다시 하나가 될때까지 (3)번을 반복한다.

뭔소린지 모르겠다면 예제를 같이 풀어보자.

 

ex) 5,1,6,4,8,3,7,9,2 데이터 집합을 병합정렬로 정렬해 보자

(1) 원래의 데이터 집합을 반으로 나눈다. 더이상 쪼갤게 없을 때까지 위에 (1),(2)번 반복!  (회색은 중간에 위치한 기준점임)

(2) 분할이 끝나면 (3),(4)번을 이용해정복한다. 하위 데이터 집합들이 다시 하나가 됐을 때 알고리즘을 종료한다.

 

끝!!

근데 두 데이터 집합을 하나로 합칠때 정렬은 어떻게 함??

(1) 두 데이터 집합을 합한 것 만큼의 비어있는 집합을 마련한다.

(2) 두 데이터 집합의 첫 번째 요소들을 비교하여 작은 요소를 새 데이터 집합에 추가한다. 그리고 새 데이터 집합에 추가된 요소는 원래의 데이터 집합에서 삭제한다.

(3) 양쪽 데이터 집합이 빌 때까지 (2)번의 과정을 반복한다.

 

뭔소린지 못알아 먹겠쥬? 그림으로 봅시다

밑에 그림은 두 데이터 집합 A와 B가 있고, 이 둘을 합한 크기와 같은 크기를 갖는 빈 데이터 집합 C가 있다. A, B를 병합해 C에 채워보자

먼저 A와 B의 첫번째 요소끼리 비교를 수행한다. 1과 2중 A의 1이 더 작으니 C에 1을 입력하고 A의 1을 삭제한다.

그 다음으로는 A의 4와 B의 2를 비교한다. 2가 작으니 2를 B에서 삭제하고 C에 입력한다.

이런식으로 데이터 집합 A와 B에 남아있는 첫 번째 요소를 비교하고 C에 옮겨 넣는 일을 계속하다 보면 B에 9하나만 남게된다. A는 남아 있지 않으므로 패스, 9를 C에 입력하고 B에서 삭제한다. 이로싸 A와 B가 모두 비게 되고 C에는 정렬된 데이터 집합이 생긴다.

 

 코드로 생각해 보자

#쉽게 설명한 병합 정렬 #입력 : 리스트a #출력 : 정렬된 새 리스트 #종료조건 : 정렬할 리스트의 자료 개수가 한개 이하이면 정렬할 필요 없음 def merge_sort(a): n = len(a) if n<= 1: return a #그룹을 나누어 각각 병합 정렬을 호출하는 과정 mid = n // 2 g1 = merge_sort(a[:mid]) # 재귀 호출로 첫 번째 그룹을 정렬 g2 = merge_sort(a[mid:]) # 재귀 호출로 두 번째 그룹을 정렬 #두 그룹을 하나로 병합 result=[] while g1 and g2: #두 그룹에 모두 자료가 남아있는 동안 반복 if g1[0] < g2[0]: # 두 그룹의 맨 앞자리 값을 비교 #g1의 값이 더 작으면 그 값을 빼내어 결과로 추가 result.append(g1.pop(0)) else: #g2의 값이 더 작으면 그 값을 빼내어 결과로 추가 result.append(g2.pop(0)) #아직 남아있는 자료들을 결과에 추가 #g1과 g2중 이미 빈 것은 while을 바로 지나감 while g1: result.append(g1.pop(0)) while g2: result.append(g2.pop(0)) return result d=[5,1,6,4,8,3,7,9,2] print(merge_sort(d))

값 : [1, 2, 3, 4, 5, 6, 7, 8, 9]

 

출처 : [알기쉬운 알고리즘-양성봉] 전공책입니다.  [모두의 알고리즘 파이썬]책을 참고하여 코드를 넣었습니다.