Reference
-
TreeReference/자료구조 2024. 1. 18. 15:54
# 비선형 자료구조의 탐색 방법 : 트리 자료구조의 가장 핵심적인 내용 중 하나는 탐색이다. 매우 유용한 링크드 리스트의 경우 원하는 자료형에 도달하기 위해서는 하나씩 넘겨가며 찾는 방법 이외에는 없다. 자료가 정렬되어 있다면 이진 탐색이나 보간 탐색 같은 꽤 빠른 탐색 알고리즘을 적용할 수 있지만, 정렬되지 않은 자료들에 대해서는 활용할 수 없다. 이를 보완하기 위한 방법으로 트리를 생각해 볼 수 있다. 트리란 그래프와 유사한 구조이다. 트리를 다른 말로 Connected Acyclic Graph라고도 한다. 즉, 모든 노드가 연결되어 있어야 하며 동시에 사이클이 없는 그래프를 트리라고 한다. 그림1처럼 a-b, b-c, c-a 같이 한 번 지난 노드는 다시 지나지 않을 때 처음 시작 노드로 돌아오는 ..
-
QueueReference/자료구조 2024. 1. 9. 17:30
# 큐의 구조 큐도 스택과 마찬가지로 매우 직관적인 구조를 가진다. 한쪽에서는 삽입이, 반대쪽에서는 삭제가 이루어진다. 삽입과 삭제는 들어온 순서대로 이루어지며 먼저 도착한 데이터가 먼저 나가는 FIFO 구조를 가진다. 큐도 구현하기에 따라 배열로도, 리스트로도 구현할 수 있다. 이 글에서는 배열로 구현되어 있다. 스택과 다르게 배열로 구현한 쪽이 조금 더 복잡하다. # 순환 큐의 구현 큐를 단순히 배열에 넣고 구현한다면 삭제를 한번 수행할 때 마다 모든 원소를 한 칸 움직이는 연산을 수행해야 하므로 비효율적이다. 그러므로 우리는 포인터를 움직이는 방식으로 삭제와 삽입을 구현해야 한다. 그러나 이 방식으로는 완전하게 큐를 구현할 수 없는데, 삽입과 삭제 연산이 일어나다 보면 Front, Rear 포인터의..
-
StackReference/자료구조 2024. 1. 3. 15:00
# 스택의 구조 스택의 구조는 매우 단순하다. 모든 삽입과 삭제 연산이 한 끝에서 이루어지는 구조이다. 컴퓨터 프로그램은 일반적으로 램이라고 부르는 Random Access Memory에 공간을 할당받고 프로그램이 올라가게 된다. (물론 RAM 이외에도 펌웨어에 많이 사용되는 Read-Only Memory, 캐시 메모리에 쓰이는 associative memory, 하드디스크 등등 여러 종류의 저장장치가 있고 적제적소에 맞게 사용된다.) RAM은 상당히 빠른 속도로 데이터에 접근할 수 있는데, 어떤 공간을 올바르게 찾아가기 위해서는 그 공간의 주소값이 필요하다. 이때, 스택에서는 연산이 TOP 위치의 주소값에서 일어나게 된다. 다익스트라는 스택을 마치 철로 전환에 비유하여 설명하고 있다. 그림 2에서 이 ..
-
Double Linked ListReference/자료구조 2023. 12. 31. 01:26
# 더블 링크드 리스트의 구조 자료구조의 첫 개시글은 더블 링크드 리스트이다. 그림을 보면 개념을 이해하기 쉽다. next 포인터는 다음 노드 자체를 가리키고 있고, prev 포인터는 이전 노드를 가리킨다. 그림1에서는 설명되어 있지 않지만, 리스트 블럭중 가장 첫 번째 블럭은 Head, 가장 마지막 블럭은 Tail이라 불린다. 위 그림1을 예시로 들면 A 노드는 Head, B 노드는 Tail이다. 링크드 리스트의 구조는 prev, next 포인터와 데이터 부분으로 나누어진다. typedef int ElementType; typedef struct tagNode { ElementType Data; struct tagNode * PrevNode; struct tagNode * NextNode; } Node..
-
자료구조Reference/자료구조 2023. 12. 30. 16:08
여러 자료구조에 대해 정리하고 구현해보려고 한다. 예전 수업시간에 배웠던 공부의 복습 목적도 있지만, 이번 방학 중 목표로 잡았던 것 중 하나인 OS 구현에서 사용하기 위함이 더 크다. OS에서 사용하는 자료구조는 더블 링크드 리스트(DLL), 큐(Queue), 스택(Stack), RB tree, B-tree 등 다양한 종류의 자료구조를 사용한다. 이 카테고리에서는 자료구조를 간단하게 설명하고, 직접 구현해본 다음 코드를 깃허브에 올려놓겠다. 깃허브 주소는 아래와 같다. https://github.com/seyoung4503/dataStructure 모든 코드는 C 코드로 작성된다. 이유는 가장 기본에서 시작해서 구현하고 싶다. 또한, 웬만한 자료구조를 전부 구현하고 나서 OS를 구현할 계획인데 이때 M..
-
아두이노 첫 시작Reference/Arduino Reference 2020. 5. 8. 16:25
아두이노를 처음 사용해 보았을 때는 고등학교 시절이었다. 그 당시 내가 인식하던 아두이노는 초등학생들이나 중학생들이 코딩을 처음 배울 때 재미있게 배우기 위한 "교구"정도로 알고 있었다. 그렇게 접할 기회가 많이 있는 것도 아니었고 무엇보다도 수업도 실습도 너무 재미없었다. 실습도 기껏해야 고작 LED 불 켜기, 소리 내기, 모터 움직이기 정도였고 더 높은 상위의 것을 재현하고 싶었던 나는 뭔가 좀 더 "전문화된" 기기를 사용해 보고 싶었다. 내가 상상했던 것과 비교하면 LED 불 켜기는 정말로 시시해 보였던 것이다. 출처: https://ko.wikipedia.org/wiki/%EC%95%84%EB%91%90%EC%9D%B4%EB%85%B8 어느 날, (유*) 대학으로 대학 탐방을 가게 되어 캠퍼스를 ..