kwan's note

수강일시 :12월 29일 출처: kmooc 컴퓨터구조 3주차: CPU의 기본구조 및 구성요소에 대해 설명할 수 있다. 명령어 세트의 설계개념을 설명할 수 있다.명령어 및 데이터가 존재하는 메모리의 위치를 찾는 명령어 주소지정 방식을 설명할 수 있다. CPU의 기본 구조 및 구성요소 1.산술논리연산장치(ALU) 산술 및 논리데이터에 대한 연산을 위한 하드웨어 모듈 2.레지스터 세트 엑세스 속도가 빠르지만 제한적이다. 특수기능과 범용으로 나뉜다 특수기능(SPR)레지스터 PC: 다음에 인출할 명령어 주소값을 가지고 있는 레지스터로 명령어가 인출된 후 자동적으로 일정크기만큼 증가한다. 분기나 조건 명령어가 실행되면 해당 주소값으로 갱신된다. AC:메모리에서 데이터를 가져 왔을 때 저장 위치 순서를 결정하는 내용..

수강일시 :12월 28일 출처: kmooc 컴퓨터구조 3주차: ALU정수형 상수의 곱셍방식을 이해하고 부동소수점 수의 표현 방법을 설명할 수 있다. 부동소수점 연산 방법에 대해 설명할 수 있다. unsigned integer 곱 왼쪽은 사람이 계산하는 방식이고 오른쪽이 컴퓨터가 연산을 진행하는 방식이다. 피승수에 승수를 곱학게 되는데 승수Q의 첫번째자리와 피승수 1011을 곱하여 A reg에 넣는다. AQreg를 logical shift right한다. 이러한 방식으로 마지막 비트까지 진행하면 첫째자리는 계속 logical shift right 하므로 본인의 실제 필요만큼 내려간다. 이를 하드웨어 관점에서 보면 다음과 같다. 레지스터를 보도록 하자. 교수님의 설명을 그대로 적었다. "A Register는..

수강기간: 2020.09-2020.12 출처: 고려대학교 정연돈교수님 자료구조 수업 힙은 binary 트리이지만 bst와는 다르게 노드의 크기를 기준으로 좌우로 크기를 나눈것이 아닌 매 루트의 크기가 전체 트리에서 가장 작거나 가장 큰 tree를 말한다. 그림으로 차이를 보면 다음과 같다. MIN heap은 루트가 가장 작은경우 MAX heap은 루트가 가장 큰 경우를 말한다. 힙의 장점은 가장 크거나 작은 값을 바로 찾을 수 있다. 힙은 array를 통해서도 비교적 효과적으로 구성할 수 있다. complete tree이므로 2n+1이 왼쪽자식 2n+2가 오른쪽 자식 노드가 된다. 힙의경우 insert, delete의 과정에서 다시 힙으로 만드는 reheap의 과정이 필요하다. 힙에 insert하는경우의..

수강일시 : 2020.09~ 2020.12 출처: 고려대학교 정연돈 교수님 자료구조 강의 6주차 tree 7주차 binary search tree 8주차 avl tree 트리는 말그대로 나무 형태의 자료구조이다. tree는 node와 노드를 잇는 branches로 구성되어있다. 각 노드들은 부모/자식으로 표현하고 같은세대는 level로 표현한다. 예를들어 root node는 level 0, BEF노드들은 level1 CDGHI노드들은 level2 라고 한다. 각 노드들은 그 자체로도 서브트리를 구성한다. 트리중에서 각 노드의 자식이 2개 이하인 트리를 binary tree(이진트리)라고 한다. 이진트리의 특성은 다음과 같다. 이진트리중에서 모든 노드의 자식이 2개로 이루어진 경우 FULL binary t..

수강일시 : 2020.09~ 2020.12 출처: 고려대학교 정연돈 교수님 자료구조 강의 stack이란 아래서부터 쌓고 마지막으로 쌓은것부터 꺼내는 방식의 자료구조. Stack 의 ADT 작동예시 push(green) push(blue) Pop() push(red) array 를 이용하여 stack 을 구현한다면 초기에 stack의 최대 갯수를 stacksize로 정의하고 int stack[stacksize]; 로 선언한다. int top=-1;으로 초기화하고 void push(int arr[],int data,int top) { arr[++top]=data; } int pop(int arr[]) { return arr[top--]; } 등과 같은 방법으로 구현한다. 하지만 여기서 단점은 stack의 s..

수강일시 : 2020.09~ 2020.12 출처: 고려대학교 정연돈 교수님 자료구조 강의 재귀함수 (recursion)이란 자기 자신을 호출하는 함수이다. 새로운 재귀함수를 만들었을 때, 그 함수가 실행 과정에서 자기 자신을 다시 불러서 동일한 함수가 실행되도록 만든 것을 말한다. Factorial을 재귀함수를 이용하여 구현했을때 호출을 보면 다음과 같이 작동한다. 자기자신을 부른 시점에서 자신의 복사본이 실행되는것으로 볼 수 있다. 재귀함수에서 중요한것은 위에서 언급한 바와 같이 자신의 복사본이 실행되기 때문에 stack영역에 함수가 쌓이게 된다. 재귀함수가 호출될 때 마다 stack 영역에 쌓이기 때문에 호출이 계속된다면 stack이 꽉차게되고 stack overflow가 발생 할 수 있다. 따라서 ..

수강일시 : 2020.09~ 2020.12 출처: 고려대학교 정연돈 교수님 자료구조 강의 알고리즘이란 특정 또는 일반적인 문제를 해결하기 위한 방법도(혹은 순서도) input의 갯수는 상관없지만 output이 존재해야함. 결과는 명확하고 효과적이어야 한다. 알고리즘을 설명하는 방법으로는 1.자연어 2.pseudocode 3.flow chart 4.programming language 가 있다. pseudo code는 자연어와 프로그래밍 언어의 중간 성격으로 작성하기 쉽고 컴퓨터 언어를 사용하는 사람이라면 그 언어가 무엇이든간에 쉽게 알아볼 수 있도록 작성해야 한다. pseudo code를 읽으면 컴퓨터 언어로 쉽게 작성할 수 있지만 이를 컴퓨터가 직접 해석할 수 있도록 작성할 필요는 없다. ADT란 sp..

이 복습노트는 고려대학교 정연돈 교수님의 자료구조 강의를 기반으로 작성하였습니다. 수강기간:2020.09~2020.12 강좌설명은 아래와 같습니다