CEO

이진 탐색 트리를 구현하기 위해, 구글에 여러 코드들을 보았지만, 데이터 타입에 상관없이 사용할 수 있는 코드는 없었다. 이에 이진 검색 트리의 동작 원리나 이해보다는, 구현을 중점으로 글을 정리해보고자 한다. BST? Binary search tree - Wikipedia From Wikipedia, the free encyclopedia Jump to navigation Jump to search Data structure in tree form sorted for fast lookup A binary search tree of size 9 and depth 3, with 8 at the root. The leaves are not drawn. In computer science, a binary s..

해시에 대한 개념보다는 C로 해시를 구현하고, data type에 자유롭게 사용할 수 있도록 구현적 측면에서 해시를 다루고자 한다. key-value pair를 구조체에서 별도로 명시하지 않고, entry에 다른 구조체를 포인팅함으로써 더 많은 자료를 다룰 수 있도록 구현하였다. Hash? 해시는 위의 그림과 같이, key 값을 생성하는 `해시 함수(hash function)`를 통해 배열에 어떤 값이 있는지 즉각적을 찾을 수 있는 자료구조이다. 트리의 경우 한쪽으로 탐색을 하여 범위를 좁혀가면서 탐색을 한다. 하지만 해시의 경우 해시 함수를 통해, 찾고자 하는 값의 key를 즉각적으로 알 수 있으므로 탐색에 매우 효율적인 자료구조이다. 하지만 해시에서도 문제점은 있다. `충돌(Collision)`이 발..

정렬 방식 자주 사용하는 정렬 방식은 크게 2가지로 나눌 수 있다. 첫 번째로 2중 반복문을 사용하는 Bubble, Select, Insert 정렬이다. 두 번째는 분할-정복 방법을 사용하는 병합, 퀵 정렬이다. 2중 반복문을 사용하는 정렬 방식 해당 방식은 최악의 경우 시간복잡도는 O(N^2)이 된다. 이와 같은 이유는 2개의 반복문을 통해 값을 비교하기 때문이다. Bubble Sort 서로 인접한 두 원소를 검사하여 정렬하는 방식을 사용한다. swap이 더 이상 발생하지 않으면, 중단하여 불필요한 반복문을 실행하지 않을 수 있다. def bubble_sort(nums): for i in range(len(nums)): swap = False for j in range(1, len(nums)): if ..

그래프 탐색 방법 그래프를 탐색하는 방법중 DFS(Depth First Search와 BFS(Breadth First Search)를 간단한 예시를 통해 이해하고자 한다. 두 방식은 각각 Stack과 Queue를 통해 구현할 수 있으며, 그래프 방문 여부를 체크하여 중복으로 탐색하는 것을 방지하여야 한다. 그래프를 코드로 나타내기 그림 1의 그래프에 대한 노드 정보를 코드로 나타내면 다음과 같다. graph = { 'A': ['B', 'C'], 'B': ['A', 'D'], 'C': ['A', 'E', 'F'], 'D': ['B', 'G'], 'E': ['C', 'H'], 'F': ['C'], 'G': ['D'], 'H': ['E'], } DFS 그림 2는 루트 노드를 시작으로 모든 그래프 경로를 탐색하..

Recursion? 재귀는 특정 함수 내에서 함수 자신을 다시 호출하는 것을 의미한다. 재귀는 Stack의 특성을 그대로 반영하여, 가장 최근에 호출된 함수 부터 처리되는 방식으로 진행된다. 재귀를 잘 다룰 수 있다면 DFS와 백트래킹, 트리 탐색과 같은 문제를 해결 할때 효율적으로 접근할 수 있게 된다. 이진 트리 순회 그림 1과 같은 이진 트리가 있을 경우, 3가지 방식으로 트리를 순회할 수 있다. 첫 번째는 전위 순회로 1-2-4-5-3-6-7 순서로 트리를 순회한다. 두 번째는 중위 순회로 4-2-5-1-6-3-7 순서로 트리를 순회 한다. 마지막으로 후위순회는 4-5-2-6-7-3-1로 순회한다. 트리를 순회하는 것은 재귀 호출을 통해서 구현 할 수 있다. Simple Tree Travel de..

Linked List? 단순한 선형 배열(리스트)을 선언하면 메모리를 연속적으로 할당한다. 만약, 배열 내의 값 삭제가 필요하거나 추가가 필요한 경우 값들의 자리 교체가 필요하다. 이와 달리 연결 리스트는 연속적인 공간을 사용하지 않고, 각각의 노드들을 연결한 구조로 연결되어 중간의 값 삭제가 빈번하게 일어나는 자료를 관리하기에 보다 효율적이다. Single Linked List class Node: def __init__(self, data): self.data = data self.next = None class SingleLinkedList: def __init__(self, data): self.head = Node(data) def add(self, data): node = self.head w..

Queue? 가장 처음에 삽입된 데이터를 먼저 뺄 수 있는 방식(First in First Out) 형식의 자료구조 Queue의 연산 enqueue(data) : data를 Queue의 가장 마지막에 추가한다. dequeue() : Queue의 가장 최근에 추가된 data를 제거하고 반환한다. peek() : pop()과 달리 가장 최근에 추가된 data를 반환하고, 제거하진 않는다. is_empty() : pop()을 수행하기 위해서는 추가된 data가 존재하여야 하는데 이를 판별하기 위함이다. Queue를 활용하는 경우 선입선출이 필요한 경우 프로세스 관리, 우선순위 대기열, 프린터 출력 처리 등 BFS 구현 Queue의 선입선출 방식을 통해 BFS를 구현할 수 있다. DFS의 경우 Stack을 사용..

Stack? 가장 마지막에 삽입된 데이터를 먼저 뺄 수 있는 방식(Last in First Out) 형식의 자료구조 Stack의 연산 push(data) : data를 stack의 가장 마지막에 추가한다. pop() : stack의 가장 마지막에 추가된 data를 제거하고 반환한다. peek() : pop()과 달리 가장 최근에 마지막의 data를 반환하고, 제거하진 않는다. is_empty() : pop()을 수행하기 위해서는 추가된 data가 존재하여야 하는데 이를 판별하기 위함이다. Stack을 활용하는 경우 재귀 호출 재귀적으로 함수를 호출하는 경우, 가장 마지막에 호출된 함수 부터 차례로 실행결과를 반환한다. 따라서 재귀 호출의 경우 Stack을 통해 이를 가능하도록 한다. 수식의 괄호 검사 (..