공부 기록장 💻

삽입과 삭제가 한 곳(top)에서만 이루어는 후입선출(LIFO)의 입출력 구조를 가졌던 스택(Stack)과 달리, 배열의 양 끝에서 입력과 출력이 이루어지는 큐(Queue)에 대해서 알아보자! 큐(Queue) 큐(Queue) 는 리스트의 앞 부분에서는 삭제가, 뒷 부분에서는 삽입이 이루어지는, 먼저 삽입된 자료가 먼저 삭제되는 선입선출(FIFO)의 입출력 구조로 운영된다. 다음과 같은 전단(front)과 후단(rear)이 리스트의 양 끝을 가리키게 된다. - 전단(front) : 데이터의 삭제 연산 (가장 먼저 들왔던 데이터가 쌓여있는 쪽) -> dequeue() 연산 - 후단(rear) : 데이터의 삽입 연산 (가장 나중에, 최근에 삽입된 데이터가 쌓여있는 쪽) -> enqueue() 연산 큐의 ADT..

#include #include #define MAX_STACK_SIZE 100// 스택의 크기 #define MAZE_SIZE 6// 6*6 미로 // 좌표(x,y)로 구성된 스택 typedef struct StackObjectRec { short r;// row short c;// column }StackObject; StackObject stack[MAX_STACK_SIZE];// x,y 좌표로 구성된 스택 선언 int top = -1; // top 값 초기화 StackObject here = { 1,0 };// 미로 탐색하며 이동하는 현재 위치값 StackObject entry = { 1,0 };// 미로의 시작 위치 // 미로 - 이동 가능한 경로는 '0'으로 표시, 출구는'x'로 표시 char..

연결리스트에서 head가 가리키는 값에 새로운 노드를 추가하는 구조와 스택 구조는 매우 유사하다. 첫 부분에 노드를 추가하는 (insert_first) 연결 리스트와 구조가 유사하며 top을 가리키는 포인터가 있다는 것만 조금 다르다. // 연결리스트를 이용한 스택 구조 #include #include typedef int StackObject; // Object에 대한 structure과 object를 담은 스택 typedef struct StackRec { StackObject item; // 데이터필드 struct StackRec* link; // 링크필드 : next item의 주소를 담은 포인터 }StackRec; // link 포인터를 따라가며 가장 마지막에 삽ㅇ비한 StackRec의 Obje..

y = a * (b-c) + d/c 수식(expression)은 연산자, 피연산자, 괄호로 이루어져 있다. 연산자들은 우선순위가 있어 우선순위가 높은 연산자가 먼저 계산된다. 위의 수식에서는 괄호 내의 식이 가장 우선순위가 높기 때문에, 괄호 안의 뺄셈이 가장 먼저 계산되고, 이어서 곱셈, 나눗셈, 덧셈 순으로 계산된다. 중위표기 수식 : y=a*(b-c)+d/c 후위표기 수식(postfix notation) : y=abc-*dc/+ 프로그래머가 수식을 연산자가 피연산자 사이에 위치한 중위표기법으로 작성하면, 컴파일러는 이것을 연산자가 피연산자 뒤에 위치하는 후위표기법으로 변환한 후에 스택을 이용해 계산한다. 후위 표기법을 사용하는 이유는? 1. 괄호가 필요 없다. 괄호를 쓰지 않고도 우선 계산하여야 할..

