오늘 배울 것
- 정렬
- 스택
- 큐
- 해쉬
정렬
정렬 - 알고리즘의 굉장히 중요한 주제로, 데이터를 순서대로 나열하는 방법
정렬 - 1
버블 정렬
- 첫 번째 자료와 두 번째 자료를, 두 번째 자료와 세 번째 자료를, 세 번째와 네 번째를, … 이런 식으로 (마지막-1)번째 자료와 마지막 자료를 비교하여 교환하면서 자료를 정렬하는 방식
- 작은 숫자, 큰 숫자 순서로 있으면 내버려두고 큰 숫자, 작은 숫자 순서로 있으면 둘의 위치를 변경한다.
[4, 6, 2, 9, 1] # 정렬되지 않은 배열
1단계 : [4, 6, 2, 9, 1]
4와 6을 비교합니다!
4 < 6 이면 그대로 둡니다.
2단계 : [4, 6, 2, 9, 1]
6과 2를 비교합니다!
6 > 2 이므로 둘을 변경합니다!
[4, 2, 6, 9, 1] 이렇게요!
3단계 : [4, 2, 6, 9, 1]
6과 9를 비교합니다!
6 < 9 이면 그대로 둡니다.
4단계 : [4, 2, 6, 9, 1]
9와 1를 비교합니다!
9 > 1 이므로 둘을 변경합니다!
[4, 2, 6, 1, 9] 이렇게요!
자, 그러면 이제 한 바퀴를 돌렸죠?
이 과정에서 가장 큰 숫자인 9가 맨 뒤로 왔습니다.
큰 게 나오면 둘의 자리를 변경했으니 가장 맨 뒤에 갔다는 소리입니다!
그러면, 맨 뒷자리를 제외하고 다시 한 번 돌리면 됩니다!
5단계 : [4, 2, 6, 1, 9]
4와 2을 비교합니다!
4 > 2 이므로 둘을 변경합니다.
[2, 4, 6, 1, 9] 이렇게요!
6단계 : [2, 4, 6, 1, 9]
4와 6을 비교합니다!
4 < 6 이면 그대로 둡니다.
7단계 : [2, 4, 6, 1, 9]
6와 1을 비교합니다!
6 > 1 이므로 둘을 변경합니다!
[2, 4, 1, 6, 9] 이렇게요!
그러면 이제 두 번째로 큰 숫자인 6이 맨 뒤에서 두번쨰로 왔습니다!
여기까지만 비교하시면 됩니다. 6과 9을 비교할 필요는 없습니다.
다시 한 번 가볼게요!
8단계 : [2, 4, 1, 6, 9]
2와 4을 비교합니다!
2 < 4 이면 그대로 둡니다.
9단계 : [2, 4, 1, 6, 9]
4와 1을 비교합니다!
4 > 1 이므로 둘을 변경합니다!
[2, 1, 4, 6, 9] 이렇게요!
자, 이제 세 번쨰로 큰 숫자인 4가 맨 뒤에서 세번째로 왔습니다!
마지막 비교만 하면 됩니다!
10단계 : [2, 1, 4, 6, 9]
2와 1을 비교합니다!
2 > 1 이므로 둘을 변경합니다!
[1, 2, 4, 6, 9] 이렇게요!
자, 모두 정렬이 되었습니다! 어떠신가요? 감이 좀 오시나요?
* Swap 하는 방법
>>> a = 3
>>> b = 4
>>> a, b = b, a # a, b 스왑
>>> print(a)
4
>>> print(b)
3
코드로 구현
input = [4, 6, 2, 9, 1]
def bubble_sort(array):
n = len(array)
for i in range(n): # n-1번만 비교하면 되니까
for j in range(n - i - 1): # Q. 여기서왜 n - i - 1 일까요?
if array[j] > array[j + 1]: # A. array[j] 와 array[j + 1] 을 비교할거라,
array[j], array[j + 1] = array[j + 1], array[j] # 마지막 원소까지 가지 않아도 되기 때문이에요!
return array
bubble_sort(input)
print(input)
print("정답 = [1, 2, 4, 6, 9] / 현재 풀이 값 = ",bubble_sort([4, 6, 2, 9, 1]))
print("정답 = [-1, 3, 9, 17] / 현재 풀이 값 = ",bubble_sort([3,-1,17,9]))
print("정답 = [-3, 32, 44, 56, 100] / 현재 풀이 값 = ",bubble_sort([100,56,-3,32,44]))
함수의 시간 복잡도
2차 반복문을 array만큼 구현 -> O(N^2)
참고로, 버블 정렬은 다음과 같이 동작합니다!
맨 오른쪽을 보면 옆과 비교하면서
최댓값이 찾아지면서 쌓아지는구나! 라고 생각하시면 됩니다.
정렬 - 2
선택 정렬
선택 정렬 - 선택해서 정렬한다.
최솟값을 찾아 맨 앞에 배치(swap)
두번째로 작은 값을 찾아 두번째 자리에 배치(swap)
...
[4, 6, 2, 9, 1] # 정렬되지 않은 배열
1단계 : [4, 6, 2, 9, 1]
4와 6과 2와 9와 1을 차례차례 비교합니다.
그 중 가장 작은 1과 맨 앞 자리인 4를 교체합니다!
[1, 6, 2, 9, 4] 이렇게요!
자, 그러면 이제 가장 작은 숫자인 1이 맨 앞으로 왔습니다.
가장 작은 걸 가장 맨 앞으로 옮기기로 했으니까요!
그러면, 맨 앞자리를 제외하고 다시 한 번 반복하면 됩니다.
2단계 : [1, 6, 2, 9, 4]
6과 2와 9와 4를 차례차례 비교합니다.
그 중 가장 작은 2와 두번째 앞 자리인 6을 교체합니다!
[1, 2, 6, 9, 4] 이렇게요!
3단계 : [1, 2, 6, 9, 4]
6과 9와 4를 차례차례 비교합니다.
그 중 가장 작은 4와 세번째 앞 자리인 6을 교체합니다!
[1, 2, 4, 9, 6] 이렇게요!
4단계 : [1, 2, 4, 9, 6]
9와 6을 비교합니다!
그 중 가장 작은 6과 네번째 앞 자리인 9을 교체합니다!
[1, 2, 4, 6, 9] 이렇게요!
자, 모두 정렬이 되었습니다! 어떠신가요? 감이 좀 오시나요?
버블 정렬보다 훨씬 더 적은 비교를 하는 것 같지만,
실제로는 각 배열을 계속해서 탐색하는 방식이라 2중 반복문을 사용해야 합니다!
코드로 구현
input = [4, 6, 2, 9, 1]
def selection_sort(array):
n = len(array)
for i in range(n - 1):
min_index = i
for j in range(n - i):
if array[i + j] < array[min_index]:
min_index = i + j
array[i], array[min_index] = array[min_index], array[i]
return array
selection_sort(input)
print(input)
print("정답 = [1, 2, 4, 6, 9] / 현재 풀이 값 = ",selection_sort([4, 6, 2, 9, 1]))
print("정답 = [-1, 3, 9, 17] / 현재 풀이 값 = ",selection_sort([3,-1,17,9]))
print("정답 = [-3, 32, 44, 56, 100] / 현재 풀이 값 = ",selection_sort([100,56,-3,32,44]))
버블 정렬과의 차이점
버블 정렬하고 다른 건 바로 "최솟값"을 찾아 변경하는 것입니다.
따라서, min_index 라는 변수를 통해 각각의 인덱스들과 비교합니다.
그리고 내부의 반복문이 끝나면, 최소 값의 인덱스와 i의 값들을 교체해주면 됩니다!
함수의 시간 복잡도 - 2차반복문을 array 길이로 -> O(N^2)
* 참고로, 선택 정렬은 다음과 같이 동작합니다!
맨 왼쪽부터 보면 최솟값이 찾아지면서 쌓아지는구나! 라고 생각하시면 됩니다.
삽입 정렬
삽입 정렬 - 전체에서 하나씩 올바른 위치에 "삽입" 하는 방식
선택 정렬은 현재 데이터의 상태와 상관없이 항상 비교하고 위치를 바꾸지만, 삽입 정렬은 필요할 때만 위치를 변경하므로 더 효율적인 방식입니다!
[4, 6, 2, 9, 1] # 정렬되지 않은 배열
1단계 : [4, 6, 2, 9, 1]
4는 현재 정렬되어 있는 부대원입니다.
그럼 이제 새로운 신병인 6을 받습니다.
4, 6 이 되는데 4 < 6 이므로 그대로 냅둡니다.
[4, 6, 2, 9, 1] 이렇게요!
자, 그러면 이제 한 바퀴를 돌렸죠?
이 과정에서 새로운 부대원인 4, 6은 현재 정렬된 상태입니다!
이처럼, 삽입 정렬은 한 바퀴가 돌 때마다 정렬된 상태가 됩니다.
끝까지 한 번 반복해볼게요!
2단계 : [4, 6, 2, 9, 1]
4, 6 은 현재 정렬되어 있는 부대원입니다.
그럼 이제 새로운 신병인 2를 받습니다.
4, 6, 2 가 되는데 6 > 2 이므로 둘을 변경합니다!
4, 2, 6 가 되는데 4 > 2 이므로 둘을 변경합니다!
[2, 4, 6, 9, 1] 이렇게요!
3단계 : [2, 4, 6, 9, 1]
2, 4, 6 은 현재 정렬되어 있는 부대원입니다.
그럼 이제 새로운 신병인 9를 받습니다.
2, 4, 6, 9 가 되는데 6 < 9 이므로 그대로 냅둡니다.
[2, 4, 6, 9, 1] 이렇게요!
4단계 : [2, 4, 6, 9, 1]
2, 4, 6, 9 은 현재 정렬되어 있는 부대원입니다.
그럼 이제 새로운 신병인 1을 받습니다.
2, 4, 6, 9, 1 가 되는데 9 > 1 이므로 둘을 변경합니다!
2, 4, 6, 1, 9 가 되는데 6 > 1 이므로 둘을 변경합니다!
2, 4, 1, 6, 9 가 되는데 4 > 1 이므로 둘을 변경합니다!
2, 1, 4, 6, 9 가 되는데 2 > 1 이므로 둘을 변경합니다!
[1, 2, 4, 6, 9] 이렇게요!
자, 모두 정렬이 되었습니다! 어떠신가요? 감이 좀 오시나요?
코드로 구현
input = [4, 6, 2, 9, 1]
def insertion_sort(array):
n = len(array)
for i in range(1, n):
for j in range(i):
if array[i - j - 1] > array[i - j]:
array[i - j - 1], array[i - j] = array[i - j], array[i - j - 1]
else:
break
return array
insertion_sort(input)
print(input)
print("정답 = [4, 5, 7, 7, 8] / 현재 풀이 값 = ",insertion_sort([5,8,4,7,7]))
print("정답 = [-1, 3, 9, 17] / 현재 풀이 값 = ",insertion_sort([3,-1,17,9]))
print("정답 = [-3, 32, 44, 56, 100] / 현재 풀이 값 = ",insertion_sort([100,56,-3,32,44]))
함수의 시간 복잡도 - O(N^2)
* 그러나, 버블 정렬과 선택 정렬과 다른 면이 있습니다. 버블 정렬과 선택 정렬은 최선이든 최악이든 항~~상 O(N^2) 만큼의 시간이 걸렸지만, 최선의 경우에는 Ω(N) 만큼의 시간 복잡도가 걸립니다. 거의 정렬이 된 배열이 들어간다면 break 문에 의해서 더 많은 원소와 비교하지 않고 탈출할 수 있기 때문입니다!
정렬 - 3
**면접에서 직접 구현해보라고 하는 구현 방법들
병합 정렬 - merge
병합 정렬(merge) - 배열의 앞부분과 뒷부분의 두 그룹으로 나누어 각각 정렬한 후 병합하는 작업을 반복하는 알고리즘
[1, 2, 3, 5] # 정렬된 배열 A
[4, 6, 7, 8] # 정렬된 배열 B
[] # 두 집합을 합칠 빈 배열 C
↓
1단계 : [1, 2, 3, 5]
↓
[4, 6, 7, 8]
1과 4를 비교합니다!
1 < 4 이므로 1을 C 에 넣습니다.
C:[1]
↓
2단계 : [1, 2, 3, 5]
↓
[4, 6, 7, 8]
2와 4를 비교합니다!
2 < 4 이므로 2를 C 에 넣습니다.
C:[1, 2]
↓
3단계 : [1, 2, 3, 5]
↓
[4, 6, 7, 8]
3과 4를 비교합니다!
3 < 4 이므로 3을 C 에 넣습니다.
C:[1, 2, 3]
↓
3단계 : [1, 2, 3, 5]
↓
[4, 6, 7, 8]
5와 4를 비교합니다!
5 > 4 이므로 4을 C 에 넣습니다.
C:[1, 2, 3, 4]
↓
3단계 : [1, 2, 3, 5]
↓
[4, 6, 7, 8]
5와 6을 비교합니다!
5 < 6 이므로 5을 C 에 넣습니다.
C:[1, 2, 3, 4, 5]
엇, 이렇게 되면 A 의 모든 원소는 끝났습니다!
그러면 B에서 안 들어간 원소인
[6, 7, 8] 은 어떡할까요?
하나씩 C 에 추가해주면 됩니다.
C:[1, 2, 3, 4, 5, 6, 7, 8] 이렇게요!
그러면 A 와 B를 합치면서 정렬할 수 있었습니다.
한 번, 직접 이 로직을 코드로 구현해보겠습니다!
코드로 구현
array_a = [1, 2, 3, 5]
array_b = [4, 6, 7, 8]
def merge(array1, array2):
result = []
array1_index = 0
array2_index = 0
while array1_index < len(array1) and array2_index < len(array2):
if array1[array1_index] < array2[array2_index]:
result.append(array1[array1_index])
array1_index += 1
else:
result.append(array2[array2_index])
array2_index += 1
if array1_index == len(array1):
while array2_index < len(array2):
result.append(array2[array2_index])
array2_index += 1
if array2_index == len(array2):
while array1_index < len(array1):
result.append(array1[array1_index])
array1_index += 1
return result
print(merge(array_a, array_b))
print("정답 = [-7, -1, 5, 6, 9, 10, 11, 40] / 현재 풀이 값 = ", merge([-7, -1, 9, 40], [5, 6, 10, 11]))
print("정답 = [-1, 2, 3, 5, 10, 40, 78, 100] / 현재 풀이 값 = ", merge([-1,2,3,5,40], [10,78,100]))
print("정답 = [-1, -1, 0, 1, 6, 9, 10] / 현재 풀이 값 = ", merge([-1,-1,0], [1, 6, 9, 10]))
병합 정렬 - mergeSort
그런데, 의문이 생길 수 있습니다.
이 방법으로 어떻게 정렬을 할 수 있는건가요?
이건 그냥 정렬된 배열을 합치는 거 아닌가요?
바로, 분할 정복의 개념을 적용하면 됩니다.
분할 정복은 문제를 작은 2개의 문제로 분리하고 각각을 해결한 다음,
결과를 모아서 원래의 문제를 해결하는 전략입니다.
예를 들어서 [5, 4] 라는 배열이 있다면
이 배열을 [5] 와 [4] 를 가진 각각의 배열로 작은 2개의 문제로 분리해서 생각하는 것입니다.
그러면 이 둘을 합치면서 정렬한다면? 결국 전체의 정렬된 리스트가 될 수 있습니다.
이 개념을 조금 더 확대해서 생각해보겠습니다.
[5, 3, 2, 1, 6, 8, 7, 4] 이라는 배열이 있다고 하겠습니다. 이 배열을 반으로 쪼개면
[5, 3, 2, 1] [6, 8, 7, 4] 이 됩니다. 또 반으로 쪼개면
[5, 3] [2, 1] [6, 8] [7, 4] 이 됩니다.
또 반으로 쪼개면 [5] [3] [2] [1] [6] [8] [7] [4] 이 됩니다.
이 배열들을 두개씩 병합을 하면 어떻게 될까요?
[5] [3] 을 병합하면 [3, 5] 로
[2] [1] 을 병합하면 [1, 2] 로
[6] [8] 을 병합하면 [6, 8] 로
[7] [4] 을 병합하면 [4, 7] 로
그러면 다시!
[3, 5] 과 [1, 2]을 병합하면 [1, 2, 3, 5] 로
[6, 8] 와 [4, 7]을 병합하면 [4, 6, 7, 8] 로
그러면 다시!
[1, 2, 3, 5] 과 [4, 6, 7, 8] 를 병합하면 [1, 2, 3, 4, 5, 6, 7, 8] 이 됩니다.
어떤가요? 문제를 쪼개서 일부분들을 해결하다보니, 어느새 전체가 해결되었습니다!
이를 분할 정복, Divide and Conquer 라고 합니다.
이렇게 동일한 형태로 반복되는 경우에는 어떤 코드가 생각나나요?
바로 "재귀" 적인 코드가 떠오릅니다.
자기 자신을 포함하는 형식으로 함수를 이용해서 정의해보면,
MergeSort(시작점, 끝점) 이라고 해볼게요.
그러면 MergeSort(0, N) = Merge(MergeSort(0, N/2) + MergeSort(N/2, N)) 라고 할 수 있습니다.
즉, 0부터 N까지 정렬한 걸 보기 위해서는
0부터 N/2 까지 정렬한 것과 N/2부터 N까지 정렬한 걸 합치면 된다. 라는 개념입니다.
아까 봤던 [1, 2, 3, 5] 와 [4, 6, 7, 8] 을 합치면 정렬된 배열이 나온 것 처럼요!
자, 이제 그러면 위의 생각들을 코드로 옮겨보겠습니다!
def merge_sort(array):
mid = (0 + len(array)) // 2
left_array = merge_sort(array[:mid]) # 왼쪽 부분을 정렬하고
right_array = merge_sort(array[mid:]) # 오른쪽 부분을 정렬한 다음에
merge(left_array, right_array) # 합치면서 정렬하면 됩니다!재귀 함수의 형태로 만들어졌습니다!
엇 그런데 재귀 함수의 필수 조건, 탈출 조건을 안 써줬네요!
어느 시점에 탈출하죠?
문자열의 길이가 1보다 작거나 같을 때,
무조건 정렬되었다고 볼 수 있을테니 (하나밖에 없으니까요!)
탈출시키도록 하면 됩니다!
def merge_sort(array):
if len(array) <= 1:
return array
mid = (0 + len(array)) // 2
left_array = merge_sort(array[:mid]) # 왼쪽 부분을 정렬하고
right_array = merge_sort(array[mid:]) # 오른쪽 부분을 정렬한 다음에
merge(left_array, right_array) # 합치면서 정렬하면 됩니다!이 개념을 가시고 한 번 병합정렬을 구현하러 가보겠습니다!
array = [5, 3, 2, 1, 6, 8, 7, 4]
def merge_sort(array):
if len(array) <= 1:
return array
mid = len(array) // 2
left_array = array[:mid]
right_array = array[mid:]
return merge(merge_sort(left_array), merge_sort(right_array))아직 조금 감이 안 온다면, 아래처럼 print 문을 사이사이에 넣어 출력해보세요!
array = [5, 3, 2, 1, 6, 8, 7, 4]
def merge_sort(array):
if len(array) <= 1:
return array
mid = len(array) // 2
left_array = array[:mid]
right_array = array[mid:]
print(array)
print('left_arary', left_array)
print('right_arary', right_array)
return merge(merge_sort(left_array), merge_sort(right_array))
# 출력된 값을 보면 다음과 같습니다!
# [5, 3, 2, 1, 6, 8, 7, 4] 맨 처음 array 이고,
# left_arary [5, 3, 2, 1] 이를 반으로 자른 left_array
# right_arary [6, 8, 7, 4] 반으로 자른 나머지가 right_array 입니다!
# [5, 3, 2, 1] 그 다음 merge_sort 함수에는 left_array 가 array 가 되었습니다!
# left_arary [5, 3] 그리고 그 array를 반으로 자르고,
# right_arary [2, 1] 나머지를 또 right_array 에 넣은 뒤 반복합니다.
# [5, 3]
# left_arary [5]
# right_arary [3]
# [2, 1]
# left_arary [2]
# right_arary [1]
# [6, 8, 7, 4]
# left_arary [6, 8]
# right_arary [7, 4]
# [6, 8]
# left_arary [6]
# right_arary [8]
# [7, 4]
# left_arary [7]
# right_arary [4]
함수의 시간복잡도 - 모든 단계에서 N 만큼 비교, 크기가 N → N/2 → N/2^2 → N/2^3 → .... → 1 (logN) -> O(NlogN)
스택(stack)
스택이란? - 한쪽 끝으로만 자료를 넣고 뺄 수 있는 자료 구조. LIFO
ex) 컴퓨터의 되돌리기 (ctrl + z)
스택의 구현
push(data) : 맨 앞에 데이터 넣기
pop() : 맨 앞의 데이터 뽑기
peek() : 맨 앞의 데이터 보기
isEmpty(): 스택이 비었는지 안 비었는지 여부 반환해주기
스택은 뭘로 구현하면 좋을까?
스택은 데이터 넣고 뽑는 걸 자주하는 자료 구조 -> 링크드 리스트와 유사한 방식!
class Node:
def __init__(self, data):
self.data = data
self.next = None
class Stack:
def __init__(self):
self.head = None
def push(self, value):
# 어떻게 하면 될까요?
return
# pop 기능 구현
def pop(self):
# 어떻게 하면 될까요?
return
def peek(self):
# 어떻게 하면 될까요?
return
# isEmpty 기능 구현
def is_empty(self):
# 어떻게 하면 될까요?
return
push - 새 데이터를 헤드로 만들고 원래 헤드를 다음으로 지정
def push(self, value): # 현재 [4] 밖에 없다면
new_head = Node(value) # [3] 을 만들고!
new_head.next = self.head # [3] -> [4] 로 만든다음에
self.head = new_head # 현재 head의 값을 [3] 으로 바꿔준다.
pop - 제일 위에 있는 데이터(head)를 다른 변수에 저장해 둔 다음 head 가 지칭하는 노드를 현재 head 의 다음값으로 지 정하고, 저장해둔 head 를 반환
def pop(self):
if self.is_empty(): # 만약 비어있다면 에러!
return "Stack is empty!"
delete_head = self.head # 제거할 node 를 변수에 잡습니다.
self.head = self.head.next # 그리고 head 를 현재 head 의 다음 걸로 잡으면 됩니다.
return delete_head # 그리고 제거할 node 반환
peek - 제일 위에 있는 노드를 주기 -> head 를 반환해주기만 하면 된다.
def peek(self):
if self.is_empty():
return "Stack is empty!"
return self.head.data
is_empty - head 가 None 인지 아닌지 여부를 반환
def is_empty(self):
return self.head is None
** 실제 코드에서는 파이썬의 list 를 이용해서 스택으로 사용한다
stack = [] # 빈 스택 초기화
stack.append(4) # 스택 push(4)
stack.append(3) # 스택 push(3)
top = stack.pop() # 스택 pop
print(top) # 3!
큐(queue)
큐란? - 한쪽 끝으로 자료를 넣고, 반대쪽에서는 자료를 뺄 수 있는 선형구조. FIFO
순서대로 처리되어야 하는 일에 필요하다.
큐의 구현
enqueue(data) : 맨 뒤에 데이터 추가하기
dequeue() : 맨 앞의 데이터 뽑기
peek() : 맨 앞의 데이터 보기
isEmpty(): 큐가 비었는지 안 비었는지 여부 반환해주기
데이터 넣고 뽑는 걸 자주하는 자료 구조 - 링크드 리스트와 유사하게 구현한다. 이 때, 큐는 스택과 다르게 끝과 시작의 노드를 전부 가지고 있어야 하므로, self.head 와 self.tail 을 가지고 시작
class Node:
def __init__(self, data):
self.data = data
self.next = None
class Queue:
def __init__(self):
self.head = None
self.tail = None
def enqueue(self, value):
# 어떻게 하면 될까요?
return
def dequeue(self):
# 어떻게 하면 될까요?
return
def peek(self):
# 어떻게 하면 될까요?
return
def is_empty(self):
# 어떻게 하면 될까요?
return
enqueue
def enqueue(self, value):
new_node = Node(value)
if self.is_empty(): # 만약 비어있다면,
self.head = new_node # head 에 new_node를
self.tail = new_node # tail 에 new_node를 넣어준다.
return
self.tail.next = new_node
self.tail = new_node
dequeue
def dequeue(self):
if self.is_empty():
return "Queue is empty!" # 만약 비어있다면 에러!
delete_head = self.head # 제거할 node 를 변수에 잡습니다.
self.head = self.head.next # 그리고 head 를 현재 head 의 다음 걸로 잡으면 됩니다.
return delete_head.data # 그리고 제거할 node 반환
peek
def peek(self):
if self.is_empty():
return "Queue is empty!"
return self.head.data
is_empty
def is_empty(self):
return self.list.head is None
해쉬
해쉬 테이블이란?
컴퓨팅에서 키를 값에 매핑할 수 있는 구조인, 연관 배열 추가에 사용되는 자료 구조이다. 해시 테이블은 해시 함수를 사용하여 색인(index)을 버킷(bucket)이나 슬롯(slot)의 배열로 계산한다. 데이터를 다루는 기법 중에 하나로 데이터의 검색과 저장이 아주 빠르게 진행된다.
ex) 파이썬의 딕셔너리 - 키로 데이터를 저장하고 찾을 수 있는 방법, 딕셔너리를 해쉬 테이블이라고 부르기도 한다.
dict = {"fast" : "빠른", "slow": "느린"}키를 통해 바로 데이터를 받아올 수 있으므로, 속도가 획기적으로 빨라진다.
해쉬 함수(Hash Function) - 임의의 길이를 갖는 메시지를 입력하여 고정된 길이의 해쉬값을 출력하는 함수이다.
파이썬에서 hash(object) 로 제공
>>> hash("fast")
-146084012848775433
>>> hash("slow")
7051061338400740146엇 그러면 이 값들을 이용해서 어떻게 배열에 넣을까요??
마이너스 값도 있고, 무지막지하게 큰 값도 있는데..
바로, 배열의 길이로 나눈 나머지 값을 쓰면 됩니다.
예를 들어 배열의 길이가 8이라면,
8로 나눈 나머지는 0~7이기 때문에
무조건 배열 내부의 인덱스로 연결될 것이라는 걸 알 수 있습니다!
그럼 이 개념을 가지고 한 번 간단하게 딕셔너리를 구현해보겠습니다.
딕셔너리에는 put과 get 함수가 필요합니다!
put(key, value) : key 에 value 저장하기
get(key) : key 에 해당하는 value 가져오기
class Dict:
def __init__(self):
self.items = [None] * 8
def put(self, key, value):
# 구현해보세요!
return
def get(self, key):
# 구현해보세요!
return
my_dict = Dict()
my_dict.put("test", 3)
print(my_dict.get("test")) # 3이 반환되어야 합니다!
put
키에 대해서 해쉬함수를 사용해서 임의의 숫자로 만든 뒤,
이걸 배열의 길이로 나눠 인덱스로 만들기로 했죠?
그러면 다음과 같이 하면 인덱스를 구할 수 있겠네요!
hash(key) % len(self.items)
이 값의 인덱스에 value 를 담기만 하면 됩니다!
def put(self, key, value):
index = hash(key) % len(self.items)
self.items[index] = value
get
해당 인덱스를 가진 items 의 원소를 반환해주기만 하면 됩니다!
def get(self, key):
index = hash(key) % len(self.items)
return self.items[index]
충돌(collision)
해쉬의 값이 같거나 혹은 해쉬 값을 배열의 길이로 나눴더니 똑같은 숫자가 되어 같은 어레이의 인덱스로 매핑이 되어서 데이터를 덮어 써버리는 결과
충돌을 해결하는 방법 - 체이닝(Chaining), 개방 주소법(Open Addressing)
충돌을 해결하는 첫번째 방법은 바로 링크드 리스트를 사용하는 방식입니다.
이 방식을 연결지어서 해결한다고 해서 체이닝(Chaining) 이라고 합니다!
fast 의 해쉬 값과 slow 의 해쉬 값이 동일하게 3이 나왔다고 해볼게요.
현재 3번째 인덱스에 현재 fast 와 slow 가 서로 가지겠다고 싸우고 있습니다.
그러면, 둘을 아예 연결해주는거에요! 이렇게요!
[None, None, (fast, "빠른") → (slow, "느린"), ... ]
아직 감이 안 오시죠?
이 데이터를 이용해서 개선된 딕셔너리를 만들면 느낌 오실거에요!
class LinkedTuple:
def __init__(self):
self.items = []
def add(self, key, value):
self.items.append((key, value))
def get(self, key):
for k, v in self.items:
if k == key:
return v이 자료 구조를 가지고, 기존 딕셔너리의 충돌을 해결하러 가 봅시다!
아래 형태와 같습니다.
class LinkedDict:
def __init__(self):
self.items = []
for i in range(8):
self.items.append(LinkedTuple())
def put(self, key, value):
# 구현해보세요!
return
def get(self, key):
# 구현해보세요!
return
이 새로운 자료 구조를 가지고, 기존 딕셔너리의 충돌을 해결하러 가 봅시다!
class LinkedDict:
def __init__(self):
self.items = []
for i in range(8):
self.items.append(LinkedTuple())
def put(self, key, value):
# 구현해보세요!
return
def get(self, key):
# 구현해보세요!
return
put 라는 함수 먼저 볼게요!
개선된 버젼에서는 각 index 마다 LinkedTuple 이 존재합니다.
즉, 해당하는 index 의 LinkedTuple 에 새로운 값을 추가해주기만 하면 됩니다!
def put(self, key, value):
index = hash(key) % len(self.items)
self.items[index].add(key, value)
# 만약, 입력된 key가 "fast" 인데 index 값이 2가 나왔다.
# 현재 self.items[2] 가 [("slow", "느린")] 이었다!
# 그렇다면 새로 넣는 key, value 값을 뒤에 붙여주자!
# self.items[2] == [("slow", "느린") -> ("fast", "빠른")] 이렇게!get 라는 함수도 구현해보겠습니다!
개선된 버젼에서 각 index 마다 LinkedTuple 이 존재합니다.
즉, 해당하는 index 의 LinkedTuple 에 값을 가져오기만 하면 됩니다!
def get(self, key):
index = hash(key) % len(self.items)
return self.items[index].get(key)
# 만약, 입력된 key가 "fast" 인데 index 값이 2가 나왔다.
# 현재 self.items[2] 가 [("slow", "느린") -> ("fast", "빠른")] 이었다!
# 그렇다면 그 리스트를 돌면서 key 가 일치하는 튜플을 찾아준다.
# ("fast", "빠른") 이 일치하므로 "빠른" 이란 값을 돌려주자!
충돌을 해결하는 두 번째 방법은 배열의 다음 남는 공간에 넣는 것입니다!
fast 의 해쉬 값이 3이 나와서 items[3] 에 들어갔습니다.
그런데 slow 의 해쉬 값이 동일하게 3이 나왔습니다.
그러면, items[4] 를 봅니다. 앗, 이미 차 있네요.
그러면 그 다음 칸인 items[5] 를 봅니다.
비어 있으니까 items[5] 에 slow 의 value 값을 넣는 방식을
개방 주소법(Open Addressing) 이라고 합니다! 이 방법은 따로 구현하지는 않겠습니다!
해쉬 - 2
정리
해쉬 테이블(Hash Table)은 "키" 와 "데이터"를 저장함으로써 즉각적으로 데이터를 받아오고 업데이트하고 싶을 때 사용하는 자료구조입니다.
해쉬 함수(Hash Function)는 임의의 길이를 갖는 메시지를 입력하여 고정된 길이의 해쉬값을 출력하는 함수입니다.
해쉬 테이블의 내부 구현은 키를 해쉬 함수를 통해 임의의 값으로 변경한 뒤 배열의 인덱스로 변환하여 해당하는 값에 데이터를 저장합니다.
그렇기 때문에 즉각적으로 데이터를 찾고, 추가할 수 있는 것 입니다.
만약, 해쉬 값 혹은 인덱스가 중복되어 충돌이 일어난다면?
체이닝과 개방 주소법 방법으로 해결할 수 있습니다!