Tie up loose ends!

1. 버블 정렬 (Bubble Sort) - 두 인접한 데이터를 비교해서, 앞에 있는 데이터가 뒤에 있는 데이터보다 크면, 자리를 바꾸는 정렬 알고리즘 * 버블 정렬 시간 복잡도 : O(n^2) 2. 삽입 정렬 (Insertion Sort) - 해당 인덱스(key값) 앞에 있는 데이터(B)부터 비교해서 key값이 더 작으면, B값을 뒤 인덱스로 옮기는 정렬 알고리즘 * 삽입 정렬 시간 복잡도 : O(n^2) 3. 선택 정렬 (Selection Sort) - 주어진 데이터 중 최소값을 찾아 앞에 위치한 데이터와 교체하는 정렬 알고리즘 * 삽입 정렬 시간 복잡도 : O(n^2)

힙(Heap)은 최대값이나 최소값을 빠르게 찾기 위해 고안된 완전 이진 트리(Complete Binary Tree) 이다. 완전 이진 트리란 노드를 삽입할 때 최하단 왼쪽 노드부터 차례대로 삽입하는 트리를 말한다. 최대값을 구하기 위한 최대 힙(Max Heap)과 최소값을 구하기 위한 최소 힙(Min Heap) 으로 분류되고, 최대 힙의 경우 각 노드의 값은 해당 노드의 자식 노드가 가진 값보다 크거나 같고 최소 힙은 그 반대이다. 힙은 배열을 이용해 구현할 수 있고, 편의를 위해 0번 인덱스 대신 1번 인덱스를 루트 노드로 지정한다. 부모 노드 인덱스 번호 = 자식 노드 인덱스 번호 // 2 왼쪽 자식 노드 인덱스 번호 = 부모 노드 인덱스 번호 * 2 오른쪽 자식 노드 인덱스 번호 = 부모 노드 인덱..

트리(Tree)는 Node와 Branch를 이용해서 사이클을 이루지 않도록 구성한 데이터 구조로, 주로 최대 Branch 갯수가 2개인 이진 트리(Binary Tree)를 많이 사용한다. 이진 탐색 트리(Binary Search Tree, BST)는 이진 트리인 동시에 왼쪽 자식 노드는 해당 노드보다 작은 값, 오른쪽 자식 노드는 해당 노드보다 큰 값을 가지는 특징을 지닌다. 이 자료구조는 데이터 검색 속도에 강점을 가진다. * 이진 탐색 트리의 시간 복잡도 트리의 높이(Depth)를 ℎ 라고 한다면, 시간 복잡도는 O(ℎ) 이다. ℎ=𝑙𝑜𝑔𝑛 에 가까우므로, O(𝑙𝑜𝑔𝑛) 이라고 말할 수 있다. 하지만 아래와 같이 최악의 경우는 연결리스트(Linked List)와 동일한..

해쉬 테이블(Hash Table)은 키(Key)와 데이터(Value)를 저장하는 데이터 구조로, 키와 짝을 이루는 데이터를 빠르게 찾을 수 있는 특징이 있다. 해쉬(Hash)는 임의의 값을 고정 길이로 변환하는 것으로, 해쉬 함수(Hashing Function)을 통해 해쉬 값(Hash Value)을 산출할 수 있다. 즉 해쉬 테이블의 키를 해싱 함수로 연산해서 얻은 해쉬 값을 기반으로 데이터 저장 위치를 정하는 것이다. 해쉬 테이블은 배열처럼 미리 데이터 공간을 생성한 후 사용한다. 따라서 서로 다른 키들의 해쉬 값이 우연히 같을 경우, 같은 공간에 데이터를 저장해버리는 충돌(Collision) 문제가 발생할 수 있다. 따라서 이 문제를 해결하기 위한 여러가지 알고리즘들이 존재한다. 참고로 파이썬에서는..

배열(Array)은 순차적으로 연결된 공간에 데이터를 나열하는 구조인데 비해 연결리스트(Linked List)는 떨어진 곳에 존재하는 데이터를 포인터(Pointer)로 연결해서 관리한다. 따라서 연결리스트는 데이터와 다음 데이터의 주소를 가리키는 포인터를 하나의 저장 단위로 한다. 이 하나의 저장 단위를 노드(Node)라고 한다. 장점 - 배열처럼 데이터 공간을 미리 할당하지 않아도 됨 - 중간에 데이터를 추가/삭제시 연결을 위한 포인터 값만 바꾸면 되므로, 배열처럼 데이터를 옮겨줘야하는 작업이 불필요함 단점 - 데이터 뿐만 아니라 연결을 위한 데이터도 함께 관리해야 하므로 저장공간 효율이 좋지 않음 - 데이터가 메모리상에 순차적으로 저장된다는 보장이 없으므로 데이터 접근 속도가 느림 연결리스트의 종류로..