Hash Table이란 효율적인 key value lookup을 위해 key를 value에 매핑하는 자료 구조입니다. 찾는 과정을 살펴보면, 먼저 hash function을 사용해서 hash code 값을 계산합니다. key를 변환해서 더 작은 key로 만드는데 사용되는 함수가 hash function 인데요, 그렇게 해서 얻어진 값인 hash(key) 값이 hash code 입니다.

이 hash code를 array length로 나누어 얻어진 나머지를 index로 사용해서 해당 index에 매핑되는 value를 array에 저장하고 찾는 것입니다.

예를 들어, [“apple”, “banana”, “lemon”] 이라는 key 배열이 있다고 가정하면 python에서 hash function을 사용해서 hash code를 얻으면 각각 값이 4431541238040168687, 7306034771644922176, 3404778505129102945 이 됩니다. array의 length는 3이기 때문에 각각을 3으로 나눈 나머지는 0, 1, 1 입니다. 그리고 이 값들이 index가 되어서 해당 index에 있는 value가 원래 key인 “apple”, “banana”, “lemon”에 매핑되는 값입니다.

이 경우에서도 볼 수 있지만 hash code가 다르더라도 동일한 index가 나올 수 있습니다. 또한 서로 다른 key에 대해서 hash code 값이 같을 수도 있어서 이 경우에도 동일한 index가 나올 수 있습니다.

이를 보완하기 위해 Linear Probing 기법에서는 index가 겹치면 그 다음 index를 사용합니다. 예를 들어, 아까처럼 “lemon”의 hash code를 3으로 나눈 나머지가 1로 “banana”의 index와 겹치면 1대신 2를 index로 사용합니다.

이러한 충돌이 매우 높으면 worst case로는 런타임이 O(N)이 됩니다. (여기서 N은 key의 갯수입니다.) 그러나 일반적으로 충돌이 최소한으로 발생한다고 가정하여 look up 타임을 O(1)로 가정합니다.

Binary Search, 이진 탐색 알고리즘이란 배열의 원소가 순서대로 sorting이 되어 있다는 가정하에 중간에 있는 element와 찾으려는 element의 크기를 비교해서 찾는 방식입니다.

크기를 비교해서 찾으려는 element보다 중간에 있는 element가 작으면 그 이하를 탐색에서 제외하고, 중간에 있는 element가 그보다 크면 그 이상도 탐색에서 제외합니다. 그래서 찾으려는 값과 중간에 있는 값이 같아질 때까지 반복합니다. 이렇게 하면 탐색 범위를 N/2, N/4 … 이런식으로 절반씩 줄여나갈 수 있다는 장점이 있습니다.

예를 들어, [1,2,4,5,6,7,8,9] 라는 배열에서 6을 찾는다고 가정합니다. 전체 8개로 이루어진 리스트의 중간 element는 약 3번째 index를 가진 5입니다. 그러면 5와 6을 비교했을 때 5보다 6이 크기 때문에 중간 element인 5 이하는 탐색에서 제외합니다. 그래서 6부터 9까지 보는데 여기에서 중간 위치에 있는 element는 7입니다. 7보다 6이 작기 때문에 7 이상부터는 탐색에서 제외합니다. 그러면 이제 6만 남기 때문에 찾는 것이 완료되게 됩니다.

다음은 Python으로 구현한 코드입니다. middle에 있는 값을 구해서 찾으려는 값과 비교하여 같으면 middle에 있는 값의 index를 리턴하고 만약 middle에 있는 값이 찾으려는 x보다 작으면 lower를 현재 middle index 값보다 + 1만큼 증가시켜서 middle 보다 큰 값에서부터 x를 찾습니다. 반대로 middle에 있는 값이 찾으려는 x보다 크면 upper를 현재 middle index 값보다 – 1 만큼 감소시켜서 middle보다 낮은 값에서부터 x를 찾습니다.

def binarySearch(L, x):
    lower = 0
    upper = len(L) - 1
    while lower <= upper:
        middle = (lower + upper) // 2
        if L[middle] == x:
            return middle
        elif L[middle] < x:
            lower = middle + 1
        else:
            upper = middle - 1
    return -1

