데이터과학 유망주의 매일 글쓰기 — 80일차
분할 정복(Divide and Conquer)
# 분할 정복, #Divide and Conquer, # 병합정렬
오늘 한일:
오늘은 자가 점검의 시간이었다. Big O 표기법에 대해서 대부분 다루었는데, 내가 이 것을 제대로 리뷰하지 못해 애를 좀 먹었다. 각 프로그램이 얼마나 시간복잡도를 가지는지, 찾아가면서 답을 했다. 덕분에, 단시간에 빡세게 공부해서 훨씬 더 개념을 잘 이해하게되었다.
시험 문제를 풀면서, 프로그램을 부분 부분으로 나누어서 보아야 정확히 몇 번의 연산이 이루어지는지 알 수 있었다. 사실 이번 과정에 들어서 문제를 부분 부분으로 나누어서 보는 연습을 계속했다. 그렇게 해서 생각난 것이 전날 배웠던 분할정복(Divide and Conquer)이라는 개념이었다. 문제를 가장 작은 단위까지 나누어 쪼개 풀고, 모든 답을 합치는 방식이다. 이러한 분할정복 개념에 가장 기본이 되는 알고리즘이 병합정렬이라는 것이다.
분할 정복(Divide and Conquer)
분할정복(Divide and Conquer)이란 아래 3개의 과정에 따라 문제를 해결하는 방법이다.
1. 나누기: 문제를 비슷한 타입의 여러개의 단위 문제로 나누기
2. 정복: 재귀를 활용하여 단위 문제를 해결
3. 병합: 적절하게 결과를 병합하기
병합정렬(Merge Sort)
분할 정복의 대표적인 방법에는 병합정렬(Merge Sort)이 있는데 이를 조금 더 효과적으로 설명하기 위해, 아래와 같은 배열을 가정했다.
- [7, 6, 1, 5, 4, 3]
작동 순서:
1. 위 배열을 2개로 나눈다.
> [7, 6, 1], [5, 4, 3]
2. 다시 위 배열들을 계속해서 더 이상 나눌 수 없을 때까지 분리한다.
> [7, 6], [1], [5, 4], [3]
> [7], [6], [1], [5], [4], [3]
3. 마지막으로 정렬된 상태로 각 아이템을 병합한다.
> [6, 7], [1], [4, 5], [3]
> [1, 6, 7], [3, 4, 5]
> [1, 3, 4, 5, 6, 7]
이를 표현하자면 아래와 같은 코드가 될 수 있다.
# 병합 정렬 코드 예제 (참조: [1])
# 배열의 2 하위 배열을 병합하는 형태
# 첫 배열은 arr[l..m]
# 두 번째 배열은 arr[m+1..r]
def merge(arr, l, m, r):
n1 = m - l + 1
n2 = r- m
# 두 개의 일시적 배열 생성
L = [0] * (n1)
R = [0] * (n2)
# L[] 과 R[]의 배열에 데이터 카피
for i in range(0 , n1):
L[i] = arr[l + i]
for j in range(0 , n2):
R[j] = arr[m + 1 + j]
# 일시적 배열을 arr[l..r]로 병합하기
i = 0 # 첫 하위배열의 초기 인덱스값
j = 0 # 두 번째 하위배열의 초기 인덱스값
k = l # 병합된 배열의 초기 인덱스값
# 하위 배열 1과 2를 나누기
while i < n1 and j < n2 :
if L[i] <= R[j]:
arr[k] = L[i]
i += 1
else:
arr[k] = R[j]
j += 1
k += 1
# L[]의 나머지 아이템을 복사하기
while i < n1:
arr[k] = L[i]
i += 1
k += 1
# R[]의 나머지 아이템을 복사하기
while j < n2:
arr[k] = R[j]
j += 1
k += 1
# l은 정렬될 배열의 왼쪽 인덱스, r은 오른쪽 인덱스를 나타냄
def mergeSort(arr,l,r):
if l < r:
# (l+r)//2와 같으나, l과 r의 인덱스 경계를 맞추기 위함
m = (l+(r-1))//2
# 첫 하위 배열과 두 번째 하위 배열을 정렬 및 병합하기
mergeSort(arr, l, m)
mergeSort(arr, m+1, r)
merge(arr, l, m, r)
return arr
# 위 코드를 실행
arr = [12, 11, 13, 5, 6, 7]
n = len(arr)
mergeSort(arr,0,n-1)>> [5, 6, 7, 11, 12, 13]
앞으로 할일:
분할정복이라는 개념은 말에서도 그 의미를 유추할 수 있을 정도로 직관적이다. 역시 모든 문제는 작게 쪼개서 풀어야 좋다. 그게 조금 시간이 걸리더라도, 가장 효율적으로 문제를 풀 수 있는 방법인 경우가 많기 때문이다.
삶의 복잡한 문제들도, 하나 하나 단계적으로 풀어야 하듯이, 무언가를 배울 때 푸는 문제들도 다르지 않다는 것을 많이 느꼈다. “돌다리도 두드려보고 건너라”, “급할수록 돌아가라"는 말이 있듯이, 모든 문제는 침착하게 작은 부분으로 나누어, 어디서 부터 시작해야 하는지 분석후 파악하여 해결하는 것이 가장 효율적이다. 오늘도 시험을 보면서 예상치 못한 부분에서 막혀 어떻게 해야 할지 모르는 경우도 있었지만, 그럴 때마다 차분히 시간을 가지고 내가 무엇부터 할 수 있는지 보았다. 그렇게 문제를 들여다보고, 부분 부분 나누어보니, 생각보다 어렵지 않았다. 나무보다 숲을 보라고 하지만, 문제를 해결할 때는 많은 경우 숲을 못 본다면, 눈에 들어오는 나무부터 유심히 보면 실마리를 얻을 수 있는 경우가 많다.
앞으로도 내가 모르거나 감이 안 잡히는 문제에 대해서는 차분히 부분 부분을 들여다 보면서 더 작은 단위의 문제로 나눌 수 있는지 보아야겠다는 생각을 했다. 프로그래밍 뿐만 아니라 삶의 문제를 해결하는데 있어서도 많은 가르침을 주는 이번 과정에 매우 감사하다. 다른 수강생들도 앞으로 자신에게 닥친 문제를 해결할 때 이런 태도를 갖기를 바란다.
모두에게 다음 주 마지막 스프린트까지 힘차게 달리자고 말하고 싶다. 다들 수고하셨다!
참조:
