LimeCoding

스레드 이진 트리란?(What is treaded binary tree?) ​이진 트리를 연결 리스트로 표현했을 때 각 노드당 2개의 링크필드를 가지므로 n개의 노드에 대해 2n개의 링크필드를 가진다. 이때 마지막 노드가 n+1개의 링크필드를 가지는데 이 링크필드 모두 NULL을 가리켜 메모리 낭비가 심하다. 이를 해결하기 위해 펄리스(Perlis)와 손톤(Thornton)이 NULL링크들이 특정 노드를 가리키도록 하는 방법을 만든다. 여기서 조정된 NULL링크를 스레드(thread)라고 한다. 스레드 이진 트리는 기존 이진 트리의 구조에 2개의 쓰레드를 추가한다. 스레드 이진 트리에서 왼쪽 스레드와 오른쪽 스레드는 순회 방법에 따라 각각 특정 노드의 오른쪽 링크와 왼쪽 링크가 직전 방문 노드와 다음 방..

오늘은 어떻게 보면 시작하는 날이다. 뭘 시작하냐고? 바로 학교 공부이다. 날짜가 딱 봐도 학교를 가는 날이다. 다행이도 먼 거리를 가지 않고 집에서 비대면 수업을 받게 됐다. 학교를 갈 수 있으면 좋겠지만 어떻하겠는가? 아침에 일어나서 내가 시간표도 잠깐 손을 봐주고 수업 오리엔테이션을 하고 친구가 놀자고 해서 갔다 왔다. 이번에는 포천을 갔다왔는데 내가 생각하지 못한 곳에 멋진 곳이 있었다. 과장하자면 중국의 장가계 부럽지 않은 멋진 곳이었다. 그렇게 치킨도 먹고 놀았다. 공부는 했냐고 묻는다면 흠... 변명이겠지만 내일부터 시작!!

지난 2월달에 대한 결산을 하자면 100% 성공이라고 말할 수는 없지만 약 70~80%정도의 달성율을 보여주었다. 이 달성율은 어떤건 100%, 어떤건 40%가 아니라 평균적으로 70~80%정도의 달성율이다. 이 정도면 나름 좋은 성과가 있다고 생각한다. 꼭 하루 2시간 전공 관련 공부하기가 있었는데 이건 초과 달성이다. 나를 너무 과소 평가했다. 하루에 길게는 10시간 이상이고 짧게는 4~5시간은 한 것같다. 매일 1시간씩 운동도 아침에 둘레길을 걸으면서 달성했다. 아쉽게도 매일은 아니었지만 일주일에 5일이면 준수한 편인 것 같다. 트위치나 유튜브 시청 시간도 많이는 아니지만 유의미한 수치는 나온다. 기존 보다 2~3시간 정도는 감소했다. 그게 다 공부하는 시간이나 책읽는 시간, 영화보는 시간으로 갔으..

트리 순회(Tree Traversal) 배열은 인덱스를 통해 모든 데이터를 접근할 수 있다. 연결 리스트의 경우도 처음부터 끝까지 링크를 통해 접근할 수 있다. 하지만 트리는 선형 자료구조가 아니기 때문에 트리를 선형 자료 구조와 같은 방법으로 접근할 수 없다. 그렇다면 트리 구조에서 모든 데이터를 보고 싶다면 어떻게 해야할까? 트리에서는 순회(traversal)를 통해 모든 노드들을 접근할 수 있다. 트리를 순회하는 방법은 노드를 방문하는 순서에 따라 전위(preorder), 중위(inorder), 후위(postorder), 레벨(level)로 나뉜다. 전위 순회(Preorder Traversal) 전위 순회(preorder traversal)는 루트 노드를 먼저 방문한 후 이 노드의 왼쪽 서브트리를 ..

트리란?(What is Tree?) 트리는 우리가 일상생활에서도 많이 볼 수 있는 형태의 자료구조이다. 윈도우 탐색기에서의 폴더 구조나 대진표가 대표적인 트리 구조이다. 트리는 나무를 거꾸로 뒤집어 놓은 형태를 가지며 노드라 불리는 데이터 요소를 기준으로 나무가지가 뻗어나가듯이 노드들이 연결되어 있다. 트리를 좀 더 명확하게 정의하면 다음과 같다. 정의 트리는 다음과 같이 재귀적으로 정의된다. 트리는 최상위 노드(node)인 하나의 루트(root)를 갖는다. 루트를 제외한 나머지 노드들은 n(n≥0)개의 서로소인 부분집합 T1, ... ,Tn 으로 분리되는데, 각각의 부분집합은 마찬가지로 트리이다. 이때, T1, ... ,Tn을 서브트리(subtree)라 한다. 트리가 무엇인지 간단하게 알았으니 이번에는..

