[컴퓨터구조] #9 Pipeline
·
CS/컴퓨터구조
• Piplelined Processing 중복 실행 방법에서 새로운 작업은 현재 작업 Set 중 첫번째 작업이 끝나면 시작될 수 있다.아래의 그림을 비교해보면 이해가 쉽다. pipeline에서도 sigle-cycle에서 공부했던 5가지 단계가 동일하게 적용된다.(IF/ID/EX/MEM/WB) • Pipelined Performance 파이프라인을 통해 성능향상이 많이 이루어진 것을 확인해볼 수 있다. 그러나 만약 balanced 되어있지 않으면, 성능향상은 작아진다.또한 각 명령어 당 수행시간은 감소하지 않는다. RISC-V ISA는 파이프라이닝에 적합한데, 이는 32-bit 고정 길이 명령어를 가지고 있고, 제한된 명령어 포맷과 load/store 주소지정방식을 가지고 있기 때문이다. • Piplin..
[객체지향프로그래밍] #6 모듈과 패키지
·
CS/객체지향프로그래밍
프로그램을 작성하다 보면 두 객체가 같은지 비교해야 하는 상황이 있다. • == 연산자== 연산자는 두 레퍼런스가 동일한 객체를 가리키는지 비교한다.Point a = new Point(2,3);Point b = new Point(2,3);Point c = a;if(a == b) // false System.out.println("a==b"):if(a == c) // true System.out.println("a==c"): 실행결과 : a==c 위의 코드가 실행되면 2개의 Point 객체가 생성되고, 레퍼런스 a와 b는 이들을 각각 가리킨다. • boolean equals(Object obj)equals는 인자로 건네진 객체 obj와 자기 자신을 비교하여 두 객체의 내용이 같은지를 비교하는 메..
[자료구조] #19 Heap(2)
·
CS/자료구조
• 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 +..
[자료구조] #18 Heap(1)
·
CS/자료구조
• 우선순위(Priority) 어떤 일을 먼저 처리할지 순서를 정하는 것이다.  • 우선순위 큐 우선순위의 개념을 큐에 적용한 자료구조이다.우선순위를 가진 데이터를 저장하며 우선순위가 높은 데이터가 먼저 나가게 된다.  • 우선순위 큐의 ADT 데이터item = (여기서는 key = value = priority라고 심플하게 하자.) 주요 연산insert(item) : 우선순위 큐에 item을 추가remove: 우선순위가 가장 높은 요소를 삭제하고 반환find() : 우선순위가 가장 높은 요소를 삭제하지 않고 반환 우선순위 큐의 종류최소 우선순위 큐 :  우선순위가 작을수록 우선순위가 높음최대 우선순위 큐 : 우선순위가 클수록 우선순위가 높음  • 우선 순위 큐의 구현 방법 1. 배열을 이용해서 구현 ..
[컴퓨터구조] #8 Processor
·
CS/컴퓨터구조
이제 실제 프로세서로 구현하면 어떻게 될지 알아보도록 하자. • 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..
[자료구조] #17 Binary Search Tree(2)
·
CS/자료구조
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..
[자료구조] #16 Binary Search Tree(1)
·
CS/자료구조
• 탐색(Search) 특정 자료구조 내에 저장된 정보를 찾아내는 일이다.방대하게 저장된 데이터에서 원하는 정보를 효율적으로 찾아내는 것은 중요하다. n개의 아이템을 가지는 1차원 배열에서 원하는 값을 찾기 위해 가장 간단한 방법은 순차 탐색이다.그러나 순차 탐색은 최악의 경우 O(n)의 시간 복잡도를 요구한다.(마지막에 있거나 아예 없거나) 그렇다면 Insert/remove/search 등을 O(n) 보다 더 빠르게 할 수 있는 방법은 없을까? 탐색을 위해 특화된 이진 트리인 이진 탐색 트리에 대해 알아보도록 하자. • Key & Value 트리에서 노드는 key와 value를 가진다.Key : 해당 노드를 다른 노드와 구분 짓게 하는 식별자(ID)를 의미한다.Value : key에 대응되는 데이터 값..
[자료구조] #15 Tree(2)
·
CS/자료구조
• 이진 트리의 순회 순회는 자료구조 내의 데이터를 특정 순서대로 방문하는 것을 의미한다. 선형 자료구조에서의 순회선형적인 순서로 조회한다.이진 트리에서의 순회트리는 비선형 자료구조이기 때문에 여러가지 순서로 노드를 방문할 수 있다. • 이진 트리의 순회 방법 전위 순회(pre-order traversal)루트 출력 → 왼쪽 서브트리 → 오른쪽 서브트리def preorder(node): if node is not NULL: # 현재 노드가 NULL이 아닌 경우에만 수행 print(node.data) # 현재 노드의 데이터를 출력 preorder(node.left) # 왼쪽 자식 노드를 전위 순회 preorde..
[자료구조] #14 Tree(1)
·
CS/자료구조
• Tree 트리는 계층적인 구조를 나타낼 수 있는 자료구조이다.부모-자식 관계의 노드들로 이루어져 있다. • 트리의 용어 노드(node) : 트리의 구성요소루트(root) 노드 :  제일 상단에 있는 노드(부모가 없는 노드)간선(link, edge) : 노드와 노드를 연결하는 선서브트리(subtree) : 하나의 노드와 자손들로 이루어짐 단말노드(terminal, leaf, external) : 자식이 없는 노드비단말노드(brach, internal) : 자식을 가지는 노드 자식, 부모, 형제, 조상 노드특정 노드를 기준으로 가족 관계를 따진다. 노드의 차수(degree) : 노드의 자식 노드 수노드의 깊이(depth) : 루트 노드에서 특정 노드까지의 간선의 수노드의 레벨(level) : 트리의 계층..
[자료구조] #12 Recursion(1)
·
CS/자료구조
• Recursion Recursion = 재귀함수단 몇개의 문자만으로 문제의 solution을 구할 수 있다.다만 반드시 효율적이지는 않으며, 모든 문제가 재귀적으로 풀리지는 않는다. • 일반적인 Format 1) Simple base case : 더 이상 재귀호출을 진행하지 않고 정답을 생성한다.2) Recursive step : 함수가 재귀적으로 호출된다.모든 재귀함수는 점진적으로 base case로 이동한다. 아니면 무한 loop에 빠진다. 만약 base case가 없다면?스택이 용량이 초과되어 overflow error가 발생할 것이다. • Recursion 푸는 방법 Divide & Conquer : 작은 문제로 나눠주고 각각 풀어준다.우선 가정을 하고 설계한다! 그럼 어떻게 올바른 계산이 되..