Chapter 10. 단순한 정렬 알고리즘
주의 사항! 이 글은 제가 직접 공부하는 중에 작성되고 있습니다. 따라서 제가 이해하는 그대로의 내용이 포함됩니다. 따라서 이 글은 사실과는 다른 내용이 포함될 수 있습니다. 다음과 같이 네 개의 숫자가 나열되어 있다고 가정하겠습니다. 3 2 4 1 위와 같이 나열된 숫자를 오름차순으로 정렬해 보겠습니다. 먼저 맨 앞의 3과 그 다음의 2를 비교합니다. 비교 결과 오름차순에 위배되면 두 숫자의 위치를 바꿉니다. 따라서 다음과 같이 됩니다. 2 3 4 1 이번에는 두 번째 숫자와 그 다음 숫자를 비교합니다. 비교하면 3과 4로 오름차순에 위배되지 않으므로 두 숫자의 위치를 바꾸지 않습니다. 바로 다음으로 넘어가 이번에는 세 번째 숫자와 그 다음의 숫자를 비교합니다. 비교 결과 오름차순에 위배되므로 두 숫자..
Chapter 09. 힙의 구현과 우선순위 큐의 완성
주의 사항! 이 글은 제가 직접 공부하는 중에 작성되고 있습니다. 따라서 제가 이해하는 그대로의 내용이 포함됩니다. 따라서 이 글은 사실과는 다른 내용이 포함될 수 있습니다. 힙의 구현을 위해서는 데이터의 저장과 삭제의 방법을 먼저 알아야 합니다. 따라서 먼저 데이터의 저장 과정을 '최소 힙'을 기준으로 설명하겠습니다. 위 힙의 데이터가 데이터이자 곧 우선순위라고 가정하겠습니다. 여기에 2를 저장하는 알고리즘을 어떻게 구성할 수 있을까요? 책에서 소개하는 알고리즘은 다음과 같습니다. 우선 우선순위가 가장 낮다고 가정하고 힙의 마지막 위치에 저장합니다. 마지막 위치란 마지막 레벨의 가장 오른쪽 노드 자리를 말합니다. 만약 마지막 레벨이 다 채워지면 그 다음 레벨의 가장 왼쪽 노드 자리를 마지막 위치로 합니..
Chapter 09. 우선순위 큐의 이해
주의 사항! 이 글은 제가 직접 공부하는 중에 작성되고 있습니다. 따라서 제가 이해하는 그대로의 내용이 포함됩니다. 따라서 이 글은 사실과는 다른 내용이 포함될 수 있습니다. 앞서 배웠던 '큐'의 핵심 연산 두 가지는 다음과 같았습니다. enqueue 큐에 데이터를 삽입하는 행위 dequeue 큐에서 데이터를 꺼내는 행위 이와 마찬가지로 '우선순위 큐'의 핵심 연산 두 가지도 다음과 같습니다. enqueue 우선순위 큐에 데이터를 삽입하는 행위 dequeue 우선순위 큐에서 데이터를 꺼내는 행위 반면 연산의 결과에는 차이가 있습니다. 큐는 연산의 결과로, 먼저 들어간 데이터가 먼저 나오지만, 우선순위 큐의 연산 결과는 들어간 순서에 상관없이 우선순위가 높은 데이터가 먼저 나옵니다. 때문에 큐를 가리켜 '..
주의 사항! 이 글은 제가 직접 공부하는 중에 작성되고 있습니다. 따라서 제가 이해하는 그대로의 내용이 포함됩니다. 따라서 이 글은 사실과는 다른 내용이 포함될 수 있습니다. 앞서 수식 트리를 구현할 때 수식 트리를 계산하는 함수는 소개하지 않았습니다. 그때 제가 소개했던 것은 제가 직접 구현한 함수였습니다. 이제 책에서는 수식 트리를 어떻게 구현하고 있는지 소개하겠습니다. int EvaluateExpTree(BTreeNode* bt) { int op1, op2; if (GetLeftSubtree(bt) == NULL && GetRightSubTree(bt) == NULL) { return GetData(bt); } op1 = EvaluateExpTree(GetLeftSubTree(bt)); op2 = ..
Chapter 08. 수식 트리(Expression Tree)의 구현
주의 사항! 이 글은 제가 직접 공부하는 중에 작성되고 있습니다. 따라서 제가 이해하는 그대로의 내용이 포함됩니다. 따라서 이 글은 사실과는 다른 내용이 포함될 수 있습니다. 이진 트리를 이용해서 수식을 표현해 놓은 것을 가리켜 '수식 트리'라고 합니다. 즉 수식 트리는 이전 트리와 구분이 되는 별개의 것이 아닙니다. 먼저 다음의 수식을 보겠습니다. 7 + 4 * 2 - 1 우리는 보통 이러한 수식을 컴퓨터가 스스로 알아서 인식할 수 있다고 생각합니다. 그렇다면 컴파일러는 어떻게 이러한 수식을 처리하는 걸까요? 알다시피 컴파일러는 위의 코드를 실행이 가능한 상태로 만드는 소프트웨어입니다. 그런데 그 방법을 인간이 결정하여 컴파일러에게 인식시킨다는 사실을 놓치는 경우가 종종 있습니다. 컴퓨터의 유연한 판단..
Chapter 08. 이진 트리의 순회
주의 사항! 이 글은 제가 직접 공부하는 중에 작성되고 있습니다. 따라서 제가 이해하는 그대로의 내용이 포함됩니다. 따라서 이 글은 사실과는 다른 내용이 포함될 수 있습니다. 앞서 트리의 노드를 삭제할 때, 그 후손 노드까지 전부 삭제해야 한다고 말했습니다. 그러기 위해서는 삭제하고자 하는 노드의 모든 후손 노드들에 접근하는 일을 수행해야 합니다. 이를 '순회'라고 합니다. 이진 트리의 순회가 필요한 이유는 앞서 설명했으니, 이진 트리의 순회 방법을 설명하겠습니다. 이진 트리를 대상으로 하는 대표적인 순회 방법은 다음과 같습니다. 전위 순회(Preorder Traversal) 루트 노드를 먼저 중위 순회(Inorder Traversal) 루트 노드를 중간에 후위 순회(Postorder Traversal)..