다양한 컴퓨터 지식 다양한 컴퓨터 지식

C++에서는 자료구조를 제공한다. map 자료구조는 key와 value 값을 하나의 데이터 묶음으로 저장하여 key 값을 통해 value값을 찾을 수 있도록 하는 자료구조이다. 이와 유사하게 C#에서는 자료구조를 제공하는데, 더 엄밀하게 말하면 dictionary 자료구조는 map이 아닌 hash map가 동일한 자료구조이다. hash map 자료구조는 C++에서 unordered_map으로 제공되고 있다. 그럼 map과 hash map의 차이점은 무엇일까? - map은 데이터가 red black tree로 구성되어 있다. 따라서 데이터의 삽입과 삭제에 걸리는 시간 복잡도는 O(logN)이다. - hash map은 hash table로 구성된 map 자료구조로, '메모리를 내주고 속도를 취하는' 방법으로..

병합 정렬은 '분할 정복'의 아이디어로 구현된 정렬 방법이다. 분할 정복 이란? 분할 : 문제를 단순하게 분할 정복 : 분할된 문제를 해결 결합 : 결과를 취합하여 마무리 3가지의 절차를 걸쳐 문제를 해결하는 것을 말한다. 따라서 병합 정렬은 가장 최소 단위까지 문제를 쪼개는 게 우선이며, 이 과정에서 재귀적인 함수 호출이 요구된다. 만약 6개의 숫자가 무작위로 나열되어 있다면, 함수의 재귀적 호출을 통해 해당 배열의 개수의 / 2 개로 계속해서 쪼갠 뒤, 쪼개진 배열에 정렬을 수행해준다. 더 이상 쪼개질 수 없는 상태가 되었을 때, 함수를 종료하게 된다. #include #include using namespace std; void MergeResult(vector&, int, int, int); vo..

힙 정렬은 힙 트리를 이용한 정렬 방법이다. 힙 트리는 우선순위 큐를 구현하는 데 사용되는 자료구조로, 힙 정렬에서도 우선순위 큐를 이용하면 간단하게 구현 가능하다. 1. 힙 트리 최대 힙의 경우, 최대값을 root로 두고 이진 트리를 구성하는 트리 구조. 부모 노드가 자식 노드의 값보다 무조건 큰 값을 갖는다. 최소 힙의 경우, 최대 힙의 경우와 반대이다. 부모 노드 접근 식 : (n - 1) / 2 n은 현재 노드의 인덱스 값으로, 힙 트리의 경우 이진 트리의 성질을 갖기 때문에 데이터 삽입 시, _heap.size() - 1 부터 시작하여 순차적으로 접근한다. left 노드 접근 식 : (n * 2) + 1 right 노드 접근 식 : (n * 2) + 2 데이터 삭제 시, 힙 트리의 경우 root..

직장생활 중 친구와 함께 effective C++ 스터디를 진행했고, 그에 대한 정리본이다. 일주일에 한 번씩 진행하느라 총 6개월 정도의 시간이 소요되었지만, 혼자하는 공부가 아니였기 때문에 더욱 꼼꼼히 공부할 수 있었다. 중간중간 의아하고 여전히 궁금한 내용들이 존재하지만, Effective C++을 공부하는 데 어려움을 겪는 사람들이 조금이나마 도움을 얻었으면 좋겠다. https://www.notion.so/Effective-C-b5fa08c0c24c4f3a9e6f80479a074685

레드 블랙 트리의 노드 삭제는 까다롭다. 레드 블랙 트리의 5가지 특성 중 마지막 요건을 맞춰줘야 하기 때문이다. 1. 노드는 레드 혹은 블랙 중 하나이다. 2. 루트 노드는 블랙이다. 3. 모든 리프 노드들(_nil)은 블랙이다. 4. 레드 노드는 연달아 나타날 수 없고 블랙 노드만이 레드 노드의 부모가 될 수 있다. 5. 어떤 노드로부터 시작되어 그에 속한 하위 리프 노드에 도달하는 모든 경로에는 리프 노드를 제외하면 모두 같은 개수의 블랙 노드가 있다. - 삭제할 노드의 색깔이 red인 경우 -> 해당 노드 삭제 * 해당 노드를 그저 삭제만 진행하는 것은 사실상 삭제할 노드의 색깔이 red이며 child 노드가 없는 경우이다. child 노드를 가진 노드의 경우, next 노드의 value 값과 삭..

https://ko.wikipedia.org/wiki/%EB%A0%88%EB%93%9C-%EB%B8%94%EB%9E%99_%ED%8A%B8%EB%A6%AC 레드-블랙 트리 - 위키백과, 우리 모두의 백과사전 위키백과, 우리 모두의 백과사전. 레드-블랙 트리(red-black tree)는 자가 균형 이진 탐색 트리(self-balancing binary search tree)로서, 대표적으로는 연관 배열 등을 구현하는 데 쓰이는 자료구조다. 1978년 ko.wikipedia.org 레드 블랙 트리는 이진 탐색 트리가 한쪽으로 치우쳐지는 것을 막기 위한 방법이다. 레드 블랙 트리의 특성으로는 다음이 있다. 1. 노드는 레드 혹은 블랙 중 하나이다. 2. 루트 노드는 블랙이다. 3. 모든 리프 노드들(_nil..

이진 트리란? -> 하위 노드로 최대 2개의 노드를 같은 트리를 말한다. 이진 탐색 트리 힙 트리는 최대 혹은 최소 값이 root 값인 반면, 이진 탐색 트리는 root 노드가 정해져 있지 않다. root 노드가 무엇인지에 따라 이진탐색트리의 시간복잡도가 상이하다. 이유는 이진 탐색 트리는 parent 노드를 기준으로 작은 값은 왼쪽, 큰 값을 오른쪽에 놓이기 때문이다. 따라서 최소값이나 최대값을 root 갑으로 지정할 경우 왼쪽 혹은 오른쪽으로 트리가 치우치게 되어 연결리스트와 동일한 시간 복잡도를 갖는 경우도 있다. ** 힙트리 - 최대 혹은 최소값을 root로 두고 왼쪽부터 차례로 이진 트리 생성 이진 탐색 트리 내장 함수 1. 데이터 삽입 : void insert(int value) - 데이터 삽..

https://www.notion.so/68b8229f15804792982324cb76e66f48 노션 주소 공유드립니다. 강의 자료는 인프런 운영체제 공룡책 무료 강의를 참조하였습니다. 강의 링크 공유드려요~ https://www.inflearn.com/course/%EC%9A%B4%EC%98%81%EC%B2%B4%EC%A0%9C-%EA%B3%B5%EB%A3%A1%EC%B1%85-%EC%A0%84%EA%B3%B5%EA%B0%95%EC%9D%98/dashboard