Big O 란 컴퓨터 공학에서 알고리즘의 성능이나 복잡성을 측정하기 위해 사용되는 개념입니다. 주로 worst 시나리오를 가정하는데, input size가 증가함에 따라 알고리즘의 실행 소요시간(Time Complexity) 또는 메모리나 디스크 상에서 차지하는 공간(Space Complexity)을 나타냅니다. 개념에 대한 설명은 Cracking the Coding Interview의 순서를 따랐습니다.

1. 1. Time Complexity

표기는 O(N), O(N^2) 처럼 표시 됩니다. 예를 들어 O(N)이라는 것은 input size에 “선형적”으로 런타임이 비례하는 것입니다.

기울기가 1인 Y = X 라는 그래프를 생각해보았을 때 아래 그래프처럼 선형적인 모양이 생각나실 텐데요, X 값이 증가함에따라 선형적으로 Y 값도 증가하는 것처럼 O(N)도 input N의 크기에 따라 선형적으로 런타임이 증가한다고 이해할 수 있습니다.

1. 2. Space Complexity

Space Complexity는 알고리즘이 차지하는 메모리를 나타냅니다. 예를 들어 size가 n인 배열을 생성한다고 하면 O(N) 만큼의 space를 차지한다고 보면 됩니다.

3. Drop the Constants

Big O에서 상수만큼 곱해진 것은 고려하지 않는 것입니다. 예를 들어 O(2N) 으로 보여지는 것도 결국 O(N)과 같습니다.

예를 들어 for loop 하나 안에 if 절 2개가 정의된 것이나 for loop 하나에 if 절 하나, 그 다음 for loop 하나에 if 절 하나인 것이나 같습니다. 다음은 pseudo 코드로 간략하게 로직을 적어본 것입니다.

# O(N)
for loop:
    if 절 첫번째
    if 절 두번째

# O(2N) 이나 결과적으로 O(N)
for loop:
    if 절 첫번째
for loop:
    if 절 두번째

4. Drop the Non-Dominant Terms

Big O를 계산할 때 큰 영향을 끼치지 않는 것은 제외하는 것입니다. 예를 들어, O(N^2 + N)에서 N은 Big O 계산시에 영향력이 있는 값이 아니기 때문에 N을 제외해서 O(N^2) 으로 나타냅니다. 왜냐면 N이 커지면 커질수록 N을 더하는 것의 영향력은 작아지고 N^2의 영향력이 주요하기 때문입니다.

앞서 살펴본 Drop the Constants 원칙과 비슷한 맥락으로 이해할 수 있습니다.

5. Multi-Part Algorithms: Add + Multiply

만약 알고리즘이 A를 먼저하고 그게 끝나면 그 다음에 B를 하라고 하면 O(A+B)입니다. 반면에 A를 할 때마다 B를 하라고 하면 O(A*B) 입니다. 이러한 로직으로 런타임을 더하거나 곱할 수 있습니다. 다음은 pseudo 코드로 간략하게 로직을 적어본 것입니다.

# O(A+B) --> A 끝나고 B
for loop (A):
for loop (B):

# O(A*B) --> A의 element 마다 B 실행
for loop (A):
   for loop (B):

6. Amortized Time

Amortized Time 이라는 개념은 worst case가 가끔 발생하지만 한 번 발생하면 한동안은 발생하지 않는다는 것입니다. 예를 들어 array에 element가 추가되다가 어느 순간 capacity에 한계가 오면 새로운 array를 capacity를 double로 해서 생성한다고 할 때, 그 새로운 array에 모든 element를 복제합니다. 이 경우 element를 insertion 하는데 걸리는 런타임을 어떻게 표시할 수 있을까요?

N개의 element를 포함하는 array의 용량이 꽉 차서 사이즈가 2N인 새로운 array로 옮겨갈 경우, 새로 만들어진 array에 기존 element를 추가하는 시간은 O(N)일 것입니다.

그렇지만 이렇게 꽉차서 새로운 array를 생성해서 element를 insert해야하는 상황은 자주 발생하지 않습니다. 따라서 기존에 있던 array에 element를 추가하는 대부분의 insertion하는 시간은 O(1) 입니다.

따라서 어쩌다 한 번 발생하는 worst case의 경우 O(N), 그리고 평균적으로 insertion 하는 case는 O(1) 입니다.

