• MaxHeap Classclass MaxHeap {private: static const int root_index = 1; // 루트 노드의 인덱스는 1로 설정 static const int HEAP_SIZE = 200; // 힙의 최대 크기는 200으로 설정 int nodes[HEAP_SIZE]; // 힙 노드를 저장할 배열 int size; // 현재 힙의 크기 // 주어진 인덱스의 왼쪽 자식 노드의 인덱스를 반환 int LEFT(int i) { return i * 2; } // 주어진 인덱스의 오른쪽 자식 노드의 인덱스를 반환 int RIGHT(int i) { return i * 2 +..

• 우선순위(Priority) 어떤 일을 먼저 처리할지 순서를 정하는 것이다.  • 우선순위 큐 우선순위의 개념을 큐에 적용한 자료구조이다.우선순위를 가진 데이터를 저장하며 우선순위가 높은 데이터가 먼저 나가게 된다.  • 우선순위 큐의 ADT 데이터item = (여기서는 key = value = priority라고 심플하게 하자.) 주요 연산insert(item) : 우선순위 큐에 item을 추가remove: 우선순위가 가장 높은 요소를 삭제하고 반환find() : 우선순위가 가장 높은 요소를 삭제하지 않고 반환 우선순위 큐의 종류최소 우선순위 큐 :  우선순위가 작을수록 우선순위가 높음최대 우선순위 큐 : 우선순위가 클수록 우선순위가 높음  • 우선 순위 큐의 구현 방법 1. 배열을 이용해서 구현 ..

이제 실제 프로세서로 구현하면 어떻게 될지 알아보도록 하자. • Execution Cycle Instruction Fetch(IF) : 메모리로부터 명령어를 가져온다.Instruction Decode(ID) : 명령어를 해석해서 필요한 동작을 정의한다.Operand Decode : Operand 데이터를 가져온다.Execute(EX) : 명령어의 결과값/상태를 계산한다.Result Store(MEM) : 결과값을 스토리지에 저장한다.Instruction Next : 다음 명령어를 정의한다. (PC = PC+4) • Implementation Overview 메모리 및 FU를 통과하는 데이터의 흐름이다.  • Digital Systems 디지털 시스템을 구현하기 위해 필요한 3가지 컴포넌트들이 있다.  C..

BST(1)에서 슈도코드로 다뤘던 것들을 이제 C++ 코드로 살펴보자. • BinaryNode Classclass BinaryNode { // BinarySearchTree 클래스가 BinaryNode의 private 멤버에 접근할 수 있도록 설정 friend class BinarySearchTree;private: int key; // 노드의 키 값 int value; // 노드의 데이터 값 BinaryNode* left; // 왼쪽 자식 노드에 대한 포인터 BinaryNode* right; // 오른쪽 자식 노드에 대한 포인터public: // 생성자: 키, 값, 왼쪽 자식 포인터, 오른쪽 자식 포인터를 초기화 BinaryNode(int key = 0..

• 탐색(Search) 특정 자료구조 내에 저장된 정보를 찾아내는 일이다.방대하게 저장된 데이터에서 원하는 정보를 효율적으로 찾아내는 것은 중요하다. n개의 아이템을 가지는 1차원 배열에서 원하는 값을 찾기 위해 가장 간단한 방법은 순차 탐색이다.그러나 순차 탐색은 최악의 경우 O(n)의 시간 복잡도를 요구한다.(마지막에 있거나 아예 없거나) 그렇다면 Insert/remove/search 등을 O(n) 보다 더 빠르게 할 수 있는 방법은 없을까? 탐색을 위해 특화된 이진 트리인 이진 탐색 트리에 대해 알아보도록 하자. • Key & Value 트리에서 노드는 key와 value를 가진다.Key : 해당 노드를 다른 노드와 구분 짓게 하는 식별자(ID)를 의미한다.Value : key에 대응되는 데이터 값..

• 이진 트리의 순회 순회는 자료구조 내의 데이터를 특정 순서대로 방문하는 것을 의미한다. 선형 자료구조에서의 순회선형적인 순서로 조회한다.이진 트리에서의 순회트리는 비선형 자료구조이기 때문에 여러가지 순서로 노드를 방문할 수 있다. • 이진 트리의 순회 방법 전위 순회(pre-order traversal)루트 출력 → 왼쪽 서브트리 → 오른쪽 서브트리def preorder(node): if node is not NULL: # 현재 노드가 NULL이 아닌 경우에만 수행 print(node.data) # 현재 노드의 데이터를 출력 preorder(node.left) # 왼쪽 자식 노드를 전위 순회 preorde..

• Tree 트리는 계층적인 구조를 나타낼 수 있는 자료구조이다.부모-자식 관계의 노드들로 이루어져 있다. • 트리의 용어 노드(node) : 트리의 구성요소루트(root) 노드 :  제일 상단에 있는 노드(부모가 없는 노드)간선(link, edge) : 노드와 노드를 연결하는 선서브트리(subtree) : 하나의 노드와 자손들로 이루어짐 단말노드(terminal, leaf, external) : 자식이 없는 노드비단말노드(brach, internal) : 자식을 가지는 노드 자식, 부모, 형제, 조상 노드특정 노드를 기준으로 가족 관계를 따진다. 노드의 차수(degree) : 노드의 자식 노드 수노드의 깊이(depth) : 루트 노드에서 특정 노드까지의 간선의 수노드의 레벨(level) : 트리의 계층..

• Recursion Recursion = 재귀함수단 몇개의 문자만으로 문제의 solution을 구할 수 있다.다만 반드시 효율적이지는 않으며, 모든 문제가 재귀적으로 풀리지는 않는다. • 일반적인 Format 1) Simple base case : 더 이상 재귀호출을 진행하지 않고 정답을 생성한다.2) Recursive step : 함수가 재귀적으로 호출된다.모든 재귀함수는 점진적으로 base case로 이동한다. 아니면 무한 loop에 빠진다. 만약 base case가 없다면?스택이 용량이 초과되어 overflow error가 발생할 것이다. • Recursion 푸는 방법 Divide & Conquer : 작은 문제로 나눠주고 각각 풀어준다.우선 가정을 하고 설계한다! 그럼 어떻게 올바른 계산이 되..

