맵과 셋, 우선순위 큐는 항상 헷갈린다. 이번에 확실히 정리해 보자. Map, multi Map 맵은 기본적으로 레드-블랙 트리를 사용한 자료구조이다. key, value쌍을 가지며 key를 기준으로 오름차순 정렬하여 저장한다. 레드-블랙 트리로 구성되어 있으므로 항상 트리의 높이가 log n을 유지한다. 또, 중복을 허용하지 않고 multi Map만 중복을 허용한다. 맵은 주로 고유한 키와 값을 연결하여 정렬할 필요가 있을 때 사용한다. 또, 모든 값에 대해 빠른 접근과 삽입/삭제를 지원한다. Set, MultiSet 셋 또한 레드-블랙 트리를 사용한 자료구조이다. value 하나의 값만을 가지며 오름차순 정렬이 디폴트이며 중복을 허용하지 않는다. 셋은 고유한 값에 대한 정렬된 자료구조가 필요할 때 사..

해시테이블을 구현할 때 고민되는 부분이 몇 가지 있다. 해시 테이블 크기와 해시 함수이다. 먼저 해시 테이블 크기를 정해보자. 해시 테이블의 크기 해시 테이블에서 원소의 개수 / 테이블의 크기를 load factor라고 하고, 원소의 최대 개수는 곧 삽입의 최대 횟수이다. load factor를 작게 유지하면 충돌이 덜 생겨 연산들이 O(1)에 동작하겠지만 cache hit rate가 줄고 메모리를 많이 차지한다. 반대로 load factor를 크게 유지하면 충돌이 많이 생겨 성능에 악영향을 줄 수 있다. load factor를 정하는 방식은 체이닝 기법이냐 개방 주소화 기법이냐에따라 나뉜다. 먼저 체이닝 기법은 충돌이 어느 정도 발생하더라도 load factor를 1 이하로 둔다. 반면 개방 주소화 기..

일반적으로 효율적인 데이터의 저장 방법(직접 주소 테이블) 일반적으로 (key : value) 데이터를 기본 자료구조에 배치하면 탐색에 O(N)이 걸리거나 삽입/삭제에 O(N)이 걸린다. 가장 빠른 방법이 배열의 index로 key를 사용했을 때 탐색에 O(1) 시간이 걸린다. 그러나 key값의 종류가 대략 10^16 정도로 매우 많아지면 똑같이 배열로 구현할 수 있을까? 현실적으로 불가능하다. 혹은 key값이 최대 2000인데 실제 존재하는 key값은 0, 2000 뿐이라면 배열의 1~1999까지의 공간은 낭비된다. 이러한 문제들을 해시 테이블을 통해 해결할 수 있다. 해시 테이블이란? 해시 테이블은 임의의 길이를 가진 key값에 해시함수를 적용해 고정된 크기의 index를 생성하여 그 index에 값..

스택 스택은 가장 최근에 삽입된 원소가 삭제되는 LIFO구조이다. 스택의 top에서 원소의 삽입과 삭제가 일어난다. 스택에서 필수적으로 지원해야 할 메서드를 보자. ​ Stack-Empty Stack-Empty(S){ if(S.top==-1) return 1; else return 0; } Push Push(S, x){ S.top++; S[S.top] = x; } Pop Pop(S){ S.top--; return S[S.top+1]; } 큐 큐는 가장 먼저 삽입된 원소가 먼저 삭제되는 FIFO구조이다. 큐의 front에서 삭제가 일어나고 rear에서 삽입이 일어난다. 큐를 그냥 배열로 사용하게 되면 큐가 메모리에서 마치 빙하처럼 점점 이동한다는 문제점이 생긴다. 데이터의 삽입/삭제가 반복되면 인덱스가 감..

힙 최대 힙은 완전 이진트리이고, 부모가 항상 자식보다 큰 자료구조이다. 완전 이진트리란, 마지막 레벨을 제외하고 모든 레벨의 노드가 다 채워져 있고 마지막 레벨은 왼쪽부터 채워지는 트리이다. 최소 힙은 반대로 부모가 항상 자식보다 작다. 힙은 완전 이진트리의 특성상 부모와 자식의 index가 명확해서 배열을 사용한다. A[i]의 부모는 A [i/2]이고 왼쪽 자식은 A [2*i] 오른쪽 자식은 A [2*i + 1]이다. 힙은 힙 특성 유지하기(heapify), 힙 만들기(buildHeap), 삽입(insert), 삭제(delete)만 알면 된다. 힙 구현 힙 특성 유지하기(heapify) 배열 A에 대해 i번째 원소를 최대힙의 루트가 되게 한다. 아래는 퍼수도 코드이다. heapify(A, i){ l ..