Embedded Engineer (92) 썸네일형 리스트형 cin, cout and namespace cpp 프로그래밍 정리. std::cout cout은 c++의 표준 출력 스트림 객체이다. 프로그램에서 출력할 데이터를 자신과 연결된 스크린에 대신 출력해준다. c언어에서의 printf와 비슷한 기능이다. std::cout을 쓰기 위해서는 Matlab 기본 문법 -1 Matlab 기본 문법에 대해 공부하자 참조: https://matlabacademy.mathworks.com/ Self-Paced Online Courses - MATLAB & Simulink Learn MATLAB for free with MATLAB Onramp and access interactive self-paced online courses and tutorials on Deep Learning, Machine Learning and more. matlabacademy.mathworks.com matlab 은 프로그래밍 언어와 비슷하게 if, for, while등으로 흐름제어를 할 수 있는거 같다. 1. 명령 입력하기 이 파트에서는 특별히 기록할 만한것 없이 기본적인 연산에 대해 공부한다. .. Hash Table Chaining 구현 Hash Table의 Chaining을 구현 해보자 기존 Hash Table 에서 약간(?) 심화 과정으로써 Hash Table에서 Hash Key가 겹쳤을 경우를 처리하는 자료구조이다. 위와 같은 상황이 놓여졌을 때 Chaining으로 하여 값을 Insert 한다. Chaining은 Linked List로 구현하기 위해 Hash Table 구조체를 다음과 같이 수정하였다. typedef struct _storage { void *mem_slot_p; struct _storage *next_p; } Storage; typedef struct _hashTable { /* == hash table member == */ Storage **data_strge_pp; /* == hash table work fu.. Hash Table 구현 Hash Table을 구현해 보자 Hash Table 이란 자료를 저장하기 위한 여러가지 자료구조중 하나로 복잡도가 O(n) 이다. Hash Table을 대략 그림으로 표현 하면 다음과 같다. data 및 Hash key를 만드는 함수에 따라 Hash Key 가 중복 될수 있지만 추후 다루고 현재는 중복되지 않는다는 가정에 작업한다. Hash Table 에 자료를 저장할 변수는 void 형 이중 포인터로 한다. void로 한 이유는 저장 할 데이터 구조가 어떻게 저장하냐에 따라 저정할 데이터 구조가 매번 바뀌기 때문에 범용성을 위해 void 형을 사용 했고 저장하는 데이터 역시 데이터 자체를 저장하기 보다 데이터를 나타내는 포인터를 저장하기 위해 이중 포인터를 사용했다. 따라서 HashTable를 사용하.. AVL Tree 구현 AVL Tree를 구현해보자. AVL Tree는 이진 트리의 균형이 맞지 않을 때 탐색연산의 시간 복잡도가 O(log2n)아닌 O(n)에 가까운 시간 복잡도를 보이는데 이런 단점을 해결위한 트리중 하나이다. 위 그림을 봤을 때 왼쪽은 균형이 무너진 이진트리이고 오른쪽은 균형이 잡힌 이진트리이다. 5를 탐색한다고 했을 때 한눈에 봐도 성능차이가 난다는 것을 알 수 있다. AVL Tree는 균형이 무너졌는지 확인 후 균형을 맞추는 작업을 한다. 여기서 균형이 무너졌는지 확인 하는 방법은 균형 인수(Balance Factor)를 구하여 확인한다. 균형 인수 = 왼쪽 서브 트리의 높이 - 오른쪽 서브 트리의 높이 서브트리의 높이를 구하는 방법은 자식 노드를 가지고 있는 부모노드 의 갯수를 체크하여 높이를 확인한.. 이진탐색트리 Search 후 remove 구현 이진 탐색트리 삭제를 구현해보자 이진 탐색트리에서 search후 삭제를 할 때 다음 같은 상황이 있다. 1. 삭제할 노드의 자식 노드가 left 노드만 존재하는 경우 2. 삭제할 노드의 자식 노드가 right 노드만 존재 하는 경우 3. 삭제할 노드의 자식 노드가 양쪽 노드가 모두 존재하는 경우 4. 삭제할 노드의 자식 노드가 없는 경우 1. 삭제할 노드의 자식 노드가 left 노드만 존재하는 경우 위 그림에서 4의 자식노드는 left 노드만 있으므로 4를 삭제한다고 해보자 쉽게 판단 할 수 있듯이 4의 자식 노드를 8의 자식노드에 붙여 주면 끝이다. 4 노드를 삭제 후 8의 자식노드를 2에 연결 해주면 끝~!!! 2. 삭제할 노드의 자식 노드가 right 노드만 존재 하는 경우 삭제할 노드의 자식노드가.. 이진탐색트리 Insert, Search 구현 이진 탐색 트리를 구현해보자 이진 탐색 트리는 '이진 트리'에 '데이터의 저장 규칙'을 더해놓는 것이 '이진 탐색 트리'이다. 이진 탐색트리가 되기 위해서는 다음과 같은 조건이 필요하다. 1. 이진 탐색 트리의 노드에 저장된 키(key)는 유일하다. 2. 루트 노드의 키가 왼쪽 서브 트리를 구성하는 어떠한 노드의 키보다 크다. 3. 루트 노드의 키가 오른쪽 서브 트리를 구성하는 어떠한 노드의 키보다 작다. 4. 왼쪽과 오른쪽 서브 트리도 이진 탐색 트리이다. 앞에 언급한 키(key)는 탐색의 조건이 될 수 있으며 이번에 구현할 코딩에서는 데이터가 곧 key 값이 된다. 위 조건을 만족하는 트리를 그림으로 표현 하면 다음과 같다 (윤성우의 자료구조 참조) 위 그림을 통해 보면 다음 수식이 어디서나 만족함을.. Radix 정렬 구현 기수 정렬을 구현해보자 기수 정렬의 가장 큰 특징은 "정렬 순서상 앞서고 뒤섬의 판단을 위한 비교연산을 하지 않는다" 기본적으로 정렬 알고리즘의 이론상 성능의 한계는 O(nlog2n)으로 알려져 있는데 기수 정렬은 이러한 한계를 넘어설 수 있는 유리한 알고리즘이다. 다만 기수정렬의 단점은 범위가 매우 제한 적이다. 위에서 말하는 단점, 즉 범위의 정확한 뜻은 '데이터의 길이' 이다. 왜 데이터의 길이가 문제인가 하면 저장하는 버퍼, 즉 버킷의 갯수의 영향을 미치며 데이터 길이에 따른 별도의 알고리즘이 들어가야 한다. 별도의 알고리즘이 들어가면서 까지 기수 정렬은 효율적이지 않기 때문에 실제 사용하는 자료구조에서는 기수정렬을 많이 사용하지 않는다. 다음 그림은 한자릿 수의 기수정렬을 보여준다. 원리는 간단.. 이전 1 2 3 4 5 ··· 12 다음