이렇게 size를 증가시키는 배열을 동적 배열 dynamic array 라고 하는데요 좀 더 자세히 살펴보겠습니다. 예를 들어 element가 1개 있을 때 배열이 꽉 찼다라고 보면 이 배열의 사이즈를 2배 늘리는 것입니다. 그러면 사이즈가 원래 1 이었는데 1*2 해서 2로 늘어납니다. 여기서 element가 새로 추가되면서 size 2가 꽉 차게 됩니다. 그러면 size를 2배 늘려서 2*2 = 4 size인 배열이 만들어집니다. 이 상태에서 element 들이 추가되다가 결국 size 4도 꽉 차게 됩니다. 그러면 또 2배 늘려서 size가 8인 배열이 만들어지고 기존에 있던 element들이 이 새로운 사이즈의 배열로 복제됩니다.

이런식으로 계속 기존 배열에 element를 추가하다가 사이즈가 꽉차서 2배만큼 double로 사이즈를 늘리게 되면 공식으로는 1+ 2+ 3+ 8 + 16 + … + X 만큼 런타임이 소요되게 됩니다.

이 수식을 거꾸로 써보면 X + X/2 + X/4 + X/8 + … + 1 이렇게 되는데요 다시 이 공식을 수정하면 X( 1 + 1/2 + 1/4 + 1/8 + …..) = X*(1+1) = 2X 가 됩니다. 1/2 + 1/4 + … 를 다 더하면 이 값이 아래 위키피디아를 참고한 공식에 의해서 총 1이 되기 때문에 다 더하면 2X가 되는 것입니다.

그러면 worst case로 X 만큼 insertion하는 시간은 O(2X) 만큼의 time이 소요됩니다. 여기서 Drop the Constants라는 법칙에 따라서 2를 날려버리게 되면 array 사이즈가 꽉차서 새로 배열을 만들어 기존의 element들을 복제하는데 걸리는 시간은 결과적으로 O(N)이 됩니다.

그러나 이러한 케이스는 드물게 어쩌다 발생하는 것이고, 평소에는 element를 하나씩 추가하기 때문에 O(1) 만큼의 시간이 걸립니다.

7. Log N Runtimes

Binary Search 알고리즘을 통해 Log N 런타임을 이해해보도록 하겠습니다. Binary Search 알고리즘이란 간단하게 말해서 element가 순서대로 sorting이 되어있는 배열에서 원하는 값 x를 찾을 때 배열의 중간에 있는 값과 크기를 비교해서 범위를 축소해나가면서 x를 찾는 알고리즘입니다. 알고리즘의 탐색 범위가 N/2, N/4, N/8 이런식으로 절반씩 줄어들기 때문에 O(log N) 으로 나타낼 수 있습니다. 따라서 탐색 스페이스가 절반씩 줄어드는 알고리즘은 O(log N) 만큼의 complexity를 가진다고 볼 수 있습니다.

예를 들어 [1, 5, 8, 9, 11, 13, 15, 19, 21] 에서 N은 8 >> 4 >> 2 >> 1 이런식으로 탐색 범위가 절반식 줄어든다고 이해할 수 있습니다. 이 순서를 거꾸로 하면 N = 1 >> 2 >> 4 >> 8 이라고 볼 수 있는데 2^3 이 8 이고 log를 씌우면 log 8/log 2 = 3 즉 log N/log 2 = k 여기서 constant인 1/log 2 를 drop 하면 O(log N)이 됩니다.

8. Recursive Runtimes

결론적으로 재귀함수의 space complexity는 O(N) 입니다. 재귀함수는 전체적으로 O(2^N) 만큼의 노드가 있지만 주어진 시간 내에서 차지하는 메모리는 O(N) 입니다.

먼저 재귀함수의 전체 노드를 카운트해 보면 2^0 + 2^1 + 2^2 + … + 2^N 입니다. 수학적으로 다 더하면 2^(N+1) – 1 입니다. 따라서 노드의 수는 O(2^(N+1) – 1) 인데 Constant와 Non Dominant Terms를 제외하면 O(2^N) 이 됩니다. 그러나 주어진 시간에서는 O(N) 만큼의 메모리만 차지합니다. 그 이유는 호출되는 수와 무관하게, 처리되는 것은 depth만큼 누적되기 때문입니다. 예를 들어 다음과 같은 함수가 있을 때,

int f(int n) {
	if (n <= 1) {
	return 1;
	}
	return f(n - 1) + f(n - 1)
}

