본문 바로가기

2-1 학기20

[자료구조] 힙(Heap) 우선 순위 큐(Priority Queue) 우선순위 큐에서는 우선순위가 가장 높은(또는 가장 낮은) 원소를 먼저 삭제한다. 또 언제든지 임의의 우선순위를 가진 원소를 우선순위 큐에 삽입할 수 있다. template class MaxPQ{ public: virtual ~MaxPQ(){ }// 가상 파괴자 virtual bool IsEmpty() const = 0;// 우선순위 큐가 공백이면 true 반환 virtual const T& Top() const = 0;// 최대 원소에 대한 참조를 반환 virtual void Push(const T&) = 0;//우선순위 큐에 원소를 삽입 virtual void Pop() = 0;// 최대 우선순위를 가진 원소 삭제 }; 시간 복잡도 IsEmpty(): O(1).. 2023. 5. 29.
[자료구조] 트리(Tree) 트리(Tree) 트리(Tree)는 원소들 간에 1 : N 관계를 가지는 비선형 자료구조이다. 한 개 이상의 노드(node)로 이루어진 유한 집합으로서 노드 중에는 루트(root)라고 하는 노드가 하나 있고 나머지 노드들은 n(>=0)개의 분리집합 T1, ,,, Tn으로 분할될 수 있다. 여기서 T1, ,,, Tn은 각각 하나의 트리이며 루트의 서브트리(subtree)라고 한다. 한 노드의 서브트리의 수를 그 노드의 차수(degree)라고 한다. 예를 들어 트리의 구조가 다음과 같을 때, A의 차수는 3이고, C의 차수는 1, L의 차수는 0이다. 차수가 0인 노드를 리프(leaf) 또는 단말 노드(terminal node)라 한다. 그 외의 나머지 노드들은 비단말 노드(nonterminal node)라 .. 2023. 5. 29.
[논리회로] 카운터(Counter) 카운터(Counter) 미리 정해진 상태천이 순서를 순환하면서 클럭 펄스의 수를 카운트하는 소자(장치)이다. 세는 방향에 따른 분류 상향 카운팅 혹은 하향 카운팅으로 나눌 수 있다 클럭을 가하는 형태에 따른 분류 동기식 카운터, 비동기식 카운터 3비트 Up/Down 카운터는 입력 값에 따라 up, down 하는 것을 말한다. 입력값이 0인 경우 up을 하고, 입력값 1인 경우 down을 한다. 2023. 5. 28.
[논리회로] 플립플롭(Flip-Flop) 플립플롭(Filp - Flop) 입력의 변화가 없으면 출력이 일정한 2진값을 유지하도록 동작되는 기억소자이다. 출력이 변화를 일으키는 시점에 따라 동기식, 비동기식으로 나뉜다. 비동기식 플립플롭 입력의 변화에 따라 출력을 변화시킬 수 있는 플립플롭(latch) 동기식 플립플롭 입력이 아무리 변해도 동기신호가 출력을 변화시킬 시점이 아니면 출력의 변화가 일어나지 않는 플립플롭 Rising-edge triggered SR Filp-Flop EN = 1일 때 기본 래치가 동작하며, EN = 0일 때 래치의 출력은 변화하지 않는다. Falling-edge triggered SR Filp-Flop Master-slave Filp-Flop 주종 플립플롭은 2개의 플립플롭과 1개의 인버터로 구성하며 시간 펄스가 상승.. 2023. 5. 28.
[논리회로] 래치(Latch) 래치(Latch) 래치는 순차회로에서 한 비트의 정보를 저장하는 회로이다. 인에이블(허용)이 되면 레벨을 감지하여 입력값을 출력으로 계속해서 전송한다. NOR형 SR래치 S는 Set, R은 Reset을 의미하며, 두 개의 입력에 따라 두 개의 출력을 가진다. S R Q Q' 0 0 q q 0 1 0 1 1 0 1 0 1 1 X X 여기서 q란 과거의 값을 의미한다. 즉, S와 R이 0이면 과거의 값이 보존된다. + 래치는 Enable에 의해 회로가 동작하는 반면, 플립플롭은 CLK에 의해 회로가 동작한다. NAND형 SR래치 NAND형 SR래치에서 주의해야 할 점은 입력으로 inverting된 값이 들어간다는 것이다. S R Q Q' 0 0 X X 0 1 1 0 1 0 0 1 1 1 q q SR latc.. 2023. 5. 28.
[JAVA] 업캐스팅과 instanceof 연산자 업캐스팅 업캐스팅이란 서브클래스의 객체에 대한 래퍼런스를 슈퍼 클래스 타입으로 변환하는 것을 말한다. 업캐스팅한 래퍼런스로는 객체 내에 모든 멤버에 접근할 수 없고 슈퍼 클래스의 멤버만 접근할 수 있다. class Person{ } class Student extends Person{ } public class UpcastingEx{ public static void main(String[] args){ Person p; Student s; p = s; } } 다운캐스팅 업캐스팅과 반대로 캐스팅하는 것을 다운캐스팅이라고 한다. class Person{ String name; String id; public Person(String name){ this.name = name; } } class Studen.. 2023. 5. 23.
[JAVA] 추상 클래스 vs. 인터페이스 추상 클래스 추상 클래스(abstract class)란 선언은 되어 있으나 코드가 구현되어 있지 않은, 즉 껍데기만 있는 메소드이다. abstract 키워드와 함께 원형만 선언하고 코드는 작성하지 않는다. 추상 클래스(abstract class)가 되는 경우는 다음 2가지이다. 1. 추상 메소드를 포함하는 클래스 abstract class Shape{ public Shape(){ } public void pain() {draw();} abstract public void draw(); } 2. 추상 메소드가 없지만 abstract로 선언한 클래스 abstract class MyComponent{ String name; public void load(String name) { this.name = name.. 2023. 5. 23.
[JAVA] 상속 상속 자바에서 상속이란 아래 클래스가 위 클래스를 상속받아 확장함(extend)을 뜻한다. 부모 클래스는 슈퍼 클래스(super class), 상속받는 자식 클래스를 서브 클래스(sub class)라 부른다. 상속을 선언할 때는 extends 키워드를 사용한다. public class Person{ } public class Student extends Person{ //Person을 상속받는 클래스 Student 선언 } public class StudentWorker extends Student{ //Student를 상속받는 클래스 StudentWorker 선언 } Student 클래스는 Person 클래스의 멤버를 물려받으므로, Person 클래스에 선언된 필드나 메소드를 다시 반복하여 작성할 필요.. 2023. 5. 9.

티스토리툴바