뭘 배웠지?

엘리스 코딩 자료구조에서 배운 내용 stack(스택) class Stack: ''' 이전 실습에서 작성한 Stack 클래스 코드를 사용합니다. ''' def __init__(self) : ''' 자료를 저장할 공간(리스트) myStack을 만듭니다. ''' self.myStack = [] def push(self, n) : ''' stack에 정수 n을 넣습니다. ''' self.myStack.append(n) def pop(self) : ''' stack에서 가장 위에 있는 정수를 제거합니다. 만약 stack에 아무 원소가 없다면 아무 일도 하지 않습니다. ''' if self.empty() == 1: return self.myStack.pop() def size(self) : ''' stack에 들어..

시간 복잡도 문제 해결에 걸리는 시간 최악의 경우에 대한 소요 시간 Big-O Notation O 최악 조건의 시간 복잡도 자료구조 공부 이유 작성하고자 하는 프로그램 목적을 가장 효율적으로 달성하는 자료구조를 사용하기 위해 => 각 자료구조의 특성과 동작방법을 알고 있어야된다

엘리스 코딩 자료구조에서 배운 내용 자료구조는 왜 배울까 프로그램에 필요한 자료를 효율적으로 담기위해 여우와 두루미가 있으면 여우는 접시, 두루미는 호리병이 편한 것처럼 적절한 것을 선택해야 된다 프로그램에서 특정 알고리즘 구현하기 위해 적절한 자료구조 사용해야 좋은 성능이 나온다 추상적 자료형 자료들과, 연산들을 개념적으로 정의 자료구조 자료 저장 방법과 자료에 적용할 수 있는 연산을 구체적으로 제공 추상적 자료형 => 자료구조 추상적 자료형을 구체적으로 구현한 것이 자료구조

자료구조 12화를 듣고 배운내용 KEYWORDS m원 탐색 트리: 트리의 노드가 m개 이하의 가지를 가질 수 있는 탐색 트리 B 트리: 인덱스 구조를 구현하는데 가장 일반적으로 사용하는 차수가 m인 트리 B*: 노드의 약 2/3이상이 차야하는 B트리 B+: 모든 키 값이 잎 노드에 있고, 그 키 값에 대응하는 실제 데이터에 대한 주소를 잎 노드만 가지고 있는 트리 인덱스된 순차 파일을 구성하는데 사용되는 트리 이진 탐색 트리의 단점? 노드의 개수가 많아지면 트리의 높이가 커진다. m원 탐색 트리로 만들면 높이가 낮아진다. m원 탐색 트리 m개 이하의 자식을 가질 수 있는 트리 높이를 줄이기 위해 집중한 트리 이진 탐색 트리보다 높이가 낮다 B 트리 m원 탐색 트리에서 균형을 잡은 트리 인덱스 구조 구현하..

자료구조 11화를 듣고 배운내용 KEYWORDS 이진 탐색 트리(Binary Search Tree): 빠르게 탐색할 수 있는 이진트리 Splay 트리: 자주 탐색하는 키를 가진 노드를 루트 가깝게 위치하게 구성한 이진 탐색 트리 AVL 트리: 노드의 왼쪽 서브트리 높이와 오른쪽 서브트리 높이가 최대 1만큼 차이 나는 조건을 만족하는 트리 트리의 높이: 노드가 가질 수 있는 가장 높은 레벨에 1을 더한 값, 루트에서 잎까지 가장 긴 경로 길이 트리의 무게: 트리에 속한 잎 노드의 개수 무게가 균형 잡힌 트리: 각 노드의 양쪽 서브트리 무게가 균형을 유지하는 트리 이진 탐색 트리(BS Tree) 탐색에 최적화된 이진 트리 노드를 삽입, 삭제하는 문제가 가장 효과적인 이진 트리 노드 삽입 루트부터 키 값은 비..

자료구조 10화를 듣고 배운내용 KEYWORDS 합병 정렬(=병합 정렬 =Merge Sort): 정렬된 k개의 데이터 리스트를 하나의 리스트로 만드는 과정 선택 트리: 합병 정렬에 사용되는 특수한 트리 승자 트리: 자식노드보다 더 작은 값(승자)을 갖는 완전 이진트리 패자 트리: 자식노드보다 더 큰 값(패자)을 가지며, 최종 승자는 0번 노드에 저장 숲: 분리된 트리 모임, 0이상 n개 이상의 분리된 트리의 집합 선택 트리 일반적으로 k개일 때 k-1번 비교를 한다. 선택 트리를 이용해서 비교 횟수를 줄일 수 있다. 승자 트리 첫 번째 단계는 비교 횟수가 같지만, 두 번째 단계부터는 비교 횟수가 줄어든다. 작은 값이 승자가 되어 올라가는 토너먼트 경기 루트값이 트리에서 가장 작은 값이 된다. 패자 트리 ..

자료구조 9화를 듣고 배운내용 KEYWORDS 힢(Heap): 부모노드와 자식노드가 대소관계로 구성되는 완전 이진트리. 우선순위 큐와 같은 결과 최대힢: 루트가 가장 큰 값을 갖고, 부모노드가 자식노드보다 큰 값을 가지면 된다. 최소힢: 루트가 가장 작은 값을 갖고, 부모노드가 자식노드보다 작은 값을 가지면 된다. 큐 먼저 들어간 데이터가 먼저 삭제되는 자료구조 먼저 줄을 선 사람이 먼저 서비스를 받는 구조 우선순위 큐 대기 리스트에서 우선순위가 높은 사람이 먼저 서비스를 받는 구조 삭제시 저장된 데이터 중에서 우선순위가 높은 데이터를 삭제한다. 나머지 데이터는 어떻게 저장되던 상관없다. Heap 우선순위 큐를 구현할 때 힢이 제일 효과가 좋다고 한다. 피라미드 모양으로 쌓은 더미 쌓아놓은 더미에서 항상..

자료구조 8화를 듣고 배운내용 KEYWORDS 스레드(thread): 정해진 순회 방법에 따른 방문순서를 유지하는 포인터 스레드 트리: 스레드라는 포인터를 갖는 이진 트리 오른쪽 스레드: 정해진 순회 순서에 따른 그 노드의 후속 노드를 가리킴 왼쪽 스레드: 정해진 순회 순서에 따른 그 노드의 선행 노드를 가리킴 이진 트리의 null 포인터 개수: 2(n - (n - 1) = n + 1 스레드 트리 이진 트리의 null 포인터를 활용하기 위한 스레드 트리 자식 노드가 없는 노드의 포인터는 null을 갖는다 스레드라는 포인터를 추가해서 순회를 편리하게 했다. 스레드를 사용하면 노드를 빨리 찾아다닐 수 있다. 구현이 복잡하고, 추가 기억장소를 사용하는 부담이 있다. 스레드 트리의 구현 1 포인터 필드 추가 왼..

자료구조 7화를 듣고 배운내용 KEYWORDS 트리: 논리적 계층이 있는 구조, 트리를 구성하는 항목을 노드 혹은 점(vertex)라고 한다. 루트 노드: 최상위 노드, 부모가 없는 노드(진입 차수 = 0) 서브 트리: 부모 노드를 삭제하면 생기는 트리들 리프 노드: 최하위 노드, 서브 트리를 갖지 않는 노드(진출 차수 = 0) 진입 차수: 트리의 어떤 노드에 들어오는 선의 개수 진출 차수: 트리의 어떤 노드에 나가는 선의 개수 내부 노드: 루트도 잎도 아닌 노드 형제(sibling): 같은 부모를 갖는 노드 포화 이진 트리: 이진 트리에서 각 레벨에 최대 개수(노드당 2개씩) 노드를 가지는 트리 완전 이진 트리: 높이 k 이진트리에서 k-2까지 다 채우고, 마지막 k-1 레벨에서 왼쪽부터 오른쪽으로 노..

자료구조 6화를 듣고 배운내용 KEYWORDS 단순 연결 리스트: 링크 부분이 하나, 각 노드는 후행 노드만 가리킨다. 후행 노드는 쉽게 접근 가능, 선행 노드는 접근하기 복잡하다 이중 연결 리스트: 선행 노드와 후행 노드에 접근할 수 있는 구조 원형 연결 리스트: null 값을 갖는 마지막 노드의 링크 부분을 활용해서 프로그램 성능 주기위해 제안 모든 노드가 원형으로 연결되어 있기 때문에 한 노드에서 어떤 노드로든 접근 가능 원형 이중 연결 리스트 head에도 Llink와 Rlink를 주고 Rlink는 제일 뒤의 노드에 연결 => 앞에서부터 찾아갈 수도 있고, 맨 뒤 노드에서부터 왼쪽으로 찾아올 수 있다.