leehyeon-dv 님의 블로그

📌소개 및 기초개념 디지털 서비스 예 : 메신저, 비디오 스트리밍, 온라인게임, 소셜 미디어 핵심 메세지 : 이런 서비스들은 모두 데이터통신을 기반으로 한다 어떻게 디지털 서비스가 제공될까? 서비스 제공구성: 사용자 장치와 서버 (서버에서 장치로 데이터를 전송) 예 : 메세지, 비디오, 이미지등이 서비스 데이터 어떻게 데이터가 전달될까? 발신자(Sender) → 수신자(receiver)까지 여러 중간 단계를 거침 (데이터도 네트워크를 통해 우편배송과 유사한 방식으로 전달됨) Data Communications 실제 데이터 통신모델 : 발신자 → data 네트워크 → 수신..

🔑Table of Contents시간복잡도 알고리즘분석RAMO, Ω , Θ 표기최대 부분 배열단순한 O(n³) 알고리즘 O(nlogn) 분할정복법 알고리즘 O(n) 동적 계획법 알고리즘중복 계산을 제거한 O(n²) 알고리즘정렬과 탐색삽입정렬선택정렬거품정렬퀵정렬이진탐색선형리스트 순차매핑연결리스트 헤드노드를 가진 연결리스트 환형 연결리스트 이중 연결리스트 스택과 큐스택큐환형 큐연결리스트를 큐로 구현 리스트의 응용배열이용희박행렬 배열이용희박행렬 연결리스트 이용스트링 표현연산식트리용어정리재귀적정의트리표현 - 링크이용트리의 이진 트리 표현괄호를 이용한 트리표현이진트리이진트리의 재귀적 정의이진트리의 성질이진트리 표현 - 링크이용이진트리 표현 - 배열이용이진트리 순회수식트리중순위 순회후순위 순회와 전순위 순회..

🔑Table of Contents스택이란?📌스택이란? 삽입과 삭제 연산을 한 쪽 끝에서만 일어나도록 제한한 리스트스택에서 삽입과 삭제 연산이 일어나는 끝을 top이라하고, 삽입 연산과 삭제 연산을 각각 push, pop이라고 한다 LIFO : 스택에서 나중에 삽입된 원소가 먼저 삭제되는 성질시스템에서 함수 호출이 발생할 경우, 가장 최근에 호출된 곳으로 복귀하기 위해 스택에 복귀 주소를 저장해 둔다 📌스택의 구현1 - 배열#define MAX_STACK_SIZE 1000 // 스택의 최대 크기 정의// 스택에 저장될 요소의 구조체 정의typedef struct { int key; // 저장할 데이터 (다른 필드도 확장 가능) /* other fields here ..

🔑Table of Contents선형리스트 란?  선형리스트의 연산배열 - 선형리스트 표현1 📌선형리스트 란?     선형 리스트(혹은 리스트)는 자료가 순서를 가지고 나열된 자료구조     리스트의 원소 = 리스트를 이루고 있는 각각의 자료      n개의 원소 a₀, a₁, ... , aₙ₋₁로 이루어진 리스트는          ( a₀, a₁, ... , aₙ₋₁ )로 표기한다 📌선형리스트의 연산     리스트에서 수행하는 대표적인 연산리스트 길이는?리스트의 모든 원소를 하나씩 읽어라k번째 원소는 무엇인가k번째 원소를 다른 원소로 교체해라k번째 위치에 새로운 원소를 삽입하라, 연산을 수행한 후에는 기존의 k번째 원소가 k+1번째 원소가 된다 k번째 원소를 삭제해라. 기존의 k+1번째 원소가 k..

🔑Table of Contents정렬 및 탐색 알고리즘정렬- 재귀적 접근1  정렬- 재귀적 접근2 퀵 정렬 퀵 정렬 분석 퀵 정렬에 덧붙여..정리📌 정렬 및 탐색 알고리즘정렬삽입 정렬 → O(n²)선택 정렬  → O(n²)거품 정렬  → O(n²)퀵 정렬     → O(n²) O(n logn)합병 정렬  → O(n logn)힙 정렬      → O(n logn)이진 탐색 트리를 이용한 정렬  → O(n logn)탐색이진 탐색 → O(logn)선형 탐색 → O(n)📌 정렬- 재귀적 접근1     [ 8 21 33 6 7 10 40 87 66 42 50 ]    삽입 정렬   6  7 8 10 21 33 40 42 66 87   • 앞에서 부터 수를 정렬에 맞게 삽입 / n개 n번탐색 O(n²)    ..

