without haste but without rest

퀵 정렬(Quick Sort) 퀵소트는 반복문을 하나만 쓰기 때문에 시간복잡도 면에서 더 우수한 성능을 기대를 할 수 있다. 위 (이미지를 보다. 코드를 먼저 보는 게 더 나을 수도 있다. 보기와는 달리 정말 간단하다. 코드를 이해하면 이게 왜 빠를 수밖에 없는지 바로 이해된다.) gif 이미지에서 8을 첫번째 피벗으로 선택한다. 이때 작은 데이터와 큰 데이터를 구분하고 8의 왼쪽과 오른쪽에 붙인다. 다음으로 5를 선택하고 반복한다. (노란색이 피벗이다.) 포인트는 재귀(Recursive)를 사용한다는 것이다. 1. 배열에서 Pivot(기준점, 중심)을 정한다. 2. 피벗 보다 작은 데이터들은 left 리스트로, 큰 값은 right 리스트로 이동한다. 3. 이 과정을 재귀로 반복 시키면서 붙인다. #Qu..

삽입 정렬(Insrtion Sort) 삽입 정렬 역시 이중 루프로 구현할 수 있다. 가장 바깥 루프는 배열의 데이터를 순차적으로 선택하는 역할이며 안쪽 루프는 실질적으로 데이터를 비교하고 자리를 교체하는 역할을 수행한다. 1회 루틴 과정 -> 바깥 포 문은 배열의 인덱스를 오름차순으로 선택해 나간다. 이때 바깥 포문이 다음 데이터로 넘어가기 전에 안쪽 포 문은 현재 선택한 데이터를 배열 속에서 역방향으로 비교한다. 만약 이전 값이 현재 선택한 데이터 보다 큰 경우 두 데이터의 인덱스를 교체한다. 이를 반복한다. 위 이미지를 참고하면 쉽게 이해할 수 있다. #Insertion Sort def Insertion_Sort(array): for a in range(1, len(array)): for b in r..

선택 정렬(Selection Sort) 선택 정렬은 배열을 순회 하면서 현재 값보다 작은 값을 찾는 구조다. 위 이미지에서 8에서 시작하여 더 작은 값이 있는지 찾는다. 3이 가장 작으므로 0번 인덱스에 3이 온다. 이때 작은 값들이 오름차순으로 적재되는 것을 생각해야한다. 따라서 2회차부터는 1번 인덱스에서 시작한다. 이제 1번 인덱스인 41에서 순회를 시작한다. 바로 다음 숫자인 21이 더 작으므로 최소값을 담는 임시 변수는 21을 담는다. 다음으로 21과 3을 비교한다. 3이 더 작으므로 임시 변수는 3으로 교체한다. 그 뒤에는 3보다 작은 값이 없으므로 41의 자리인 1번 인덱스는 3으로 교체된다. #Selection Sort def selection_Sort(array): for a in ran..

버블 소트(Bubble Sort) 버블 소트는 배열에서 차례대로 두 데이터들을 비교한다. 이때 앞에 있는 숫자가 뒤에 있는 숫자보다 크다면 자리를 교체한다. 큰 숫자가 차례차례 뒤로 넘어가는 구조다. 한번의 순회가 끝나면 다시 처음부터 값들을 비교한다. 이를 반복하는 것이다. 특징으로는 한번 루틴을 돌 때 마다 가장 큰 값이 뒤로 가므로 비교해야 할 횟수가 줄어든다. 위 이미지에서는 최대 순회 횟수를 채우기 전에 데이터가 모두 정렬됐다. 즉 중간에 더 이상 비교할 필요가 없어졌다. 따라서 소스 코드 내에서 swap이라는 불리언 값을 주었다. 만약 한번의 순회를 거치는 동안 데이터간의 교체가 있는지 없는지를 체크하는 것이다. 교체가 없다면 정렬이 끝났다는 것이므로 반복문을 종료한다. 아래 코드에서 첫번째 ..

힙(Heap) 힙은 최대값과 최소값을 빠르게 찾기 위한 이진 트리다. 이진 탐색 트리(Binary Serach Tree)처럼 동일한 이진 트리라는 공통점이 있다. 하지만 트리와 힙은 다르다. 가장 큰 차이점은 힙의 경우 최대값이나 최소값이 루트 노드에 자리잡고 있다는 것이다. 또한 이진 탐색 트리의 경우 링크드 리스트 구조로 각 노드를 연결하는 반면 힙은 배열을 이용한다. 위 이미지의 구조가 트리였다면 level 2에 위치하는 3과 1은 왼쪽 노드에 존재해야한다. 하지만 힙은 삽입 데이터의 크기에 따라서 좌우 정렬을 하지 않는다. 목적 자체가 최소, 최대값을 빠르게 찾기 위함이기 때문에 최대값, 최소값을 루트 노드에 위치 시키는 것이 가장 중요하다. (위 이미지의 경우 최대 힙이므로 자식 노드는 부모 노..

트리(Tree) 트리는 노드(Node)와 브랜치(Branch)로 구성되어있다. 위 이미지에서 원이 노드, 화살표가 브랜치다. 각 노드들은 링크드 리스트 구조로 연결되어 있으며, 싸이클이 없다. 마지막 데이터에서 처음 데이터로 돌아오지 않는다. 아래 애니메이션을 보면 이진 탐색 트리 구조에서 데이터가 어떻게 삽입되는지 쉽게 이해할 수 있다. 21보다 작으면 왼쪽으로, 크면 오른쪽으로 이동한다. 그리고 다음 노드를 만나서 이 단계를 반복한다. 만약 더 이상 비교할 데이터가 없으면 해당 위치에 데이터가 삽입된다. 위 애니메이션에서 21은 루트 노드(Root Node)에 해당한다. 이 값을 기준으로 마치 나무의 가지가 뻗어 나가듯이 데이터가 추가된다. 이진 트리에서는 브랜치가 최대 2개이기 때문에 각 노드는 최..

클로즈 해싱(Close Hashing) 클로즈 해싱은 해시 테이블의 충돌 문제를 해결하는 방법 중 하나로 Linear Probing, Open Addressing 이라고 부르기도 한다. 구조는 간단하다. 위 이미지에서 John Smith와 Sandra Dee의 해시는 똑같이 873이다. 이때 먼저 들어온 John이 873이라는 해시를 먼저 키 값으로 취했고, 다음으로 들어온 Sandra는 바로 다음 값인 874를 키 값으로 가진다. 해시 중복이 발생하면 해당 해시 값부터 순차적으로 빈 공간을 찾기 시작한다. 가장 처음 찾는 빈 공간에 키와 밸류를 저장한다. 저장 효율을 높이는 방법이다. #close hashing class CloseHash: def __init__(self, table_size): se..

오픈 해싱(Open Hashing) 오픈 해싱은 해시 테이블의 충돌 문제를 해결하는 대표적인 방법중 하나로 체이닝(Separate Chaining) 기법이라고도 한다. 만약 해시 값이 중복되는 경우, 먼저 저장된 데이터에 링크드 리스트를 이용하여 중복 해시 데이터를 연결한다. 파이썬에는 굳이 링크드 리스트를 안 쓰고 슬롯을 이중 리스트 구조로 활용해서 간단하게 구현할 수 있다. # open hashing class OpenHash: def __init__(self, table_size): self.size = table_size self.hash_table = [0 for a in range(self.size)] def getKey(self, data): self.key = ord(data[0]) ret..