반응형 노트/CS 노트11 [CS 노트] : Hash table에서 Collistion 해결하기 Hash table에서 Collision 해결 방법은? 대표적인 방법으로 2개가 있다. open addressing 충돌 발생 시 규칙에 따라 table의 비어있는 slot을 찾는다. slot를 찾는 방법은 3가지가 있다. Linear Probing Quadratic Probing Double Hashing separete chaining linked list를 사용한다. 충돌 발생 시 노드(slot)을 추가해 데이터를 저장한다. Open addressing 충돌이 발생하면 규칙에 따라 table의 비어있는 slot을 찾는다. linked List나 tree를 사용하지 않는다. 때문에 separate chaining에 비해 메모리를 적게 사용한다. Linear Probing, 선형 조사법 충돌이 발생한 .. 2022. 4. 9. [CS 노트] : Hash table에 대해서 Hash table이란? 효율적인 탐색을 위한 자료구조로 key-value 쌍의 데이터를 입력받는다. Hash function h에 key값을 넣어 얻은 해시값h(k)를 위치로 지정해 키,벨류 데이터 쌍을 저장하고 저장,삭제,검색의 시간복잡도는 O(1)이다. Direct address table를 미리 알아보자 직접 주소화 테이블은 Key 값을 index에 저장하는 방식인데 문제는 메모리 공간이 낭비된다. 예를 들면 key 값이 1000부터 시작하면 1부터 999까지는 비어 있게 된다. 또, 다양한 자료형을 담을 수 없다는 문제도 있는데 String으로 들어온 경우 Key 값을 바로 index로 사용하는 특성상 활용이 불가능하다는 문제가 있다. 이런 단점을 보완하는 게 Hash table이다. Hash .. 2022. 4. 8. [CS 노트] : 이진 탐색 트리에 대해서 이진 탐색 트리 BST, 이진 탐색 트리 이진 탐색 트리는 정렬된 트리로 왼쪽 자식 노드는 부모 노드보다 작은 값을, 오른쪽 자식 노드는 부모 노드보다 큰 값을 가지고 있는 구조이다. 이진 탐색 트리의 시간 복잡도는 모두 O(logn)이고 worst case인 경우 즉, 한 쪽으로 치우친 트리가 되었을 경우에만 O(n)이 된다. 이진 탐색 트리로 조회를 할 경우엔? 조회하는 데이터를 루트 노드와 비교하고 작으면 왼쪽, 크면 오른쪽으로 보낸다. 이것을 반복해서 쭉 내리고 값이 같은 경우를 찾으면 된다. 이 과정이 O(logn)의 시간 복잡도가 걸리게 된다. 이진 트리는? 이진 트리는 모든 노드의 자식 노드의 수가 2 이하인 트리를 이진 트리라고 한다. 이진 탐색 트리의 worst case 이진 탐색 트리는.. 2022. 4. 6. [CS 노트] : Queue와 Priority Queue 비교 Queue와 Priority Queue를 비교하라 큐는 먼저 들어간 데이터가 먼저 나오는 형식이고 우선순위 큐는 들어간 순서와 상관없이 우선순위가 높은 데이터가 먼저 나오게 된다. 때문에 큐의 push, pop의 시간 복잡도는 O(1)이지만 우선순위 큐의 push, pop의 시간 복잡도는 O(logn)이 된다. 우선순위 큐와 힙 우선순위 큐는 Heap과 같다고 볼 수 있다. 힙은 완전이진트리 구조이다. 이 힙은 Max Heap과 Min Heap이 있다. Max Heap은 각 노드에 저장된 값이 자식 노드의 값 보다 크거나 같아야 하고 Min Heap은 반대로 각 노드의 저장된 값이 자식 노드의 값보다 작거나 같아야한다. 힙은 트리 구조로 이루어져 있고 트리는 보통 Linked List로 구현하지만 힙은 .. 2022. 4. 2. [CS 노트] : Queue 2개를 사용해 Stack을 구현하라 두 개의 큐를 사용해 하나의 스택을 구현하려면 데이터가 두 개의 큐를 잘 왔다갔다 하게 만들면 된다. 1-2-3-4순으로 넣고 역시 FIFO이기 때문에 1-2-3-4순으로 나온다. 하지만 여기서 다 빼지 않고 1-2-3까지만 빼고 다른 큐에 넣어두고 4를 남겨두는 것이다. 그럼 A큐에는 4만 있고 B큐에는 1-2-3이 있는 상태인데 이때 A큐의 4를 POP해주면 된다. 이런 방식을 반복해서 하면 큐 2개로 스택을 구현하는 것과 같게 되는 것이다. 기출로 대비하는 개발자 전공면접 [CS 완전정복] 을 참고해서 공부하였습니다. 2022. 4. 1. [CS 노트] : Stack으로 Queue를 구현하기 두 개의 Stack를 통해 Queue를 구현할 수 있다. 데이터를 종이컵이라고 생각하고 종이컵 쌓기로 설명을 해 본다. 종이컵1,2,3,4를 A스택과 B스택을 사용해 큐를 만들어야 한다. 먼저, 큐는 종이컵이 1-2-3-4로 들어가고 1-2-3-4로 나오게 된다. 스택으로 큐를 구현하는 방법은 간단하다. 먼저 A스택에 종이컵을 push하여 1-2-3-4순서대로 넣는다. 그리고 다시 A스택에 있는 종이컵을 POP하여 B스택에 PUSH를 해 준다. 그럼 A스택에서 종이컵4가 먼저 나오게 되고 B스택에는 종이컵4가 맨 아래에 들어간다. 그 다음은 종이컵3이 pop되고 B스택에서는 종이컵3이 PUSH된다. 결국 B스택에는 종이컵4-3-2-1 순서로 쌓이게 되고 이 상태에서 pop을하면 1-2-3-4 순서대로 나.. 2022. 3. 31. [CS 노트] : Queue에 대해서.. Queue가 무엇인가? 큐는 FIFO(선입선출)의 자료구조이다. 시간복잡도는 enqueue(데이터 넣기), dequeue(데이터 빼기) 둘 다 O(1)이다.(맨 뒤에서 데이터를 넣고, 맨 앞에서 데이터를 빼기 때문이다.) 보통 Cache 구현이나 프로세스 관리, 너비우선탐색(BFS) 등이 있다. 구현 방식은 Array Based queue와 List Based가 있다. Array Based queue는 메모리를 넣고 빼다 보면 메모리 낭비가 발생하게 되고 이것을 방지하기 위해 Circular queue 형식으로 구현하게 된다. FIFO가 맨 뒤에서 넣고 맨 앞에서 빼내게 되는데 앞 칸에서 데이터를 빼내고 난 뒤에 당겨지지 않아 앞에 빈 메모리 공간이 생기게 된다. 이게 많아지면 결국 메모리 낭비가 되는데.. 2022. 3. 30. [CS 노트] : Array와 Linked List를 비교하면 어떤가? Array는 연속적으로 데이터를 저장하고 Linked List는 Node로 이루어져 있어 각 노드가 다음 노드를 가리키고 있어 논리적으로 연속적인 데이터 구조이다. 때문에 조회나 삭제 시 시간 복잡도가 다른데 데이터 조회는 Array는 O(1), Linked List는 O(n)으로 Array가 빠르고 삽입이나 삭제는 Array는 O(n), Linked List는 O(1)로 Linked List가 더 빠르다. 기출로 대비하는 개발자 전공면접 [CS 완전정복] 을 참고해서 공부하였습니다. 2022. 3. 29. [CS 노트] : Linked List에 대해서.. Linked List는 tree, graph 등 다른 자료 구조를 구현할 때 사용되는 기본적인 자료구조로Node 구조체로 이루어져있으며 이 Node는 다음 Node의 주소 값을 가지고 있다. Linked List는 물리적인 메모리에서는 비연속적으로 저장되자만 Node의 특성(다음 Node의 주소를 가지고 있음)을 통해 논리적인 연속성을 가지게 된다. Linked List는 데이터가 추가될 때 메모리를 할당한다. 즉, 메모리를 좀 더 효율적으로 사용할 수 있는 장점이 있다. Node는 다음 주소 값을 가지고 있는데 첫 번째 노드는 head라는 포인터로 가리키고 있고 마지막 노드가 가리키는 주소는 NULL을 표시한다. Array 처럼 메모리 연속성을 유지하지 않아도 되므로 메모리 사용이 자유로운데 다음 주소.. 2022. 3. 28. [CS 노트] : Dynamic Array에 대해서.. Dynamic Array는 저장 공간이 가득차면 가변적으로 사이즈를 조절하여 데이터를 저장하는 자료 구조로 저장 공간이 고정되어 있는 Static Array의 한계를 보안하기 위해 만들어졌다. 기존에 선언된 데이터 크기만큼 저장을 하다가 메모리를 초과하게 되면 resize가 발생되고 새롭게 확장된 크기의 배열을 생성해 데이터를 모두 옮긴다. 이와 같은 점이 장점으로 미리 사이즈를 고민할 필요가 없다. resize를 하는 대표적인 방법은 Doubling이 있다. 이 Doubling은 데이터를 추가하다 메모리가 초과하면 기존 크기의 두배 크기의 배열을 선언하고 데이터를 옮기는 방법이다. 기출로 대비하는 개발자 전공면접 [CS 완전정복] 을 참고해서 공부하였습니다. 2022. 3. 27. [CS 노트] : Array에 대해서.. Array는 메모리에 연속적이고 순차적으로 미리 할당된 크기만큼 저장하는 자료 구조이다. Array는 고정된 저장 공간과 데이터를 순차적으로 저장하는 특징이 있고, lookup(검색할 범위에서 값을 찾은 뒤 출력 등)과 append(추가 작업)가 빨라 조회하는 작업에서 유리하다. Array는 고정된 저장 공간을 가지고 있어서 메모리 낭비가 발생할 수 있고 반대로 Overhead가 발생할 수도 있는 문제를 가지고 있다. Overhead가 발생했을 때 선언된 크기보다 더 큰 값으로 Array를 선언하고 데이터를 옮겨주면 된다.(Dynamic Array) 근데 만약, 처음부터 데이터의 크기를 예측할 수 없을 떄에는 Array를 사용하지 말고 Linked List를 사용하면 된다. 기출로 대비하는 개발자 전공면.. 2022. 3. 26. 이전 1 다음 반응형