트리 하나 이상의 노드로 이루어진 유한 집합 - 하나의 루트 노드 - 나머지 노드들은 n(≥0) 개의 분리 집합 \(T_{1}, T_{2},..., T_{n}\)으로 분할 - \(T_{i}\): 루트의 서브트리 노드 한 정보 아이템 + 다른 노드로 뻗어진 가지 노드의 차수(degree) 노드의 서브트리 수 단말(리프) 노드 차수 = 0 비단말 노드 차수 ≠ 0 자식 노드 X의 서브트리의 루트 형제 부모가 같은 자식들 트리의 차수 노드의 차수의 최댓값 조상 루트까지의 경로상에 있는 모든 노드 레벨 루트 == 레벨1, 자식 레벨 == 부모 레벨 + 1 높이(깊이) 노드 레벨의 최댓값 트리의 리스트 표현 (A(B(E(K,L),F),C(G),D(H(M),I,J))) - 차수가 k인 트리에 대한 노드 구조 트리 ..

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

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

희소 행렬(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;..

시스템 생명 주기(System Life Cycle) 요구사항 시스템의 요구 사항을 파악, 분석 시스템이 무엇을 해야 하는지, 어떤 기능이 있어야 하는지, 사용자의 기대는 무엇인지 결정 분석 시스템의 동작, 기능 및 특성을 정의 시스템의 다양한 구성 요소, 시스템의 관계 및 상호작용 방식을 식별 설계 다양한 구성 요소, 구성 요소 간의 관계 및 인터페이스를 포함하여 시스템의 아키텍처 설계 시스템 구현에 대한 세부 계획 개발 정제와 코딩 설계 정교화, 소프트웨어 코드화 디자인을 컴퓨터에서 실행할 수 있는 코드로 변환 코드 작성, 테스트 및 디버깅 포함 검증 시스템을 테스트하여 요구사항을 충족하고 오류가 없는지 확인 사용자의 기대를 충족하고 의도한 대로 작동하는지 확인 객체 지향 설계 구조적 프로그래밍 설계와..