Campus Coder

스트링 추상 데이터 타입 문자열(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 행렬 a m: 행의 수 n: 열의 수 m x n: 원소의 수 - 희소 행렬 0이 아닌 원소 수 / 전체 원소수 0) // 행렬의 모든 값이 0이 아니라면 작업 시작 { int *rowSize = new int[cols]; int *rowStart = new int[cols]; // rowSize[i] = b의 행 i에 있는 항 수 fill(rowSize, rowSize + cols, 0); // 위의 표처럼 배열을 초기화 for (i = 0; i < terms; i++) rowSize[smArray[i].col]++; // rowStart[i] = b에서 행 i의 시작 위치 rowStart[0] = 0; for (i = 1; i < col..

다항식 추상 데이터 타입 순서 리스트 - 예시 요일 트럼프 카드 한 벌의 값 주차별 수업 날짜 - 리스트 형태: (\(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의 크기

입출력 함수 오버로딩 매개변수 디폴트 값 이름공간 1. 헤더파일 선언/입출력의 기본구성/개행의 진행 #include //헤더파일 선언 int main(void) { int num; std::cout

메소드 오버라이딩(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..

https://www.acmicpc.net/problem/11659 11659번: 구간 합 구하기 4 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j www.acmicpc.net 풀이 수를 입력받아서 배열에 저장 - 배열에 각각 저장해서 더하면 시간 초과 -> 배열에는 배열의 이전 인덱스의 값과 입력받은 수의 합 저장 배열에서 합을 구해야 하는 구간 (끝 부분) 인덱스 값 - (처음 부분 - 1) 인덱스 값을 구하면 i~j번째 수의 합 답 #include using namespace std; int main(void) { ios::sync_with_..