지난 글에서는 트리와 이진트리, 그리고 이진 트리를 만들 수 있는 가짓수인 카탈란 수에 대해서 정리하였다. 이번 글에서는 이진 트리를 순회하는 3가지 방법을 정리해보고자 한다. 사람에 관점에서는 이진트리의 전체적인 모습이 보이기 때문에 특정 노드를 찾을 때 전체 이진트리에서 특정 노드를 바로 딱 보면 쉽게 알 수 있다. (글로벌 뷰) 하지만 컴퓨터 입장에서 이진트리를 탐색할 때는, 연결리스트 때와 비슷하게, 현재 자신이 보고 있는 노드 T와, 그 T의 ITEM(T), 왼쪽 노드 LEFT(T) , 오른쪽 노드 RIGHT(T) 만 본다. (로컬뷰) 이런 로컬 뷰가 재귀적으로 반복되기 때문에, 이진트리를 탐색할 때는 재귀를 이용하게 되는데, 이진 트리를 재귀적으로 탐색하는 방법에는 3가지가 있다. Preord..
지난 글에서는 연결리스트가 사용하는 메모리 공간을 어떻게 관리하는지 그 구현을 C언어로 직접 해보았다. 이번 글에서는 트리와 이진트리의 개념을 정리해보고자 한다. 트리 트리는 아래와 같이 정의된다. a tree is a finite set T of nodes such that 1) T has one special node called root 2) the remaining nodes are partitioned into m disjoint sets T1, T2, ... Tm, and each of these sets is turn to a tree. wee call them subtrees of T 트리는 '루트' 라고 불리는 특별한 하나의 노드를 가지고 있고, 나머지 노드들은 m 개의 서브트리를 이루는..
지난 글에서는 연결리스트를 이용해 스택과 큐를 구현하였다. 이번 글에서는 연결리스트를 이용하는 과정에서 new(), free() 기능을 사용했는데, 이 기능을 직접 구현해본다. 사실 직접 구현이라고 해서 나도 처음엔 메모리를 직접 다루는 거창한 걸 기대했는데, 그런건 아니다. 그냥 배열을 이용해서 전체 memory pool 을 세팅해두고, 그 세팅된 pool 내 메모리를 주고 받고 하는 방식이다. 메모리 풀은 연결리스트 노드의 데이터 형태로 배열에 세팅해두고, 이를 스택처럼 활용하여 메모리를 주고 받는다. 메모리 풀은 이런 구조로 존재한다. 만약 new 함수로 메모리 공간을 요청하면 top이 가리키는 노드를 제공해준다. 제공을 마친 모습이다. 제공된 메모리는 연결리스트에서 자유롭게 Item 부분에도 값을..
지난 글에서 Linked List 의 개념과 그 구현에 대해 정리하였다. 이번에는 Array 로 구현했던 Stack 과 Queue를 Linked List 로 구현하는 과정을 살펴보고자 한다. Stack With Linked List 스택을 연결리스트로 구현해보자. 연결리스트에서 데이터를 중간에 삽입할 때는 이전 노드의 주소를 알아야 하기 때문에 아주 복잡했다. 데이터를 맨 처음에 삽입하는 것이 아주 간단하기 때문에, 스택의 데이터 삽입과 삭제가 빈번히 일어나는 top 을 연결리스트의 첫 head로 설정하자. 그림으로 나타내면 이렇게 나타난다. 스택에 데이터를 추가하면 추가된 데이터를 top 이 가리키고, 추가된 데이터가 기존 데이터를 가리키는 방식으로 구현하면 된다. 스택에서 데이터를 뺄 때는 top 의..
지난 글까지 Array 를 이용한 스택과 큐의 구현에 대해 정리하였고, 지난 글에서는 특히 단순하게 구현한 큐에서 메모리를 제대로 활용하지 못하는 문제를 해결하기 위해 Circular Queue 를 구현하는 과정을 소개하였다. 이번 글에서는 Array 와 다른 Linked List 라는 새로운 자료구조를 정리하고자 한다. Linked List Linked List 는 한국어로 번역하면 '연결리스트' 라고 한다. 말 그대로 선으로 연결하여 나타낸 리스트를 의미하는데, 연결 리스트의 특징은 배열과 달리 데이터와 데이터가 메모리의 연속된 공간에 존재하지 않을 수 있다. 대신 연결된 다음 데이터를 나타낼 그 데이터의 주소를 같이 저장함으로서 데이터와 데이터의 연결관계를 나타내는 특징이 있다. 그림과 같이 저장할..
지난 포스팅에서는 배열을 이용한 큐를 구현해보았다. front, back 변수를 모두 0으로 초기화 하였을 때, push: back 변수가 가리키는 인덱스에 데이터 추가, back >= size 이면 오버플로우 pop: front 변수가 가리키는 인덱스의 데이터를 제거, front >= back 이면 언더플로우 와 같이 구현할 수 있었다. 그러나 이렇게 구현하면 push 를 최대 N번, pop은 push 횟수 이하로만 할 수 있다는 문제가 있었다. 이번에는 Size N 이라는 메모리 공간에 중간중간 여유가 생긴다면 그 여유공간까지 활용하여 push 를 더 많이 할 수 있도록 기존의 큐를 개선하여 보겠다. 그림과 같이 사이즈 5인 큐에 모든 값이 다 들어있는 상황을 생각해보자. 현재 front 는 2이고,..
이번에는 큐를 배열을 통해 구현하는 과정을 정리하고자 한다. 구현에 앞서 '큐'의 개념을 살펴보자. 큐의 개념 이번에도 구글 번역기로한번 번역부터 해 보았다. 이번에는 번역기가 번역을 해준다! 번역의 결과가 큐를 말 그대로 설명해주고 있다. 큐는 '대기줄' 이다. 대기줄의 특성을 생각해보자. 식당에 (학교에서는 교수님이 '하카타분코' 라는 라멘집을 예시로 들어주신다 ㅋㅋ) 손님이 많아서 대기줄이 길게 있다고 할 때, 신규로 오는 손님은 대기줄의 '뒤'에 서게 되고, (push) 식당에 빈자리가 생기면 대기줄 맨 앞에 있던 사람이 들어가게 된다. (pop) 큐는 이를 그대로 표방하는 자료구조이다. 먼저 들어왔던 데이터가 먼저 나가는 First In First Out (FIFO) 방식의 자료구조이다. 큐는 ..
Stack ( 스택 ) 이란 스택이라는 자료구조는 매우 직관적으로 이해할 수 있는 자료구조이다. 스택이라는 말 자체가 이미 이 자료구조에 대해 모든 걸 설명하고 있다. 보통 스택이라고 하면 어떤 것들이 쌓여있는 형태를 의미하는데, 스택이라는 자료구조도 무언가를 쌓는 형태를 자료구조화 한 것이다. 가령 책이 한 무더기 쌓여있다고 해보자. 중간에 있는 원하는 책을 찾아 꺼내려면 어떻게 해야할까? 가장 당연하게 떠오르는 방법은 맨 위에 있는 책부터 하나씩 하나씩 확인하면서 찾을 것이다. 중간 어디에 있는지도 모르는데 책을 무더기로 들춰가면서 찾는 것은 너무 힘들지 않을까 그 책 무더기에 새로운 책을 여러권 놓는다고 해보자. 그러면 가장 먼저 놓은 책이 제일 밑에 놓이고, 가장 나중에 놓은 책이 맨 위에 놓이는..
3글자의 알파벳으로 이루어진 이름과, 4글자의 숫자로 이루어진 번호 쌍을 저장하는 주소록 프로그램이 있다고 해보자. 이 프로그램에서 이름과 번호쌍을 어떻게 관리할 수 있을까? 대부분의 언어에서 기본으로 제공하는 '배열' 자료구조를 이용하여 구현한다면 아래와 같이 구현할 수 있을 것이다. 1. 두 배열을 이용하여 데이터를 저장하기 첫 번째 방법은 두 배열을 이용해서 이름과 번호를 저장하는 방법이 있다. 이름과 번호를 연결짓는 기준은 '배열의 인덱스' 가 된다. 이렇게 저장한 자료에서 이름을 기준으로 번호를 찾는다고 하면 아래와 같이 코드를 짤 수 있다. #include char name[10][3]; char number[10][4]; char find_name[3]; int main() { printf(..