data.txt {A[(i+1)]=0} {B[100-(i+5)]*5} {C/(5/5*(5-4)} (10+5)-(30-20) 전체 코드 : #include #include #define MAX_STACK_SIZE 100 typedef char element; typedef struct{ element data[MAX_STACK_SIZE]; int top; }StackType; void init_stack(StackType* s) { s->top = -1; } int is_empty(StackType* s) { return (s->top == -1); } int is_full(StackType* s) { return (s->top == (MAX_STACK_SIZE - 1)); } void push(Stack..

스택이란? 스마트폰, 컴퓨터에서 '뒤로 가기'(undo 기능 - Ctrl+z)와 같은 기능, 혹은 일상생활에서 볼 수 있는 책상 위에 쌓여있는 책 등과 같이 자료가 차곡차곡 쌓여있는 구조를 스택 형태의 예라 할 수 있다. 순환 호출 시, 함수가 호출될 때마다 복귀 주소가 저장되는 활성 레코드가 운영체제가 사용하는 시스템 스택에 쌓이는 것 또한 컴퓨터 내의 스택의 사용 예이다. 최근에 들어온 자료가 가장 위에 있게 되고, 먼저 나가게 되는 구조가 바로 스택이고, 이러한 입출력 형태를 후입선출(LIFO: Last-In First-Out)이라고 한다. 스택에 저장되는 데이터를 요소(element)라 부른다. 스택에서 요소에 대한 입출력이 이루어지는 부분을 스택 상단(stack top)이라 하고, 반대쪽 바닥 ..

컴퓨터 산술과 논리 연산 ALU의 구성 요소 - 산술 연산 장치: +, -, *, % 수행 - 논리 연산 장치 : 논리 연산(AND, OR, XOR, NOT 등) 수행 - 시프트 레지스터(shift register) : 비트들을 좌측, 우측으로 이동시키는 기능을 가진 레지스터 -> 플래그들 출력 - 보수기(complementer) : 2진 데이터를 2진 보수로 변환(음수화) - 상태 레지스터(status register) : 연산 결과의 상태를 나타내는 플래그(flag)들을 저장하는 레지스터 16-비트 부호화 크기 표현 +21 = 00010101 (8-비트 부호화-크기 표현) +21 = 0000000000010101 (16-비트 부호화-크기 표현) - 21 = 10010101 (8-비트 부호화-크기 표현..

명령어 파이프라이닝(Instruction Pipelining) CPU의 프로그램 처리 속도를 높이기 위해ㅣ CPU 내부 하드웨어를 여러 단계로 나누어 동시에 처리하는 기술 2-단계 명령어 파이프라인(Two-Stage Instruction Pipeline) 명령어를 실행하는 하드웨어를 1) 인출 단계(fetch stage), 2) 실행 단계(execute stage) 라는 두 개의 독립적인 파이프 라인 모듈로 분리한 파이프라인 기법이다. - 문제점 : 두 단게의 처리 시간이 동일하지 않으면 두 배의 속도 향상을 얻지 못하고 파이프라인의 효율이 저하된다. (fetch 단계와 execute 단계의 실행 속도 차이가 나므로 싱크가 맞지 않아 하나의 단계가 다른 단게가 끝마칠 때 까지 대기해야 하는 상황 발생) ..