🔑Table of Contents문제정의 알고리즘알고리즘1 - 기본아이디어알고리즘1 - 시간 복잡도 분석알고리즘2 - 기본 아이디어알고리즘2 - 시간 복잡도 분석순환 알고리즘 완성하기알고리즘3 - 분할정복법시간 T(n) 구하기알고리즘4 - 기본 아이디어알고리즘4 - 동적계획법 → O(n) 📌문제정의 길이 n인 배열 A[0], A[1], ... , A[n-1]이 입력으로 주어질때, i번째부터 j번째 까지 원소들로 이루어진 배열 A[j], ..., A[j]를 부분 배열이라고 하고 A[i,j]로 나타냄 → A[0]도 존재함 • 문제는 최대 부분 배열, 즉 부분 배열에 속한 원소들의 합이 최대가 되는 부분 배열을 찾는 것이다 이때, 길이가 0인 부분 배열도 허용하며, 이 부분배열의 원소들의 합은 0이라고 정..

🔑Table of Contents알고리즘 분석RAM시간복잡도공간복잡도O(빅오),Ω(오메가),Θ(세타)O,Ω,Θ 표기 연습 시간 복잡도 분류📌알고리즘 분석 주어진 문제에 대한 알고리즘을 설계한 후 다음을 분석한다 - 정확성 : 가능한 입력에 대해서 항상 옳은 답을 출력하는가?- 자원 : 얼마나 많은 자원을 사용하는가? ※ 가장 중요한 자원 = 알고리즘 실행시간, 알고리즘을 실행하는데 필요한 메모리 양 📌 RAM (Random Access Machine)명령어가 순차적으로 수행되는 보통의 컴퓨터에 기반을 두고 있음 1. 간단한 명령어를 가짐(사칙연산, 비교, 치환)2. 정수를 고정된 길이로 표현 (예 : 32비트) → 덧셈이면 크기 상관없이 다 똑같은 시간이 걸림(정수 보통 4바이트)3. 무한한 양의..

1. 덧셈과 뺄셈을 수행하는 하드웨어로 AND와 OR 같은 논리 연산을 수행한다 더보기산술논리 연산장치(ALU)  2. 인터럽트라고 하는 컴퓨터도 많이 있다. 프로그램 수행을 방해하는 계획되지 않은 사건, 예를 들면 오버플로가 탐지에 사용된다.  더보기예외(exception)  3.  프로세서 외부에서 발생하는 예외(어떤 구조에서는 모든 예외를 인터럽트라고 부른다.) 더보기- 인터럽트(interrupt):  4. 소수점의 왼쪽에는 한 자릿수만이 나타나게 한 표기법. 더보기과학적 표기법  5. 선행하는 0이 없는 부동소수점 표기법  더보기정규화된 수  6. 양수값을 갖는 지수가 지수 부분에 표현될 수 없을 만큼 큰 상황 더보기오버플로  7. 음수값을 갖는 지수가 지수 부분에 표현될 수 없을 만큼 큰 상황...

🔑Table of ContentsExceptions and interrunpts ( 예외와 인터럽트)Handing Exception (MIPS에서의 예외처리)Exceptions in a Pipeline (파이프라인에서 예외처리)Pipeline with ExceptionsException Properties(예외의 특성)Exception 예제Exception ExampleMultiple ExceptionsImprecise Exceptions (부정확한 예외처리)📌 Exceptions and interrunpts ( 예외와 인터럽트)제어의 흐름 중에 예상치 못한 상황 발생했을때 이를 처리하기 위한 메커니즘, ISA에 따라 처리 방식다름Exception(예외 ) = CPU내부에서 발생하는 비정상적인 상황0..

🔑Table of ContentsBranch HazardsReducing Branch DelayData Hazards for BranchesDynamic Branch Prediction(동적 분기 예측)1-Bit Predictor : Shortcoming (결점, 단점) 2 -bit PredictorCalculation the Branch Target(address)📌 Branch Hazards브랜치 결과가 MEM단계에서 결정난다면?Control hazard에서 브랜치 결과를 알기 위해 기다리는 것이 아닌 아닌것으로 가정아니면 그대로, 맞으면 제대로 명령어를 가져와 수행하기로 함결과 맞으면 그동안 미리 예측해 수행한 명령어는 버려야함제어신호를 0으로 해 비워야📌 Reducing Branch Dela..