kwan's note

수강기간: 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 강좌설명은 아래와 같습니다