Campus Coder

단순 연결 리스트 순차 표현(sequential) - 연속된 원소들이 일정한 거리만큼 떨어져서 저장 - 임의 원소 접근, 스택이나 큐의 원소 삽입/삭제에 적합 - 순서 리스트에서 임의 원소의 삽입/삭제 비용 큼 더보기 ex) 오름차순 내림차순 배열의 경우 중간에 수를 삽입 또는 삭제하면 다른 원소들을 이동해야함 연결된 표현(linked) - 각 원소들이 기억 장소 내의 어떤 곳에나 위치 - 노드: [데이타 | 링크(포인터)] [데이타 | 링크(포인터)] → [데이타 | 링크(포인터)] → [데이타 | 링크(포인터)] → ... → [데이타 | 0] 노드 삽입 현재 사용하고 있지 않은 노드 a 할당 노드 a의 data 필드에 데이터 설정 노드 a의 link 필드가 삽입하려는 위치 다음 노드를 가리키도록 설..

수식 - 피연산자, 연산자, 분리자로 구성 - 수식의 의미를 이해하기 위해 연산의 수행 순서를 파악해야 함 - 계산 순서를 고정하기 위해 각 연산자에 우선순위를 지정해야 함 식의 표현 - 중위 표기식: A * B / C - 후위 표기식: A B * C / - 전위 표기식: / * A B C 후위표기식 - 괄호가 불필요 - 연산자 우선순위 불필요 - 계산 과정이 간단(왼쪽에서 오른쪽) 중위 표기에서 후위표기 변환 알고리즘 식을 전부 괄호로 묶음 이항 연산자들을 모두 자기 오른쪽 괄호로 이동 괄호를 전부 삭제 더보기 예시) A/B-C+D*E-A*C ((((A/B)-C)+(D*E))-(A*C)) AB/C-DE*+AC*- 이때 피연산자의 순서는 불변 A+B*C → ABC*+ 다음 토큰 스택 출력 없음 공백 없음..

미로 문제 maze는 1≤i≤m이고 1≤j≤p인 이차원 배열 maze[i][j]로 표현 1 - 막혀있음 0 - 통과 가능 현재의 위치 x: maze[i][j] 미로의 경계면에 있을 때 경계 조건을 매번 검사하는 것을 피하기 위해 미로의 주위를 1로 둘러쌈 배열은 maze[m+2][p+2]로 선언 이동할 수 있는 방향들을 배열 move에 미리 정의 struct offsets { int a, b; }; enum directions {N, NE, E, SE, S, SW, W, NW} offsets move[8]; q move[q].a move[q].b N -1 0 NE -1 1 E 0 1 SE 1 1 S 1 0 SW 1 -1 W 0 -1 NW -1 -1 세 배열 maze, mark, move 사용 새로운 3원..

템플리 함수 - 클래스와 함수의 재사용에 기여 - 소프트웨어 개발 시간과 저장 공간을 절약 예시 template void SelectionSort(T *a, const int 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 함수 또한 템플릿화 시켜줘야 전체 함수가 올바르게 작동 } } 함수를 템플릿화 하면 기존 정수 대상으로만 작동했던 함수가 실수 대상으로도 작동 컨테이너 클래스 - 다수의 데이터 객체들을 수용 또는 저장하는 자료구조..

큐(queue) - 한쪽 끝에서 삽입이 일어나고 반대쪽 끝에서 삭제가 일어나는 순서 리스트 - 선입선출(FIFO, Firest-In-First-Out) 리스트 새로운 원소가 삽입되는 끝 - rear 원소가 삭제되는 끝 - front 큐의 구현 1차원 배열 이용 더보기 1. 큐의 첫 번째 원소를 queue[0]로 표현한 큐 - 삭제: queue[0] 원소를 제거 - 삭제 후 나머지 원소들을 왼쪽으로 이동해야 함 → 시간복잡도 - O(n) 비효율적 2. 큐의 첫번째 원소를 queue[front]로 표현한 큐 - 변수 fornt를 사용하여 큐의 첫번째 위치를 항상 유지 - 삭제: 시간복잡도 - Θ(1) - 큐의 원소: queue[fornt], ..., queue[rear] - 배열 queue의 크기가 capa..

스택(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 행렬 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