본문 바로가기

분류 전체보기112

[CH1] 컴퓨터 구조 1-1. 컴퓨터 구조의 큰 그림 / 데이터 : 컴퓨터가 이해하는 숫자,문자같은 정적정보 (명령어를 위한 재료) / 컴퓨터가 이해하는 정보 \ 명령어 : 데이터를 움직이고 컴퓨터 작동시키는 정보 컴퓨터 구조 \ 컴퓨터의 4가지 핵심 부품 : CPU, 메모리, 보조기억장치, 입출력장치 => 컴퓨터 : 명령어 처리하는 기계 (1) 메모리 : 현재 실행되는 프로그램의 명령어와 데이터를 저장하는 부품 => 프로그램이 실행되려면 반드시 메모리에 저장되어있어야함 => 이때 메모리 속 명령어와 데이터가 중구난방으로 저장되면 안되기에 주소를 이용 (2) CPU(컴퓨터의 두뇌) : 메모리에 저장된 명령어를 읽어들이고 그 명령어를 해석하고 실행하는 부품 1) ALU(산술연산장치= 계산기) : 컴퓨터 내부에서 수행되는 대부분.. 2023. 9. 20.
원형 연결 리스트 #define _CRT_SECURE_NO_WARNINGS #include #include #include #include typedef struct _listNode_ { int data; struct _listNode_* link; }listNode; typedef struct _linkedList_h_ { listNode* head; }linkedList_h; linkedList_h* createLinkedList_h() { linkedList_h* CL = (linkedList_h*)calloc(1, sizeof(linkedList_h)); assert(CL != NULL); return CL; } void orderedInsert(linkedList_h* CL, int item) { listNod.. 2023. 9. 20.
이진탐색(Binary Search) 1. 이진탐색 : 정렬되어 있는 리스트에서 탐색범위를 절반씩 좁혀가며 데이터를 탐색하는 방법 => 탐색 범위가 크다면 이진탐색 떠올리기! (1) 이진탐색의 기본 틀 start 일단 절단기의 높이를 최대한 높게 하는 것이 목표이기 때문에 start=0, end=떡의 길이를 저장한 리스트에서 최대값으로 설정 => 계속해서 start를 mid+1에 설정하며 절단기의 높이를 높여도 조건 충족하는지 확인한다 => 이때 요청한 떡의 길이 M보다 작아진다면 end = mid-1로 하여 왼쪽으로 절단기의 높이를 다시 늘린다 def Binary_Search(tteok, M, start, end): #탐색범위가 크다 ! => 이진 탐색 생각 while(startmid): sum+=(tteok[i]-mid) if(sum>=.. 2023. 9. 19.
큐 응용 : 미로문제(Maze problem) => BFS 이용 1. 원형 큐 : 배열의 처음과 끝이 연결되어있다고 가정 (1) 초기세팅 : front = rear = 0 => Enqueue : rear++하고 rear위치에 값 삽입 => Dequeue : front++하고 front위치에 있는 값 추출 => front 값 : 현재 front 위치에는 값이 존재하지 않는다 => rear 값 : 현재 rear 위치에는 마지막으로 Enqueue한 값이 삽입되어 있다 => 이 점을 고려하여 원형 공백상태 알 수 있음 1) 원형 큐 공백상태 : front = rear (삭제를 이미 수행한 데이터 위치와 마지막으로 삽입한 데이터의 위치가 동일) 2) 원형 큐 포화상태 : front = (rear+1) % n (n은 큐 사이즈) : 원형 큐는 하나의 공간은 항.. 2023. 9. 19.
스택 응용 : 미로문제(Maze problem) => 깊이우선탐색(DFS) 이용 #define _CRT_SECURE_NO_WARNINGS #include #include #include #define STACK_MAX_SIZE 100 #define MAZE_SIZE 6 //출발 위치:e, 벽:1, 이동 가능한 곳:0, 출구:x, 방문한 곳:. typedef struct _RAT_POS_ { char row; char col; }RAT_POS; int top = -1; void push(RAT_POS* st, RAT_POS item) { if (top == STACK_MAX_SIZE) { fprintf(stderr, "더이상 스택에 삽입할 수 없습니다\n"); return; } else { top++; st[top] = item; } } int IsEm.. 2023. 9. 15.
스택 응용(수식 계산) 1. 수식표기법 (1) 중위표기법(infix notation) : 연산자를 피연산자의 가운데 표기하는 방법 => 우리가 사용하는 방식 ex) A+B (2) 후위표기법(postfix notation) : 연산자를 피연산자 뒤에 표기하는 방법 => 컴퓨터 처리 방식 : 응용하여 중위표기법->후위표기법->수식 계산 : 스택 이용 ex) AB+ 1.1 괄호 검사 : 이때 수식을 계산하기 위해서는 올바른 수식인지 확인하기 위해 괄호 검사가 필요하다 : 수식에 포함된 괄호는 가장 마지막에 열린 괄호가 가장 먼저 닫아주어야 하는 구조를 스택을 통해 구현가능 : 수식검사가 완료된 경우, 공백 스택 상태여야함 왼쪽 괄호를 만나면 스택에 push 오른쪽 괄호를 만나면 스택에서 pop하여 같은 종류의 쌍의 괄호인지 확인 #.. 2023. 9. 15.

티스토리툴바