Showing

1. Queue 개념과 구현 Queue는 시간 순서상 먼저 저장한 데이터가 먼저 출력되는 선입선출 FIFO(First In First Out) 형식으로 데이터를 저장하는 자료구조입니다. queue의 rear에 데이터를 추가하는 것을 enqueue라고 합니다. 또한 queue의 front에서 데이터를 꺼내는 것을 dequeue라고 합니다. 더블링크드리스트를 파이썬으로 아래와 같이 구현해보았습니다.(직접 구현한 것이므로 버그가 있다면 지적 부탁드립니다.) Array list로 구현한 큐는 선출할 때, O(n)의 시간복잡도가 걸리므로(배열 길이만큼 한칸씩 앞으로 땡겨주어야 함) O(1)로 처리가능한 링크드리스트로 구현하는 것이 좋습니다.(head 값만 바꿔주면 됨) class Node: def __init_..

* 이론을 토대로 직접 구현한 것이므로 버그가 발생할 수 있습니다. 버그 발생시 댓글 남겨주시면 감사하겠습니다. 1. 물리적 비연속적, 논리적 연속적 Linked List는 Node라는 구조체가 연결되는 형식으로 데이터를 저장하는 자료구조입니다. 각각의 요소(Node)가 데이터 값과 다음 요소를 가리키는 포인터(next node의 주소값)로 구성된 자료구조입니다. 각 Node들은 데이터를 저장할 뿐 아니라, next node의 addr 정보도 가지고 있기 때문에 논리적으로 연속성을 유지하면서 연결될 수 있습니다. Array의 경우 연속성을 유지하기 위해 메모리 상에서 순차적으로 데이터를 저장하는 방식을 사용하였지만, Linked lsit에는 메모리상에서 연속성을 유지하지 않아도 되기 때문에 메모리 사용이..

1. List 자료구조 vs Set 자료구조 Set과 List는 둘 다 선형자료구조이지만 중요한 차이점이 있습니다. (1) 중복된 요소 (2) 순서가 있는/없는 (3) 인덱스 기반 접근 (1) 중복 요소 - Set은 중복된 요소를 허용하지 않습니다. 각 요소는 유일해야 합니다. - List는 중복된 요소를 허용합니다. 동일한 요소가 여러 번 포함될 수 있습니다. (2) 순서 - Set은 인덱스 순서가 보장되지 않습니다. [1,2,3],[2,1,3], [3,1,2]가 각 인덱스와 값이 달라도 set에 들어가면 [1,2,3]으로 동일한 자료구조가 됩니다. 각 요소가 어떤 순서로 들어오든 상관없이 하나씩 존재한다는 점에서 모두 같은 set이 되는 것입니다. 요소들의 순서는 구현에 따라 다를 수 있습니다. - ..

1. 레드블랙트리 삭제로직 살펴보기 안녕하세요! FlyDuck Dev🦢입니다. 지난 포스팅에 이어서 레드블랙트리 삭제로직을 살펴보도록 하겠습니다. 참고 영상: https://youtu.be/lU99loSvD8s 2. 삭제로직 레드 블랙 트리에서 삭제연산을 진행할 때 크게 고려할 세가지 케이스는 -1- 왼쪽 차일드노드가 NIL일때, -2- 오른쪽 차일드노드가 NIL일때, -3- 양쪽 차일드노드가 모두 NIL이 아닐 때, 입니다. -1- 왼쪽 차일드노드가 NIL -2- 오른쪽 차일드노드가 NIL -3- 양쪽 차일드노드가 모두 NIL이 아님 (1) rbtree_erase 수도코드와 c코드를 살펴보겠습니다. int rbtree_erase(rbtree *t, node_t *z) { node_t *y = z; co..

1. 레드블랙트리 구현해보기 안녕하세요! FlyDuck Dev🦢입니다. 오늘은 레드블랙트리를 구현해보기 위해 삽입 로직을 정리해보고자 합니다. 레드-블랙 트리(Red-Black Tree)는 이진 탐색 트리(Binary Search Tree)의 일종으로, 검색, 삽입, 삭제의 연산에서 최악의 경우에도 시간 복잡도 O(log n)을 보장하는 자료구조입니다. 이를 위해 노드마다 "레드(red)" 또는 "블랙(black)"의 색을 지정하고, 색의 규칙에 따라 노드의 위치와 색을 조정함으로써 트리의 균형을 유지합니다. 레드-블랙 트리의 속성 모든 노드는 레드 또는 블랙 중 하나의 색을 갖습니다. 루트 노드는 블랙입니다. 모든 리프 노드(NIL 또는 NULL)는 블랙입니다. 레드 노드의 자식 노드들은 모두 블랙입니..