• List vs Deque(Stack or Queue) 공통점 : 1차원 배열에 데이터를 저장한다.차이점 : 임의의 포지션에서 연산이 가능하다.(Index로 주어지는 위치에서 삽입/삭제 가능) • 부가연산empty(): 리스트가 비어있으면 true를 반환한다.full() : 리스트가 가득 차있으면 true를 반환한다.size() : 리스트의 아이템들의 개수를 반환한다.  • 메인연산insert(i, item) : 새로운 아이템을 i번째 위치에 삽입한다.remove(i) : i번째 위치의 아이템을 삭제한다.get(i) : i번째 위치의 아이템을 반환한다.replace(i, item) : 아이템과 i번째 위치의 아이템을 교체한다.find(item) : 아이템의 인덱스(위치)를 반환한다.*find(itme)..

부모 클래스에 만들어진 필드와 메소드를 자식 클래스가 물려받는 것이다.동일한 특성을 재정의할 필요가 없어 자식 클래스가 간결해진다. 자바에서는 부모 클래스를 슈퍼 클래스, 상속받는 자식 클래스를 서브 클래스라고 부른다.  • 서브 클래스/슈퍼 클래스의 생성자 호출 및 실행 new에 의해 서브 클래스의 객체가 생성될 때 슈퍼클래스 생성자와 서브 클래스 생성자가 모두 실행된다. 호출 순서 : 서브 클래스의 생성자가 먼저 호출, 서브 클래스의 생성자는 실행 전 슈퍼 클래스 생성자 호출실행 순서 : 슈퍼 클래스의 생성자가 먼저 실행된 후 서브 클래스의 생성자가 실행된다. 원칙적으로 서브 클래스의 개발자가 서브 클래스의 각 생성자에 대해 함께 실행될 슈퍼 클래스의 생성자를 지정해야 한다.하지만 개발자의 명시적 지..