n = 4일 때 f(4) = f(3) + f(3) 인데 여기서 f(3)이 처리되고 순서상 바로 f(2) >> f(1) 까지 순차적으로 처리 되어야만 그 때부터 누적된 것들이 거슬러 올라가면서 처리됩니다. 즉 가장 먼저 처리되는 순서를 보면 f(4) >> f(3) >> f(2) >> f(1) 이기 때문에 depth인 4만큼이 메모리를 차지합니다. 따라서 O(N) 만큼의 space complexity를 차지한다고 볼 수 있습니다.

안녕하세요 이번 포스트에서는 Quick Sort 알고리즘의 정의를 알아보고 Quick Sort를 Python으로 구현한 코드까지 같이 살펴보도록 하겠습니다.

Quick Sort 알고리즘은 divide and conquer 방식으로 배열을 나누어 가면서 정렬하는 방식으로 다음과 같이 계산됩니다.

1) 배열에서 pivot(중심점)을 선택합니다.

2) 두 번째로, 선택된 pivot보다 작은 값들은 왼쪽으로 큰 값들은 오른쪽으로 움직입니다.

3) 이 과정은 위의 pivot보다 작은 값들로 이루어진 sub array에서도 반복되고 pivot보다 큰 값들로 이루어진 sub array에서도 반복되어서 배열 전체 값이 정렬될때까지 재귀적으로 이루어집니다. 그렇게해서 결과적으로 순서대로 배열이 정렬되게 됩니다.

자세한 설명은 아래 유투브 영상에서 시각적으로 보여주고 있어서 참고 링크를 첨부드립니다.

이 영상에서는 pivot을 선택하고 그 pivot을 기준으로 맨 왼쪽부터 체크해서 pivot보다 큰 값을 itemFromLeft로 정하고 맨 오른쪽부터 체크해서 pivot보다 작은 값을 itemFromRight로 정합니다.

그렇게 해서 itemFromLeft의 순서가 itemFromRight보다 Left 즉 왼쪽에 위치하면 두 값을 서로 교체하고 반대로 itemFromLeft의 순서가 itemFromRight보다 Right 즉 오른쪽에 위치하면 itemFromLeft 값을 pivot과 교체합니다. index로 표현하면 index(itemFromLeft) < index(itemFromRight) 이면 두 값을 교체하지만 index(itemFromLeft) > index(itemFromRight) 이면 이제itemFromLeft를 pivot과 교체합니다.

그러면 pivot 기준 좌측에 있는 값들은 pivot보다 전부 작고 우측에 있는 값들은 pivot보다 전부 크게 됩니다.

이후 pivot 기준 좌측 sub array와 우측 sub array에서 위와 같은 과정을 반복하면 결과적으로 순서가 sorting이 됩니다.

관련해서 Python 코드를 보겠습니다. Python 코드는 아래 유투브 영상의 댓글에서 Mr. UncleChu 라는 분이 굉장히 깔끔한 코드를 써놓아서 이 코드를 가져왔고 제가 마지막 리턴하는 부분만 수정하였습니다. 원본 코드는 리턴하는 값이 sum([lesser, [a_array[0]], bigger], []) 인데, sum 함수 안에 숫자가 아닌 것을 넣을 경우 성능이 좋지 않기 때문에 그 한 줄만 바꾸었습니다.

from functools import reduce 

def quick_sort(a_array):
    if len(a_array) < 2: return a_array
    lesser = quick_sort([x for x in a_array[1:] if x <= a_array[0]])
    bigger = quick_sort([x for x in a_array[1:] if x >  a_array[0]])
    return reduce(lambda x, y: x+y, [lesser, [a_array[0]], bigger])

보시면 quick_sort 라는 재귀함수로 구성되어 있고 처음에 [6,2,3,5,9,0,1,7,8,10,4] 라는 배열이 있다고 하면, 이 코드에서 a_array[0] 즉 6은 최초의 pivot이 됩니다.

여기에서는 pivot을 선택할 때 전체 배열의 맨 처음, 중간, 끝 중에서 중앙값을 선택하는 방식으로 하지 않고 단순히 배열의 0번을 pivot으로 지정합니다.

재귀함수가 lesser 계산하면서도 있고 bigger 계산하면서도 있기 때문에 순서를 따라가는 것이 복잡하지만 위에 공유드린 코드에서 하나하나 값들을 print로 출력해서 보시면 이 순서를 따라가실 수 있을 것입니다. 하나하나 print 하는 코드는 다음과 같습니다.

