Campus Coder

연결 스택과 큐 연결 스택 top에서 노드 삽입, 삭제 용이 top: 스택의 톱 노드를 가리키는 전용 데이터 멤버 초기엔 top = 0 template void LinkedStack::Push(const T &e) { top = new ChainNode(e, top); } template void LinkedStack::Pop() { // 스택의 첫 번째 노드를 삭제 if (IsEmpty()) throw "Stack is empty. Cannot delete."; ChainNode *delNode = top; top = top->link; // top노드를 삭제 delete delNode; // 메모리 할당 해제 } 연결 큐 rear에서 노드 삽입 용이 front에서 노드 삽입, 삭제 용이 rear: 큐..

원형리스트 원형 리스트(circular list) - 체인에서 마지막 노드의 link 필드가 첫 번째 노드를 가리킴 - 포인터 current가 마지막 노드를 가리키는지 검사할 때, current->link == 0이 아니라 current->link == first로 검사 - 삽입, 삭제 함수에서 마지막 노드의 link 필드가 첫 번째 노드를 가리키는지 연산이 끝난 후 확인 원형 리스트 예시 ↙ ← ← ← ← ← ← ← ← ↖ first → [data | link] → [data | link] → [data | link] 리스트 앞에 새 노드 삽입 - 마지막 노드의 link를 변경해야 하므로 접근 포인터가 마지막 노드를 가리키는 편이 편리 template void CircularList::InsertFro..

반복자(iterator) 반복자의 필요성 컨테이너 클래스의 종류에 따라 최대값을 찾는 구현 코드가 다름 - ex) 배열과 체인에 대해 최대값을 찾는 코드가 다르다 내부 구조의 이해 없이 컨테이너에 저장된 객체를 이용할 수 있는 반복자 필요 C++ 반복자 - 객체의 원소에 대한 포인터 - 객체의 원소를 하나씩 지나가도록 지원 C++ STL 반복자의 부류 입력 출력 전방 양방 임의접근 반복자 지원 연산 참조 연산자 * 동등 연산자 ==, != 반복자 전진 ++, 감소 -- 포인터 산술 연산, 임의의 양 점프 +=, -= Chain에 대한 전방 반복자 Chain을 위한 전방 반복자 클래스 class ChainIterator { private: ChainNode *current; public: // C++ 데..

단순 연결 리스트 순차 표현(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..

추상 메소드 선언되어 있으나 구현되어 있지 않은 메소드 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..