Algorithm/Theory19 자료구조 - 순환 큐(Circular Queue) 큐는 스택과 반대의 특성인 선입선출(First In, First Out)의 특성을 가지고 있습니다. 선입선출의 특성은 앞에서 작업의 처리가 끝나면 다음 작업이 실행될 수 있게 하는 완충장치로써 많이 사용됩니다. 가령 쇼핑몰이나, 특정한 사이트에서 카카오톡 채팅상담을 보신적이 있으실 겁니다. 상담사는 1명이지만, 상담을 받으려는 사람은 많기 때문에 큐를 사용하여 한 사람의 상담이 끝날 때까지 다른 사람은 대기하도록 하는 것이 큐의 사용입니다. 스택에서는 노드의 삽입과 제거가 최상위 노드에서만 이루어졌지만, 큐는 제거는 제일 전단에서 삽입은 후단에서 이루어집니다. 큐는 크게 배열로 만들어지는 순환 큐(Circular Queue)와 링크드 큐(LinkedQueue)가 있습니다. 하나하나씩 알아가보도록 하겠습니.. 2021. 2. 27. 자료 구조 - 스택(Stack) 스택은 앞선 링크드 리스트와 반대로 가장 먼저 들어간 노드가 가장 마지막에 나오는 선입 후출(First In, Last Out) 구조로 되어 있습니다. 스택은 소프트웨어에서 널리 쓰이는 자료 구조입니다. C에서 사용하는 자동 메모리, 대부분의 네트워크 프로토콜들이 스택으로 이루어져 있습니다. 스택은 배열과 링크드 리스트로 구현할 수 있습니다. 이번 포스팅에서는 링크드 리스트로 구현한 스택을 알아보겠습니다. 링크드 리스트로 구현하면 스택의 용량에 제한을 두지 않아도 된다는 장점이 있습니다. typedef struct tagNode { char* Data; //데이터 struct Node* NextNode; //자기 위에 쌓여있는 노드를 가르킨다. } Node; 링크드 리스트로 구현된 스택은 두가지 포인터를.. 2021. 1. 27. 자료 구조 - 더블 링크드 리스트(Double Linked List) 더블 링크드 리스트는 기존의 링크드 리스트에서 탐색 기능을 개선한 자료 구조입니다. 기존의 다음 노드에 대한 포인터만 존재하던 노드에서 이전 노드에 대한 포인터를 추가하여 양방향으로 탐색이 가능하도록 만든 자료 구조입니다. 아래는 더블 링크드 리스트의 코드입니다. typedef struct tagNode { int Data; // 데이터 필드 struct tagNode* PrevNode; // 이전 노드에 대한 포인터 struct tagNode* NextNode; // 다음 노드에 대한 포인터 } Node; 더블 링크드 리스트 노드의 생성과 소멸 기존의 링크드 리스트에서 이전 노드에 데한 포인터(PrevNode)를 NULL로 초기화하는 것만이 추가되었습니다. Node* DLL_CreatNode(int N.. 2021. 1. 19. 자료 구조 - 링크드 리스트(Linked List) 링크드 리스트는 고정적인 길이인 배열과 다르게 가변적인 성격을 가진 데이터의 집합입니다. 리스트 내의 각 요소는 노드로 이루어져 있으며, 노드는 데이터를 보관하는 필드와 다음 노드의 주소의 포인터가 들어가 있습니다. 데이터와 포인터로 이루어진 노드를 이으면 링크드 리스트가 됩니다. 링크드 리스트에서 제일 앞의 노드를 헤드(Head) 제일 마지막 노드를 테일(Tail)이라고 합니다. 위의 구조를 코드로 나타내면 아래와 같습니다. typedef struct tagNode { int data; // 데이터 필드 struct tagNode* NextNode; // 다음 노드에 대한 포인터 } Node; Node MyNode; 노드의 생성과 소멸 Node* SLL_creatNode(int newData) { //.. 2021. 1. 19. 자료 구조 - 이진 탐색 트리(Binary Search Tree) 이진 탐색 트리(Binary Search Tree)는 고정된 데이터 집합에서만 가능하던 이진 탐색의 단점을 보완한 이진 탐색을 위한 이진트리입니다. 그렇다면, 이진트리와 이진 탐색 트리의 다른 점은 무엇일까요? 이진 탐색 트리는 다음과 같은 규칙을 따릅니다. 왼쪽 자식 노드는 루트 노드보다 작고, 오른쪽 노드는 루트 노드보다 크다. 이진 트리 탐색에서의 이진 탐색 이진트리 탐색서의 이진 탐색은 기본적인 이진 탐색과 다르지 않습니다. 다만, 고정된 배열의 이진 탐색에서 중앙 요소가 이진트리에서는 루트 노드가 그 역할을 하게 됩니다. 목푯 값이 루트 노드보다 크면 오른쪽 트리를 탐색하고 작으면 왼쪽 트리를 탐색합니다. 그럼 위의 이진트리에서 목푯 값 34를 찾아가는 과정을 살펴보겠습니다. 목푯 값 34는 루.. 2021. 1. 17. 탐색 알고리즘 - 이진 탐색(Binary Search) 이진 탐색(Binary Search)은 정렬된 데이터 집합에서 사용할 수 있는 고속 탐색 알고리즘입니다. 이진 탐색을 수행하는 과정은 아래와 같습니다. 데이터 집합의 중앙에 있는 데이터를 고른다. 중앙에 있는 데이터값과 찾고자 하는 목표 값을 비교한다. 목표 값이 중앙에 있는 요소보다 작다면 중앙을 기준으로 왼쪽 데이터에 대해 새로 검색을 실시하고 크다면 오른쪽 데이터에 대해 새로이 검색을 실시합니다. 찾고자 하는 목표 값을 찾을 때까지 1~3번의 과정을 반복합니다. 예를 들어보자면, 아래와 같이 정렬된 데이터 집합이 있습니다. 이 데이터 집합에서 50을 찾아 보겠습니다. 1 5 18 20 35 40 46 50 70 90 먼저 중앙에 있는 요소를 고릅니다. 주어진 데이터 집합의 사이즈를 구하여 반으로 나.. 2021. 1. 14. 자료 구조 - 우선순위 큐와 힙 먼저 들어간 요소가 먼저 나오는(First-In First-Out) 자료 구조를 큐(Queue)라고 합니다. 우선순위 큐와 그냥 큐의 다른 점은 보통의 큐는 먼저 들어온 요소가 먼저 나가지만, 우선순위 큐에서는 요소에 우선순위를 부여해서 가장 높은 우선순위를 갖는 요소부터 빠져나가게 한다는 점에서 차이가 있습니다. 우선순위의 기준은 프로그래머에게 달려있습니다. 오름차순, 내림차순 등이 기준이 될 수도 있고, 시간의 빠름, 느림 등이 우선순위가 될 수도 있습니다. 우선순위 큐의 삽입 지금의 우선순위 큐의 기준은 값의 오름차순입니다. 이 큐에 20의 요소를 삽입한다면, 보통의 큐는 First-In First-Out의 구조로 32 뒤에 붙어야 하지만 우선순위 큐의 기준에 따라 17과 22의 사이에 삽입합니다... 2021. 1. 14. 탐색 알고리즘 - 순차 탐색(Sequential Search) 순차 탐색은 데이터의 집합(링크드 리스트, 배열등)을 처음부터 끝까지 차례대로 모든 요소를 비교해서 데이터를 찾는 알고리즘입니다. 순차 탐색은 '처음부터 끝까지 순서대로'라는 전략 때문에 효율은 나쁘지만, 구현이 간단하고 버그를 만들 가능성이 적어 높은 성능이 필요하지 않은 곳에서는 유용하게 사용됩니다. 아래의 코드는 링크드 리스트와 배열의 순차 탐색 코드 예입니다. ode* SLL_SequentailSearchNode(Node* Head, int Target) { //링크드 리스트를 위한 순차탐색 Node* Current = Head; Node* Match = NULL; // 탐색할 타겟과 일차하는 노드 while (Current != NULL) { //노드가 널이 아닐동안 => 널이면 빠져나옴 if .. 2021. 1. 12. 자료 구조 - 레드 블랙 트리 레드 블랙 트리는 불균형하게 성장한 이진 탐색 트리의 단점을 보완한 트리 구조입니다. 레드 블랙 트리가 이진 탐색 트리와 다른 점은 노드를 빨간색, 검은색으로 표시한다는 것입니다. 레드 블랙 트리는 다음과 같은 규칙을 따릅니다. 모든 노드는 빨간색 아니면 검은색이다. 루트 노드는 검은색이다. NIL(잎) 노드는 검은색이다. 빨간 노드의 자식들은 모두 검은색이다. 하지만 검은색 노드의 자식이 빨간색일 필요는 없다. 루트 노드에서 모든 NIL(잎) 노드 사이에 있는 검은색 노드의 수는 모두 동일하다. NIL 노드는 아무 데이터도 갖고 있지 않은 색깔만 검은색인 노드입니다. 굳이 NIL 노드를 사용하는 이유는 구현을 쉽게 하기 위해서입니다. NIL 노드를 양쪽 자식으로 연결해서 NIL 노드가 잎 노드가 되면 .. 2021. 1. 7. 이전 1 2 다음 반응형
