이전에 힙을 구현한적이 있는데 다시 정리해서 구현한 글입니다. 힙? 힙이란? '이진트리'이면서 '완전 이진트리'입니다. 힙은 max heap, min heap으로 나뉩니다. 중요한 점은 heap은 '완전 이진트리'라는 점입니다. 이진트리는 자식의 최대 개수가 두개인 트리의 형태를 의미합니다. 완전 이진트리는 마지막 레벨을 제외하고 모든 레벨이 완전히 채워져 있는 이진트리입니다. 트리에 대한 개념은 https://code-lab1.tistory.com/8

AVL 트리란? 이번글은 https://cjbworld.tistory.com/25 의 코드에 기반을 두고 확장하여 작성한 버젼입니다. 기존의 이진 탐색트리에서 탐색의 경우 "로그 시간복잡도를 보장해준다"라고 알고있는데 예외가 존재합니다. 바로 BST애 데이터를 삽입할 때 데이터들을 오름차순으로 삽입할 경우 트리의 모양이 요런식으로 되어 버려 탐색시 로그 시간복잡도가 안나온다는 것입니다... 선형시간 복잡도가 나오겠지용 그래서 이러한 문제점을 해결해주는 도구들이 바로 AVL 트리, 2-3-4트리, B트리, 2-3트리, Red-Black트리 등등이 있습니다. 이중에서도 AVL트리에 대해서 다뤄볼 것인데요. 이 AVL트리에는 위의 그림판 그림처럼 "균형"이 안맞는 상황을 위해 몇가지 개념이 추가가 됩니다. 바..

Heap? 힙이라는 자료구조를 알아보기 전에 먼저 "우선순위 큐"가 무엇인지 잠시 살펴보겠습니다. PQ(우선순위 큐)는 "들어간 순서에 상관없이 우선순위가 높은 데이터가 먼저 나오는" 특징을 가지고 있습니다. 즉, PQ는 데이터를 근거로 우선순위를 "판단"할 수 있어야 한다는 말입니다. 이 PQ를 구현을 할때 - 배열을 통해 구현 - 연결형 리스트를 통해 구현 - heap을 통해 구현 이렇게 세가지 정도로 볼 수 있습니다. 배열이나 연결형 리스트를 사용하면 PQ를 매우 간단히 구현할 수 있습니다. 하지만 이들은 PQ를 구현하는데에 있어서 그리 적합하지 않은데요 이유를 설명해드리도록 하겠습니다. 우선 "배열"의 경우 데이터의 우선순위가 높을 수록 배열의 앞부분에 데이터를 위치시킬 수 있습니다. 하지만 st..

간단한 사칙연산 계산기 구현입니다. C, C++을 통해서 계산기를 구현한 코드입니다. 먼저 알아야할 개념은 두가지 입니다. 1. 자료구조 스택 (LIFO) 2. 수의 중위 표기법, 전위 표기법, 후위 표기법 중위 표기법은 1+2*3 과같은 저희가 사용하는 수식입니다. 전위 표기법은 +1*23 후위표기법은 123*+ 입니다. 순서는 "Stack 자료구조 구현 => 중위 표현식을 후위 표현식으로 변경 => 후위 표현식을 계산" 입니다. 스택의 중위 => 후위로 변경할 때 사용하는 자료구조 입니다. 연산자의 우선순위가 높다면 스택에 쌓아두고 그렇지 않다면 현재 스택에서 pop() 을 진행한뒤 쌓아둡니다. 후위 표기법의 계산은 12+3*순일경우 앞에 있는 수 12를 차례대로 끄집어 낸다음 뒤에오는 '+' 연산자..