어제의 나보다 성장한 오늘의 나

Trie ◎ 문자열들을 저장하기 위해 사용되는 트리 자료구조 ◎ 각 노드가 26개의 자식 포인터를 가짐 ◎ 빠른 문자열 탐색 속도 1) 작동 원리 문자열들이 저장되어 있는 Trie 의 모습이다. 저장된 문자열 [ rebro , replay , hi , high , algo ] 문자열 한 글자씩 노드에 저장 해두었고 끝나는 지점을 bool finish 변수를 통해 표시 해두었다. ( 빨간색 동그라미 부분 -> finish 변수 true) 문자열 탐색하는 과정 문자열 "High" 를 찾는 다고 가정을 해보겠다. 제일 꼭대기에 있는 Root 노드 에서 High의 첫 글자인 H를 먼저 찾는다. 자식 노드 들 중 H 노드가 존재하기에 H 노드로 이동 할 수 있다. 이동한 뒤 두 번째 글자인 I 를 찾는다. I 노..

Map STL 구현 우리는 Map STL을 코딩하면서 정말 많이 사용한다. Pair로 저장할 수 있고 , 자동으로 정렬이 되고 , 삽입 / 삭제가 빠르고, … 장점이 되게 많기 때문이다. 오늘은 Map STL을 C++로 구현 해보고 Map에서 사용 된 기능 , 그 구조에 대해서 알아볼 것이다. 한 마디로 Map STL을 완전 뜯어 볼 생각이다. 많은 공부가 될 것이다. Map STL 구현 Full Code Github 주소 : https://github.com/ohinhyuk/MCNL-Study/blob/main/%EA%B3%A0%EC%9C%A4%EB%AF%BC%EA%B5%90%EC%88%98%EB%8B%98%20%EC%8A%A4%ED%84%B0%EB%94%94/week%202/RedBlack%20Tre..

STL container 중 하나인 트리 중 Complete Binary Tree (완전 이진 트리)를 구현해보았다. 그리고 응용 함수들을 만들어 보았다. 구현 Struct struct TreeNode{ int key; // node 속 data 저장 TreeNode* left; TreeNode* right; TreeNode(int k, TreeNode* l , TreeNode* r){ key = k; left = l; right = r; } TreeNode(int k) : key(k), left(nullptr), right(nullptr){} ~TreeNode(){} }; using tree = TreeNode*; 기본 함수들 empty : 비어있다면 true 반환 , 아니면 false 반환. bool..

◎ next , prev 두개의 노드 포인터를 가지고 있다. ◎ Single Linked List에 비해 함수 처리가 더 용이하고 접근성이 더 뛰어나다. ◎ 맨 앞에는 head 노드 , 맨 뒤에는 tail 노드가 있다. ◎ 삽입 / 삭제가 빠르다. 구현 구조체 1) Node Struct struct Node{ int data; // data in Node. Node* prev; // pointing before Node. Node* next; // pointing after Node. }; using pNode = Node*; 2) List Struct struct List{ Node* head; // front of list. Node* tail; // end of list. List(){ head =..

Singly Linked List란? ◎ 단일 방향으로 노드들이 연결되어 있는 STL container 중 하나이다. ◎ 데이터를 가지고 있는 연결된 노드들의 맨 앞과 맨 뒤에는 Head , Tail 이름의 노드가 있다. ◎ 노드들은 모두 next라는 노드 포인터를 가지고 있어서 다음 노드와 연결 할 수 있다. 구현 ◎ Class 와 Struct를 사용하여 좀 더 깔끔한 코드를 구현하였다. ◎ Template 을 사용하여 int 뿐만 아니라 다른 Type의 자료형을 위한 Container로도 사용할 수 있다. Coding 1) 기본 구조 template struct Node{ T data; // Node 속 data 저장 Node* next = nullptr; }; template class Singli..

Heap 이란? ◎ complete binary tree (parent node는 2개의 child node를 갖는다.) ◎ parent 와 child 간에 항상 대소 관계가 성립 ◎ parent node가 child node 보다 항상 크면 max heap, 항상 작으면 min heap ◎ max heap일때는 최상위 node가 가장 크고 , min heap일때는 최상위 node가 가장 작다. ◎ array의 index는 1 부터 사용한다. ◎ child index는 (parent_index)*2 , (parent_index)*2+1 ◎ 반대로 parent index는 (child_index) / 2 1. heap 구현 Array를 이용하여 Maxheap을 구현해보았다. 변수 / 생성자 / 소멸자 pr..

c++ STL container 중 하나인 queue를 구현해봤다. 작동 원리 FIFO (First - In - First - Out) : 먼저 들어온 값이 먼저 나가는 구조. 알고리즘 ※ circular queue circular queue란 rear와 front라는 변수를 통해 array 저장 공간을 효율적으로 사용하는 queue 구현 방법이다. rear는 array 속에 있는 값 중 가장 최근 push된 값의 array index를 나타낸다. front는 array 속에 있는 값 중 가장 먼저 push된 값의 array index를 나타낸다. rear와 front를 잘 조절하면 queue가 empty 한 상태인지 queue가 full 한 상태인지 queue의 size는 몇인지 등등 queue의 상태..

c++ 에서 array를 이용하여 stack을 구현하기. c++의 STL 중 하나인 Stack Container를 구현해봤다. Stack의 동작 원리 -LIFO (Last in First Out) : 가장 마지막에 들어온 값이 가장 먼저 나갈 수 있는 형태이다. 반대로 가장 먼저 들어온 값은 가장 마지막에 나갈 수 있다. Stack의 함수 1) empty - stack이 비어있다면 true를 return, 아니라면 false를 return. 2) push - 값을 stack에 집어넣는다. 3) pop - 가장 최근에 들어온 값을 stack에서 빼낸다. 4) top - 가장 최근에 들어온 값을 return. 5) size - stack의 크기를 return. 가 있다. 구현한 코드 설명 1) empty 스..