반응형 자료구조23 Hash (양방향, 더미노드 2개, *head, *tail) 해당 게시글은 Chaining 기법을 Memory Pool 방식으로 구현한 내용입니다. Hash 구현에 있어서 중요한 것은 Hash Function을 통해서 key → Hash Index로 변환되는 결과에서 중복 Hash Index가 적게 발생하는 것이다. 즉, 충돌을 적게 발생시키는 것이 효율적인 Hash Function 이다. Hash Function을 잘 만든다면 충돌 처리를 할 필요는 없지만, 보장할 수 없는 경우라면 크게 Chaining 기법과 Open Address 기법으로 해결할 수 있다. ▶ [해시] Hash란? ▶ [해시] Hash Chaining 기법 구현 구조체 정보 struct Node { int id; Node* prev, * next; Node* alloc(int _id, Nod.. 2021. 6. 11. Hash (양방향, 더미노드 2개, head, tail) 해당 게시글은 Chaining 기법을 Memory Pool 방식으로 구현한 내용입니다. Hash 구현에 있어서 중요한 것은 Hash Function을 통해서 key → Hash Index로 변환되는 결과에서 중복 Hash Index가 적게 발생하는 것이다. 즉, 충돌을 적게 발생시키는 것이 효율적인 Hash Function 이다. Hash Function을 잘 만든다면 충돌 처리를 할 필요는 없지만, 보장할 수 없는 경우라면 크게 Chaining 기법과 Open Address 기법으로 해결할 수 있다. ▶ [해시] Hash란? ▶ [해시] Hash Chaining 기법 구현 구조체 정보 struct Node { int id; Node* prev, * next; Node* alloc(int _id, Nod.. 2021. 6. 10. Hash (양방향, 더미노드 1개, head) 해당 게시글은 Chaining 기법을 Memory Pool 방식으로 구현한 내용입니다. ▶ Hash (양방향, 더미노드 1개, *head) 구현방식과 비교하면 좋습니다. Hash 구현에 있어서 중요한 것은 Hash Function을 통해서 key → Hash Index로 변환되는 결과에서 중복 Hash Index가 적게 발생하는 것이다. 즉, 충돌을 적게 발생시키는 것이 효율적인 Hash Function 이다. Hash Function을 잘 만든다면 충돌 처리를 할 필요는 없지만, 보장할 수 없는 경우라면 크게 Chaining 기법과 Open Address 기법으로 해결할 수 있다. ▶ [해시] Hash란? ▶ [해시] Hash Chaining 기법 구현 구조체 정보 struct Node { int id.. 2021. 6. 9. Hash (단방향, 더미노드 0개, *head) 해당 게시글은 Chaining 기법을 Memory Pool 방식으로 구현한 내용입니다. ▶ Hash 구현 (양방향, 더미노드 0개, *head) 구현방식과 비교하면 좋습니다. 양방향이지 않기 때문에 이전 노드(prev)에 대한 구현 차이가 있습니다. 삭제될 때, 이전 노드(prev)에 해당하는 노드의 연결처리가 필요합니다. Hash 구현에 있어서 중요한 것은 Hash Function을 통해서 key → Hash Index로 변환되는 결과에서 중복 Hash Index가 적게 발생하는 것이다. 즉, 충돌을 적게 발생시키는 것이 효율적인 Hash Function 이다. Hash Function을 잘 만든다면 충돌 처리를 할 필요는 없지만, 보장할 수 없는 경우라면 크게 Chaining 기법과 Open Addr.. 2021. 6. 8. Hash (양방향, 더미노드 1개, *head) 해당 게시글은 Chaining 기법을 Memory Pool 방식으로 구현한 내용입니다. ▶ Hash 구현 (양방향, 더미노드 0개, *head) Hash 구현에 있어서 중요한 것은 Hash Function을 통해서 key → Hash Index로 변환되는 결과에서 중복 Hash Index가 적게 발생하는 것이다. 즉, 충돌을 적게 발생시키는 것이 효율적인 Hash Function 이다. Hash Function을 잘 만든다면 충돌 처리를 할 필요는 없지만, 보장할 수 없는 경우라면 크게 Chaining 기법 과 Open Address 기법으로 해결할 수 있다. ▶ [해시] Hash란? ▶ [해시] Hash Chaining 기법 구현 구조체 정보 struct Node { int id; Node* prev,.. 2021. 5. 28. [Hash] Hash 구현 (양방향, 더미노드 0개, *head) 해당 게시글은 Chaining 기법을 Memory Pool 방식으로 구현한 내용입니다. Hash 구현 (양방향, 더미노드 0개, *head) Hash 구현에 있어서 중요한 것은 Hash Function을 통해서 key → Hash Index로 변환되는 결과에서 중복 Hash Index가 적게 발생하는 것이다. 즉, 충돌을 적게 발생시키는 것이 효율적인 Hash Function 이다. Hash Function을 잘 만든다면 충돌 처리를 할 필요는 없지만, 보장할 수 없는 경우라면 크게 Chaining 기법과 Open Address 기법으로 해결할 수 있다. ▶ [해시] Hash란? [해시] Hash란? Hash란? 원소가 저장되는 위치가 원소 값에 의해 결정되는 자료구조 - 평균 상수 시간에 삽입, 검색,.. 2021. 5. 11. 원형 큐 (Circular Queue) 동적할당 + Memory Pool 방식 원형 큐 (Circular Queue) 원형 큐에 대한 개념이나 배열로 구현한 내용이 궁금하시다면 ▶ [큐] 원형 큐 (Circular Queue) [큐] 원형 큐 (Circular Queue) 원형 큐 (Circular Queue) 기본적인 Queue 구조는 push와 pop을 반복하다보면 Index (Rear)는 오른쪽으로 이동하게 된다. ▶ [큐] Queue란? [큐] Queue란? Queue란? 선입선출(First In First Out, FIFO)의 자료.. zoosso.tistory.com 구조체 형태 - 생성자, 소멸자, 삭제 멤버함수 구현 struct Node{ int data; Node* next; Node(){ // default constructor data = 0, next = NU.. 2021. 5. 7. [큐] Queue (Memory Pool 방식 구현) Queue (Memory Pool 방식 구현) Memory Pool 방식이란? 연결리스트를 정적할당한 형태로, 순차 리스트 + (동적) 연결리스트의 장점을 합친 형태 - 필요한 만큼 미리 확보해서 사용 (재활용 하지 않으므로 공간 해제 불필요) - 동적할당이 실제 메모리 공간에서 할당을 했다면 Memory Pool 방식은 초기에 일정 공간을 정적할당하고, 해당 공간을 필요할 때마다 포인터로 동적으로 연결해주는 방식 ▶ [List] 순차 리스트(정적 배열) & 연결 리스트(동적할당) 비교 [List] 순차 리스트(정적 배열) & 연결 리스트(동적할당) 비교 순차 리스트(정적 배열) & 연결 리스트(동적할당) 비교 List를 구현하는 방법에는 순차 리스트(배열), 연결 리스트 존재한다. ※ 관련 연산: 삽입.. 2021. 5. 2. [큐] Queue (동적할당, 연결리스트 구현) Queue (동적할당, 연결리스트 구현) 동적할당 방식 [큐] Queue란? 에서 배열(정적할당 방식)로 Queue를 구현하였다. 동적할당 방식은 초기에 메모리 공간을 정해두지 않고, 필요할 때마다 할당하는 방식이다. - 데이터 삽입, 삭제하는 경우 O(1)에 가능하다. - (최대 메모리 공간 내에서) 리스트 크기 제한이 없다. - 인덱스를 통한 임의 접근(random access)이 어렵다 따라서 특정한 원소를 탐색하는 경우 최대 O(N) 의 시간이 필요할 수 있다 - 일반적으로 자기 참조 구조체를 이용하여 구현한다. ▶ [List] 순차 리스트(정적 배열) & 연결 리스트(동적할당) 비교 [List] 순차 리스트(정적 배열) & 연결 리스트(동적할당) 비교 순차 리스트(정적 배열) & 연결 리스트(동.. 2021. 5. 2. [스택] Stack (Memory Pool 방식 구현) Stack (Memory Pool 방식 구현) Memory Pool 방식이란? 연결리스트를 정적할당한 형태로, 순차 리스트 + (동적) 연결리스트의 장점을 합친 형태 - 필요한 만큼 미리 확보해서 사용 (재활용 하지 않으므로 공간 해제 불필요) - 동적할당이 실제 메모리 공간에서 할당을 했다면 Memory Pool 방식은 초기에 일정 공간을 정적할당하고, 해당 공간을 필요할 때마다 포인터로 동적으로 연결해주는 방식 ▶ [List] 순차 리스트(정적 배열) & 연결 리스트(동적할당) 비교 [List] 순차 리스트(정적 배열) & 연결 리스트(동적할당) 비교 순차 리스트(정적 배열) & 연결 리스트(동적할당) 비교 List를 구현하는 방법에는 순차 리스트(배열), 연결 리스트 존재한다. ※ 관련 연산: 삽입.. 2021. 5. 2. 이전 1 2 3 다음 반응형