CH2. CPU의 구조와 기능 CPU가 수행하는 세부적인 동작들의 순서 ((3)~(5) 과정은 명령어에 따라 필요한 경우에만 동작 수행) (1) 명령어 인출(Instruction Fetch) : 기억장치로부터 명령어를 읽어옴 (2) 명령어 해독(Instruction decode): 수행해야 할 동작을 결정하기 위해 명령어를 해독 (3) 데이터 인출(Data Fetch): 명령어 실행을 위해 데이터가 필요한 경우, 기억장치(Main Memory-RAM) 혹은 I/O장치(키보드, 파일 등)로부터 데이터를 읽어옴 (4) 데이터 처리(Data Process): 데이터에 대한 산술/논리 연산 수행 (5) 데이터 저장(Data Store): 수행 결과를 저장 2.1 CPU의 기본 구조 1. ALU(산술 논리 연산 ..

행렬(Matrix) - 기본적으로 연립 방정식을 풀기 위해 개발된, 수, 문자, 함수 등의 요소들을 네모꼴 괄호 안에 배열한 것 - 행렬의 각 성분은 실수여야 하고, 이를 스칼라라고 한다. - 크기 (m x n) 의 행렬 A가 있을 때, n쌍으로 된 m개의 수평 성분을 A의 행이라 하고, m쌍으로 된 n개의 수직 성분을 A의 열이라 한다. - 두 행렬 A와 B의 행과 열의 값이 모두 (m x n) 이고, 각각에 대응하는 원소가 모두 같으면 A = B라고 한다. 특수 행렬 - n차 정방 행렬(square matrix) : 행과 열의 수가 n으로 같은 행렬 (행과 열의 개수 = 정방 행렬의 차수) 주대각 성분(main diagonal) 원소 : n차 정방 행렬에서 대각선상에 위치한 원소 a(ii) 대각 행렬..

CH1 이산수학을 위한 기본 개념 1.1 이산수학 개념 1.2 이산수학 마술카드 문제 1.3 자연수와 정수 1.4 행렬 행렬 연산(행렬의 합, 차, 스칼라 곱, 곱) ✅ 특수 행렬 - 정방/대각/단위/전치/대칭/삼각/띠/특이/정칙/역/직교 행렬 ✅ 역행렬, 행렬식(소행렬식/여인수) ✅ 첨가/증가행렬, 가우스 조르단 소거법 부울 행렬(접합 / 교합 / 부울곱) ✅✅ 고유값, 고유벡터 구하기 CH2 수학적 모델과 논리 2.1 수학적 모델 2.2 논리적 추론 명제, 공리 논리 연산 논리곱 OR, 합 AND, 부정 NOT, 배타적 논리합 XOR ✅ 논리함축 -> ✅논리적 동치 ✅ 진리표 항진 명제 , 모순 명제 , 사건 명제 역 / 이 / 대우 항등 ✅ 명제의 표현: 술어, 한정자(전체 한정자∀, 존재 한정자∃..

내가 작성한 코드: (짝수번째 인덱스의 데이터 삭제 구현 실패) // data.txt 파일에 있는 숫자들을 읽어 연결리스트에 저장하고 출력, 탐색, 최대 최소 출력 #include #include typedef int element; typedef struct nArr { element data; struct nArr* link; }nArr; int main() { FILE* fp; nArr* list = NULL, * p, * prev=NULL, * next, *tmp=NULL; int getNum; int isEven = 0; element max, min; // 파일 열어 데이터 개수 저장 // 파일을 열어 파일의 끝이 아닐 때까지 계속 새로운 노드 생성하여 리스트에 삽입 fp = fopen("da..

단순 연결 리스트에서는 선행 노드에 접근하기 어렵다는 점을 개선하여, 원형 연결 리스트에서도 현재 노드의 바로 이전 노드를 접근하려면 전체 리스트를 한 바퀴 순회해야 하는 문제점이 있다. 이를 개선하여 양쪽 방향으로도 순회가 가능한 노드를 연결한 리스트인, '이중 연결 리스트'에 대해 알아보자. 이중 연결 리스트의 구조 - 하나의 노드가 선행 노드와 후속 노드에 대한 두 개의 링크를 가지는 리스트 - rlink(right link), llink(left link) - 헤드 노드(head node): 데이터를 가지고 있지 않은 노드 rrlink: 첫번째 데이터를 가지고 있는 다음 노드의 주소 llink: 마지막 데이터를 가지고 있는 노드의 주소 => 특별한 헤드 노드를 추가함으로써, 첫번째 노드와 마지막 ..

#include #define MAX_LIST_SIZE 10 #define TRUE 1 #define FALSE 0 typedef int element; typedef struct ArrayListType { element data[MAX_LIST_SIZE]; int size; }ArrayListType; // init_list void init_list(ArrayListType* L) { L->size = 0; } // is_full int is_full(ArrayListType* L) { return L->size == MAX_LIST_SIZE; } // is_empty int is_empty(ArrayListType* L) { return L->size == 0; } // insert_first v..

data.txt 2 이대호 80 75 90 75 1 박찬호 80 100 75 60 3 박세리 100 50 100 45 소스코드 : #include #include #include // 학생의 데이터를 담는 구조체를 새로운 타입 element로 정의 typedef struct student { int num; char name[20]; // 이름은 4글자까지 가능 int kor, math, eng, com; }element; // 이중 연결리스트의 자기참조구조체 구현 typedef struct DListNode { struct DListNode* llink; element data; struct DListNode* rlink; }DListNode; // 함수 원형 void init(DListNode* ph..

(C언어로 쉽게 풀어쓴 자료구조 연결리스트 Lab + 추가 변형) 1. 과일의 이름을 저장하는 단순 연결 리스트 (p.200) + 사용자로부터 직접 문자열 입력 받기 + 맨 앞의 노드에 해당하는 메모리를 반환하는 함수 delete_first 구현 * 주의할점 main 함수에서 저장된 각 동적 메모리를 반환하기 위해서 반복문을 이용하여 delete_first 함수를 호출할 때, delete_first 함수 내에서 이미 메모리를 반환하고 head의 값이 변경되고 있다는 점을 유의하여 작성해야 함. #include #include #include typedef struct { char name[100]; }element; typedef struct { element data; struct ListNode* l..

scores.txt 정우람 100.0 45.9 78.5 양현종 64.8 78.9 100 박해진 82.4 93.5 88.4 추신수 99.5 43.9 88.3 박찬호 100.0 99.9 78.5 이대호 88.9 99.9 78.9 강백호 85.4 78.6 31.5 이재학 82.4 93.5 78.4 #include #include typedef struct element { char name[20]; double kor, math, com, total; }element; typedef struct ListNode { element data; struct ListNode* link; }ListNode; ListNode* create_node(element data, ListNode* link); void inse..

2021/04/02 자료구조 실습 5주차 예제들 1. 1차원 배열: ISBN 문제 내가 작성한 코드: #include #define SIZE 13 int is_ISBN(int arr[], int size) { int sum = 0; for (int i = 0; i < size; i++) { if (i % 2) // 홀수번째인 경우 sum += arr[i]; else sum += 3 * arr[i]; // 짝수번째인 경우 3을 곱한 값을 저장 } if (sum % 10) // ISBN 코드가 올바르지 않음 return 0; else return 1; // 코드가 올바른 경우 } int main(void) { FILE* fp = fopen("data.txt", "rt"); int arr[SIZE]; for ..

(C언어로 쉽게 풀어쓴 자료구조 ch 3.3) 다항식의 표현 p(x) = a(x)^n a : 계수 x : 변수 n : 차수 구조체와 배열을 이용하여 다항식을 표현하는 두 가지 자료 구조를 알아보고, 덧셈 연산을 이용해 두 다항식에 대한 결과 값을 저장하는 방법을 살펴보자 최고 차항의 차수와 배열을 멤버로 갖는 구조체로 표현하여 하나의 다항식의 모든 항을 저장하는 구조체 변수로 선언하는 방법 계수가 0인 차항을 포함하여, 모든 차항의 계수값들을 배열 coef에 저장한다. - 단점: 계수가 0인 희소 다항식의 경우엔 공간의 낭비가 심하다. - 장점: 덧셈이나 뺄셈 연산 시, 같은 차수의 계수를 쉽게 찾을 수 있으므로 알고리즘은 간단하다. #include #define _CRT_SEC..

2주차 실습 과제 - 3번째 문제 문제 내가 작성한 코드 #include #include #pragma warning(disable : 4996) int main(void) { FILE* fp; // 파일 포인터 int i, j; // 반복문의 제어 변수 int data[12][20]; // 12개월-20년(충분한 열 공간을 미리 확보)의 데이터를 저장하는 2차원 배열 int yCount = 0; // year Count- 연도를 2000년부터 시작하여 연도가 증가할 때마다 변수 값 증가시킬 변수 int yearSum = 0; // 각 연도의 데이터들의 총합 double yearAvg = 0.0; // 각 연도의 데이터들의 평균 double monthAvg[12] = { 0.0, }; // 월별 평균 i..