from functools import reduce 

def quick_sort(a_array):
    print("start: ", a_array, len(a_array))
    if len(a_array) < 2: return a_array
    print("pivot 1: ", a_array[0], a_array)
    print("total 1: ",a_array[1:], "quick sort 1: ", [x for x in a_array[1:] if x <= a_array[0]])
    lesser = quick_sort([x for x in a_array[1:] if x <= a_array[0]])
    print("lesser: ", lesser)

    print("pivot 2: ", a_array[0], a_array)
    print("total 2", a_array[1:], "quick sort 2", [x for x in a_array[1:] if x >  a_array[0]])
    bigger = quick_sort([x for x in a_array[1:] if x >  a_array[0]])
    print("bigger: ", bigger)
    print(lesser, a_array[0], bigger)
    print("answer: ", reduce(lambda x, y: x+y, [lesser, [a_array[0]], bigger]))
    return reduce(lambda x, y: x+y, [lesser, [a_array[0]], bigger])
 
test_array = [6,2,3,5,9,0,1,7,8,10,4]
quick_sort(test_array)

구두로 풀어서 설명드리면,

전체 배열 [6,2,3,5,9,0,1,7,8,10,4] 에서 0번 index 값인 6을 pivot으로 결정하면 pivot을 제외한 배열 a_array[1:]인 [2,3,5,9,0,1,7,8,10,4] 중에서 6보다 작은 값들을 선택해서 sub array를 만듭니다. 그러면 [2, 3, 5, 0, 1, 4] 가 되는데 여기서 quick_sort 함수가 호출이 됩니다. 그러면 [2, 3, 5, 0, 1, 4] 에 대해서 다시 pivot을 계산합니다. 이번에는 2가 pivot이 되고 2를 제외한 나머지 sub array [3, 5, 0, 1, 4] 에서 2보다 작은 값들로 배열을 만들면 [0, 1] 이 되는데 여기서 또 quick_sort 함수가 호출이 됩니다. 그러면 이번에는 pivot이 0이 되고 0보다 작은 값은 없기 때문에 그 배열은 []이 됩니다. 그러면 []를 가지고 다시 quick_sort가 호출이 되는데 이번에는 배열의 length가 2보다 작기 때문에 배열이 if 절에서 바로 리턴되고 더이상 lesser에서 quick_sort가 호출될 수 없으므로 0이 pivot일 때 lesser가 계산이 되어서 lesser는 [] 가 됩니다. 그러고 나서 pivot이 0인 상태에서 이제 bigger가 계산이 되는데 그 값은 [1]로 여기서 다시 quick_sort가 호출되는데 length가 2보다 작기 때문에 배열이 if 절에서 바로 리턴되고 마저 pivot이 0일 때의 bigger가 [1]로 계산됩니다. 그러면 lesser []. pivot 0, bigger [1] 해서 answer가 [0, 1]이 되고 이제 pivot 0일 때 해야하는 것은 다 끝났기 때문에 마저 pivot 2일 때 lesser를 계산하던 로직으로 가서 lesser가 [0, 1]이 되고 pivot 2일 때 bigger를 계산하는 로직으로 넘어갑니다.이번에는 2보다 큰 값들이 [3, 5, 4] 되면서 이제 이 값을 기준으로 다시 quick_sort가 호출됩니다. 그러면서 꼬리에 꼬리를 물고 계속 더 이상 호출될 quick_sort가 없을 때까지 재귀적으로 진행된다고 보시면 됩니다.

크게 로직을 이해해보면 오히려 더 이해가 쉬워지는데요 pivot 하나를 정해서 (코드 상에서는 array의 0번째 값) 이 pivot보다 작은 값들로 이루어진 배열을 lesser, 큰 값들로 이루어진 배열을 bigger라고 하고 그 안에서도 재귀적으로 새로운 pivot을 기준으로 lesser와 bigger을 계산해주는 것입니다. 이렇게 재귀적으로 반복하다보면 최종적으로 한 pivot을 기준으로 lesser와 bigger가 나눠지는데 lesser 안에서도 순서대로 되어 있고 bigger 안에서도 순서대로 되어있어서 최종적으로 lesser, pivot, bigger 를 보면 전체 배열이 sorting이 되어있습니다.