행복한 연어의 이야기

안녕하세요 오늘은 자료구조 이진트리에 관련된 포스팅 입니다! 이진트리 구현에 앞서 트리(Tree) 가 무엇인지 한번 훑고 가보도록 하겠습니다 1. 트리(Tree) 란? 트리는 스택(Stack) 큐(Queue) 와 다르게 비선형적 자료구조 입니다. 일렬로 쭉 이어진 선형적 구조와는 다르게 트리는 계층적 관계를 표현하는 자료구조 입니다. 마치 조직도의 계급이나 컴퓨터 폴더 안에 폴더 같은 느낌이 들지 않나요?? 가지를 뻗어 나가는 모습때문에 Tree 라는 이름이 붙었다고 합니다. 어디에선가 들었는데 트리는 입출력 (스택, 큐) 자료구조라기보다 무엇인가 표현하는 자료구조라고 생각하는게 좋다고 하네요! 2. 트리의 관련 용어 노드(Node), 버텍스(Vertex) 트리의 구성요소 (A,B,C,D,E,F,G) 간..

안녕하세요. 오늘은 자료구조 큐 입니다. 이것도 스택과 마찬가지로 배열 방식 과 링크드리스트 방식 두가지를 구현해 보도록 하겠습니다. 1. 큐(Queue) 란? FIFO (First In First Out) 제일 먼저 들어간 값이 제일 먼저 나오는 자료구조입니다. 배열과 링크드리스트의 차이는 스택과 동일하게 처음 크기를 할당 하는지, 사용할때마다 크기를 줄이고 키우고 하는지 조절하는 것이 가장 큰 차이구요! 2. 배열을 이용한 큐 구현 배열로 큐를 구현하려고 하면 몇몇 문제점이 있습니다. index 를 따라서 앞에 있는 값을 빼다보면 언젠가는 index == maxSize 가 오기 때문인데요. 그렇다고 배열에서 값을 뺄때마다 뒤에 있는 값들을 배열 한칸씩 땡기는 것은 매우 비효율적인 과정이구요! 그래서 ..

안녕하세요 오늘은 자료구조 스택입니다! 오늘은 2가지 스택을 구현해 보려고 하는데요 배열을 이용한 스택과 링크드리스트를 이용한 스택입니다. 그래서 두가지 클래스를 정의 하고 동적할당 하여 생성, 해제를 해보도록 하겠습니다. 1. 스택이란? LIFO(Last In First Out) 제일 마지막에 들어간 것이 제일 먼저 나오는 구조의 자료구조입니다. 값을 넣는 Push 와 값을 빼는 Pop 으로 이루어져 있습니다. 배열 스택과 링크드리스트 스택의 가장 큰 차이점이라면 배열 스택은 처음에 배열의 크기를 할당해서 사용하고 링크드 리스트는 값을 추가 하거나 뺄때마다 크기를 조절한다고 볼 수 있겠습니다. 2. 배열을 이용한 스택 구현 class StackArray { private : int top;//가장 위를..

안녕하세요. 오늘은 저번 단일 연결 리스트에 이어 이중연결 리스트를 구현해 보도록 하겠습니다. 저번과 마찬가지로 malloc 과 free 를 사용하였습니다. 1. 이중 연결 리스트(Doubly Linked List)란? 다음 노드 정보만 가지고 있는 단일연결 리스트와는 다르게 이중 연결리스트는 이전 노드 정보도 가지고 있다는게 큰 특징이에요. 그래서 이전 노드를 찾으려고 head 부터 돌 필요가 없는 대신 앞 뒤로 연결을 해주어야 하기때문에 단일 연결리스트 보다는 구현이 조금 더 복잡하다는 단점이 있어요. 또한 이전 노드 정보도 가지고 있기 때문에 단일연결에 비해서 약간의 byte 를 더 사용 합니다. 2. 이중 연결 리스트(Doubly Linked list) 방식 설명 저번 단일 연결 링크드 리스트처럼..

안녕하세요! 오늘은 단일 연결 리스트 (Singly Linked list) 를 구현해 보도록 하겠습니다. 블로그를 돌아다니시면 많은 예제들이 있겠지만 이런 방식도 있구나! 할 수 있게 도움 되시라고 제가 공부하면서 구현한것도 설명과 함께 올려 보도록 할게요. C 의 Malloc 과 free 를 사용 하였습니다! 1. 단일 연결 리스트(Singly Linked list)란? 각 노드가 데이터와 다음 노드 정보를 가지고 한 줄로 연결되어 있는 방식으로 데이터를 저장하는 자료 구조입니다! 오직 다음 노드 정보만 가지고 있기에 단일 이라는 이름이 붙었습니다. 2. 단일 연결 리스트(Singly Linked list) 방식 설명 링크드 리스트를 찾아보셧다면 구현한 방법들이 조금씩 다르다는 것 느끼셧을거에요 대표적..