MIT 6.00 10회차 강의후기

License

License: Creative Commons BY-NC-SA

 

Divide & Conquer

Divide & Conquer의 순서

1. 문제를 같은 유형의 문제로 쪼갠다.

2. 각각의 작은 문제들을 독립적으로 해결한다.

3. 그 해결들을 합친다.

 

병합정렬

각각의 가장 작은 숫자들부터 비교해서 리스트를 합치는 알고리즘.  
big-O는 n이다.

 

분할정복의 예시

def merge(left,right):
    """Assumes left and right are sorted lists.
    Returns a new sorted list containing the same elements
    as (left + right) would contain."""
    result = []
    i,j = 0, 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i = i + 1
        else:
            result.append(right[j])
            j = j + 1
    while (i < len(left)):
        result.append(left[i])
    i = i + 1
    while (j < len(right)):
        result.append(right[j])
    j = j + 1
    return result

def mergesort(L):
    """Returns a new sorted list with the same elements as L"""
    print (L)
    if len(L) < 2:
        return L[:]
    else:
        middle = len(L) / 2
        left = mergesort(L[:middle])
        right = mergesort(L[middle:])
        together = merge(left,right)
        print ('merged', together)
        return together

분할정복을 사용한다면 큰 문제를 쪼갤 수 있지만, merge의 단계에서 더 복잡한 일을 해야한다면 효율적이지 않다.

 

분할정복의 복잡도

각 레벨마다 병합을 할때마다 n의 복잡성이 소요된다.  
이때, 문제를 절반으로 나누는 연산을 할때마다 n/2만큼의 계산이 필요하게 된다(logn).  
따라서 logn을 n회 했다는 의미의 nlogn이 분할정복의 복잡도가 된다.

 

Hashing

해쉬 함수의 복잡도는 1이라는 상수이다.  
어떤 데이터든 정수로 대응시켜 곧바로 찾아내기 때문이다.

 

End lecture from here

이후 강의부터 나오는 예외처리나 알고리즘의 경우 대부분 이미 배워본 경험이 있고,  
더 깊은 지식을 얻기 위해 따로 계획한 바가 있다.  
파이썬에 대한 선수지식도 없었고, 영어로 진행되는 강의라 배우는 것에 고생을 했지만  
이 강의를 듣지 않았다면 무엇이 좋은 코드인지, 어떤 규칙을 지켜야 하는지, 문제의 해결 방법을 어떻게 찾는지 등 프로그래밍 기초에 대한 아웃라인을 잡기 힘들었을 것이라 생각한다. 

많은 도움이 된 유익한 강의였다!  
MIT 6.00 OCW 포스트를 여기까지 하려고 한다.