이중 연결 리스트란?(What is Doubly linked list?) 이중 연결 리스트(doubly linked list)는 기존 단순, 원형 연결 리스트의 단점인 단방향 흐름을 2개의 링크 필드를 이용하여 양방향으로 움직일 수 있게 만든 것이 이중 연결 리스트이다. 원형 연결 리스트에 이중 연결 리스트를 결합하면 이중 원형 연결 리스트가 된다. 이중 연결 리스트는 양방향으로 움직일 수 있어 데이터 접근이 단순, 원형 연결 리스트보다 쉽고 삽입, 삭제 연산시 선행 노드에 대한 정보가 필요없다는 장점이 있다. 이중 연결 리스트의 노드는 다음과 같다. 이중 연결 리스트의 기본적인 연산은 다음과 같다. 리스트 생성 노드 삽입 노드 삭제 리스트 생성 리스트는 헤드 노드를 갖는 리스트를 생성한다. 리스트를 생..

연결 리스트를 잘 모른다면 필자가 포스팅한 내용을 보고 온다면 이해하기 편하다. 원형 연결 리스트란?(What is Circular linked list?) 원형 연결 리스트(circular linked list)는 단순 연결 리스트의 단점을 보완한 리스트이다. 단순 연결 리스트는 한 방향으로 움직이면서 그 끝이 정해져 있기 때문에 리스트를 검색할 때 항상 리스트의 처음부터 접근해야하는 단점이 있다. 또한 리스트가 순환을 요구한다면 더더욱 불리하다. 이를 해결하기 위해 단순 연결리스트의 마지막 노드가 리스트의 처음 노드를 가리키도록 만든 것이 원형 연결 리스트이다. 원형 연결 리스트는 다음과 같은 형태를 가진다. 원형 연결 리스트는 다음과 같은 기본연산을 가지고 있다. 리스트 생성 노드 삽입 노드 삭제 ..

연결 리스트란?(What is Linked List?) 연결 리스트(Linked list)란 링크로 원소들이 연결된 순차 리스트를 말한다. 연결 리스트는 순차 리스트의 삽입삭제 연산에서의 불리한 점을 보완하기 위해 만들어 졌다. 순차 리스트에서 삽입 연산을 하게 되면 중간에 데이터를 집어넣을 때 삽입될 데이터를 위해 공간을 만들어야 한다. 이때 공간을 만드는 과정에서 삽입되는 데이터 뒤에 데이터들이 자리를 옮기기 위한 연산을 취해야 하는데 이는 리스트가 가지고 있는 데이터가 크면 클수록 많은 시간이 걸린다. 삭제 연산도 삭제후 빈 공간을 채우기 위해 자리를 옮기는 과정이 필요하다. 이러한 문제점들을 해결하는 것이 연결 리스트이다. 연결 리스트를 이루는 기본적인 단위는 노드(node)이다. 노드는 데이터 ..

큐란?(What is Queue) 큐(Queue)는 데이터가 들어가는 곳과 나가는 곳이 한 곳으로 정해져있는 자료 구조를 말한다. 매표소에 사람들이 줄을 서 있으면 먼저 온 순서대로 표를 구매하게 된다. 큐는 먼저 온 데이터를 먼저 처리하는 형태를 띈다. 이를 FIFO(First-In-First-Out) 또는 LILO(Last-In-Last-Out)이라고 한다. 둘 다 맞는 표현이지만 FIFO를 더 많이 사용한다. 큐에서 데이터가 삽입되는 부분을 rear라고 하고 데이터가 삭제되는 곳을 front라고 한다. rear가 가리키는 데이터는 가장 최근에 삽입된 데이터이고 front가 가리키는 데이터는 가장 먼저 삽입된 데이터이다. 큐의 연산(Queue Operation) 큐의 기본 연산은 다음과 같다. Enq..

스택이란?(What is Stack?) 우리가 식당같은 곳에 가보면 다 먹은 음식의 접시나 그릇은 위로 차곡차곡 쌓아 올리는 모습을 볼 수 있다. 설거지를 할때는 위에서부터 하나씩 꺼내어 설거지를 하게 된다. 이것이 스택이다. 스택(Stack)이란 데이터 삽입, 삭제가 한 방향에서만 이루어지는 것을 말한다. 스택은 가장 먼저 들어온 데이터는 가장 나중에 나가고 가장 나중에 들어온 데이터는 가장 먼저 나가게 된는 성질을 가지고 있다. 이를 LIFO(Last-In-First-Out) 또는 FILO(First-In-Last-Out)이라고 한다. 둘 다 맞는 표현이지만 LIFO를 더 많이 사용한다. 스택은 top과 bottom이라는 2개의 포인터를 이용하여 삽입과 삭제를 제어한다. top포인터는 스택의 가장 위..