추상 메소드 선언되어 있으나 구현되어 있지 않은 메소드 public abstract String getName(); public abstract void setName(String s); 추상 메소드는 서브 클래스에서 오버라이딩하여 구현해야 함 추상 클래스 추상 메소드를 하나라도 가진 클래스 → 클래스 앞에 반드시 abstract라고 선언해야 함 추상 메소드가 하나도 없지만 abstract로 선언된 클래스 추상 클래스는 객체 생성 불가 추상 클래스의 상속 1. 추상 클래스의 단독 상속 추상 클래스를 상속받아 메소드를 구현하지 않으면 추상 클래스 됨 서브 클래스도 abstract로 선언해야 함 abstract class Shape { // 추상 클래스 public Shape() { } public void..

스택(stack) - 한쪽 끝(top)에서 모든 삽입(push)과 삭제(pop)가 일어나는 순서 리스트 - 후입선출(LIFO, Last-In-First-Out) 리스트 시스템 스택 - 프로그램 실행시 함수 호출을 처리 - 프로그램은 함수 호출시 활성 레코드 또는 스택 프레임 구조를 생성하여 시스템 스택의 톱에 둠 이전의 스택 프레임에 대한 포인터 복귀 주소 지역 변수 매개 변수 - 함수가 자기자신을 호출하는 순환 호출도 같은 방식으로 처리 스택 구현 template class Stack { private: T *stack; // 스택 원소를 위한 배열 int top; // top 원소의 위치 int capacity; // 스택 배열의 크기 public: Stack(int stackCapacity = 10..

스트링 추상 데이터 타입 문자열(string) \(S = s_{0}, s_{1}, ... , s_{n-1}\)의 형태 - \(s_{0}\): 문자 집합의 원소 - n = 0: 공백 또는 널 문자열 연산 - 새로운 공백 문자열 생성 - 문자열 읽기, 출력 - 문자열 연결(concatenation) - 문자열 복사 - 문자열 비교 - 서브스트링을 스트링에 삽입 - 스트링에서 서브스트링 삭제 - 스트링에서 특정 패턴 검색 class String { public: String(char *init, int m); // m의 길이로 문자열을 초기화하는 생성자 bool operator==(String t); // 문자열 비교 bool operator!(); // 문자열이 비어 있으면 true, 그렇지 않으면 fals..

희소 행렬(Sparse matrix)a[m][n]- m x n 행렬 am: 행의 수n: 열의 수m x n: 원소의 수 - 희소 행렬0이 아닌 원소 수 / 전체 원소수 → 0이 아닌 원소만 저장한다면 시간과 공간 절약 - 행렬에 대한 연산생성(Creation)전치(Transpose)덧셈(Addition)곱셈(Multiplication) 희소 행렬 표현 3 원소 쌍으로 식별class MatrixTerm{friend class SparseMatrix;private: // 행 번호, 열 번호, 값 int row, col, value;};class SparseMatrix{private: // 행, 열, 0이 아닌 항의 총수, 배열크기 int rows, cols, terms, capacity;..

다항식 추상 데이터 타입 순서 리스트 - 예시 요일 트럼프 카드 한 벌의 값 주차별 수업 날짜 - 리스트 형태: (\(a_{1}, a_{2}, ... , a_{n-1}\)) - 공백 리스트의 예: ( ) 순서 리스트에 대한 연산 리스트 길이 n의 계산 리스트의 항목을 왼쪽에서 오른쪽(오른쪽에서 왼쪽)으로 읽기 리스트로부터 i번째 항목을 검색, 0≤i

공간복잡도 프로그램을 실행시켜 완료하는 데 필요한 메모리 양 - 고정 부분: 보통 명령어 공간, 단순 변수, 집합체, 상수를 위한 공간 - 가변 부분: 특정 문제의 인스턴스에 따라 크기가 달라지는 변수, 순환 스택 공간 프로그램 P의 공간 요구 S(P) = c + Sₚ - c: 상수 - Sₚ: 인스턴스 특성 예시 float Abc(float a, float b, float c) { return a+b+b*c+(a+b-c)/(a+b)+4.0; } // Sₚ = 0 inline float Sum(float *a, const int n) { float s=0; for(int i=0;i

이원 탐색 이미 정렬된 배열 a[0] ... a[n-1]에서 x=a[j]인 j를 반환 - left, right: 탐색하고자 하는 리스트의 왼쪽, 오른쪽 끝 - 초기값 left = 0, right = n-1 - 리스트의 중간 위치 middle = (left/right)/2 - a[middle]과 x 비교 1) x right = middle-1 2) x = a[middle] -> middle 반환 3) x > a[middle] -> left = middle+1 int BinarySearch(int *a, const int x, const int n) { // 정렬된 배열 a[left], ..., a[right]에서 x 탐색 int left = 0, right = n - 1; whi..

선택정렬 n ≥ 1개의 서로 다른 정수의 집합을 정렬 정렬되지 않은 정수들 중에서 가장 작은 값을 찾아서 정렬된 리스트 다음 자리에 배치 void SelectionSort(int *a, const int n) { //n개의 정수 a[0]부터 a[n-1]까지 오름차순으로 정렬 for (int i = 0; i < n; i++) { int j = i; //a[i]와 a[n-1] 사이에 가장 작은 정수 탐색 for (int k = i + 1; k < n; k++) if (a[k] < a[j]) j = k; swap(a[i], a[j]); //swap함수는 두 수의 위치를 교환 } } 시간복잡도 - O(n) //n은 배열 a의 크기

메소드 오버라이딩(Method Overriding) 슈퍼 클래스의 메소드를 서브 클래스에서 재정의 슈퍼 클래스 메소드의 이름, 매개변수 타입 및 개수, 리턴 타입 등 모든 것 동일하게 작성 메소드 무시하기, 덮어쓰기 동적 바인딩 발생 - 서브 클래스에 오버라이딩 된 메소드가 무조건 실행되는 동적 바인딩 메소드 오버라이딩 사례 class Shape { public void draw() { System.out.println("Shape"); } } class Line extends Shape { public void draw() { //오버라이딩 System.out.println("Line"); } } class Rect extends Shape { public void draw() { //오버라이딩 Sys..

객체지향의 상속 부모클래스에 만들어진 필드, 메소드를 자식클래스가 물려받음 부모의 생물학적 특성을 물려받는 유전과 유사 상속을 통해 간결한 자식 클래스 작성 동일한 특성을 재정의할 필요가 없어 자식클래스가 간결해짐 장점 클래스의 간결화 - 멤버의 중복 작성 불필요 클래스 관리 용이 - 클래스들의 계층적 분류 소프트웨어의 생산성 향상 - 클래스 재사용과 확장 용이 - 새로운 클래스의 작성 속도 빠름 자바의 상속과 객체 상속 선언 - extends 키워드 사용 -> 슈퍼 클래스를 확장한다는 개념 부모 클래스 자식 클래스 슈퍼 클래스 서브 클래스 클래스 상속 만들기 - Point와 ColorPoint 클래스 class Point { private int x, y; //한 점을 구성하는 x, y 좌표 publi..