반응형 자료구조6 Red-black Tree 유명한 알고리즘인 Red Black Tree에 대해서 알아보자 복잡도는 다루지 않을 것이며 삽입 과정만 다루겠다 Red Black Tree를 이해하기 위해선 2-3-4 트리의 이해가 우선적으로 되어야지 조금 쉽다. 왜냐하면 2-3-4 트리의 단점을 극복하기 위해 제안된 것이 Red-Black Tree 이기 떄문이다. Red = 다수의 노드, black은 보통 이라고 임의로 정의한다 Red Black Tree는 3가지 핵심 규칙이 있다. 1. Root node는 모두 black이다. 2. Root에서 외부노드(끝)까지의 경로 상에는 연속된 2개의 Red node가 포함되지 않는다. 3. 루트에서 각 외부 노드까지의 경로에 있는 Black node의 수는 모두 같다. 그리고 Red-Black Tree는 Bi.. 2021. 10. 22. Linked List - C와 Python 비교 - 개념 Linked List는 말 그대로 연결된 리스트를 말한다. 지금까지의 큐와 스택 등은 모두 배열 구조로 구현하였지만 이를 연결된 자료구조로 변환하겠다. 연결을 위해선 node의 구현이 필요하고 이 노드는 데이터와 함께 링크를 갖는다. 각 항목은 다음 노드를 가르키는 링크를 가져서 이를 연결시켜주면 되는 방식이다. 이 연결의 개념을 통해 더욱 복잡한 트리나 그래프와 같이 더 복잡한 구조도 효율적으로 표현할 수 있다. 또한, 용량이 고정되지 않아서 메모리를 효율적으로 활용할 수 있다. 또한, 중간에 자료를 삽입하거나 삭제하는 것이 용이하다. 하지만 이의 단점은 n번째 항목에 접근하는데의 시간복잡도는 O(n)이라는 것이다. 그리고 배열구조에 비해 상대적으로 구현이 어렵다는 점이다.(오류도 빈번) 연결리스트의 .. 2020. 7. 15. queue - 3 우선순위 큐에 대해 구현해보자. 보통 우선순위 큐는 heap정렬 알고리즘을 이용해 구현하지만 heap을 이용하지 않고 우선순위 큐를 구현해보겠다. 우선순위 큐란 모든 데이터가 우선순위를 가지고 있고 들어온 순서와 상관없이 우선순위가 높은 데이터가 먼저 출력되는 구조이다. 즉 내림차순 정렬이라고 생각하면 된다. 우선순위 큐는 어떤 요소가 먼저 삭제되는가에 따라 최대 우선순위 큐와 최소 우선순위 큐로 나누어진다. 보통은 최대 우선순위 큐를 사용한다.(우선순위 높은 데이터가 먼저 삭제되는) 우선순위 큐는 다른 큐들과 다른 점이 일렬로 나열되어 있지 않다는 것이다. 우선순위 큐는 한 순간에 가장 우선순위가 높은 항목만 알 수 있으면 된다. 이를 heap이 아닌 list를 통해 구현해보겠다. class Prior.. 2020. 7. 15. Stack - C와 Python 비교(2) 스택의 예시로 많이 쓰는 것은 괄호 검사기이다. 프로그래밍을 하다보면 insert가 눌려져서 괄호가 하나씩 없거나 많아서 오류난 경험이 한 번 씩은 있을것이다. 이를 검사하는 프로그래밍을 할 것이다. 일단 C로 한 번 구현해보겠다. #include #include #define MAX_STACK_SIZE 100 typedef int element; typedef struct { element data[MAX_STACK_SIZE]; int top; }StackType; void init_stack(StackType* s) { s->top = -1; } int is_empty(StackType* s) { return (s->top == -1); } int is_full(StackType* s) { retur.. 2020. 7. 3. Stack - C와 파이썬 비교(1) 스택은 자료구조의 기본이라고 할 수 있다. 스택의 특징은 후입선출(LIFO)이다. 즉, 마지막에 들어간 것이 처음에 나온다고 생각하면 된다. 스택의 말 뜻처럼 쌓는다고 생각하면 편하다. 예를 들어 밑넓이는 좁고 높이가 긴 직육면체의 상자가 있다 생각해보자. 여기에 물건을 넣었을 때 맨 밑의 물건을 꺼내기 위해선 안에 있는 모든 물건을 빼야한다. 스택은 이런 것이다. 자세한 것은 밑의 링크를 참조하면 된다. https://ko.wikipedia.org/wiki/%EC%8A%A4%ED%83%9D 스택 - 위키백과, 우리 모두의 백과사전 위키백과, 우리 모두의 백과사전. 스택(stack)은 제한적으로 접근할 수 있는 나열 구조이다. 그 접근 방법은 언제나 목록의 끝에서만 일어난다. 끝먼저내기 목록(Pushdo.. 2020. 7. 3. 파이썬 리뷰 http://www.yes24.com/Product/Goods/89141599 파이썬으로 쉽게 풀어쓴 자료구조 입문자들이 보다 쉽고 재미있게 자료구조를 공부하고 다양한 문제 해결에 활용할 수 있는 능력을 기르는데 초점을 맞추어 구성한 책이다. 지루하지 않고 내용을 보다 쉽게 이해할 수 있도록 적� www.yes24.com 이 책의 답지가 없으므로 이 책의 실습 문제를 선택적으로 풀어보겠다. 데이터 분석과는 크게 상관없는 것 같지만 자료구조는 프로그래밍의 기본이므로 하는 것이 좋다고 판단하여 이 책을 공부하였다. 사실 자료구조는 C로 수업을 들어서 이미 알고 있었는데 파이썬으로 구현하면 어떤 변화가 있을까라는 생각에 이 책을 구매하게 되었다. 지금까지 공부한 바로는 다른 언어에 비해 파이썬은 엄청나게 쉬운.. 2020. 7. 3. 이전 1 다음 반응형
