개발새발

이진 트리의 순회(Traversal) - 모든 노드를 빠뜨리거나 중복하지 않고 방문하는 연산합니다. - 순회 종류는 4가지가 있습니다. - 전위 순회(Preorder Traversal) - 중위 순회(Inorder Traversal) - 후위 순회(Postorder Traversal) - 레벨 순회(Level Traversal) DFS(Depth-First Search) or Depth-First Traversal : 다음 하위 항목으로 이동하기 전에 하위 항목의 모든 하위 항목을 처리합니다. - 스택(Stack)이 사용됩니다. 전위 순회(Preorder Traversal) - 방문 순서 : 현재 노드 -> 왼쪽 노드 -> 오른쪽 노드 위 그림의 방문 순서 : A->B->C->D->E->F 중위 순회(I..

이진 트리(Binary Tree) : 어떠한 노드도 2개보다 많은 Subtree 가질수 없습니다. - 각 노드는 최대 2개의 자식을 가질 수 있습니다. - 자식 노드는 좌우를 구분합니다. - 왼쪽 자식 : 부모 노드의 왼쪽 아래입니다. - 오른쪽 자식 : 부모 노드의 오른쪽 아래입니다. Subtree : 하위 트리는 하위 트리로 나눌 수 있습니다. - 단일 노드도 하위 트리입니다. 이진 트리의 종류 포화 이진 트리(Perfect Binary Tree) : 모든 레벨에서 노드들이 꽉 채워져 있는 트리 완전 이진 트리(Complete Binary Tree) : 마지막 레벨을 제외하고 노드들이 모두 채워져 있는 트리 정 이진 트리(Full Binary Tree) : 모든 노드가 0개 또는 2개의 자식 노드를 ..

트리(Tree) : 트리는 Nodes와 Branches로 이루어져 있다. - 노드와 링크로 구성된 자료구조 (그래프의 일종, Cycle 없음) - 계층적 구조를 나타낼 때 사용 - 폴더 구조(디렉토리, 서브 디렉토리) - 조직도, 가계도, ... 트리의 구성 요소 - 노드(Node) : 트리 구조의 자료 값을 담고 있는 단위 - 에지(Edge) : 노드 간의 연결선 (=link, branch) - 루트 노드(Root) : 부모가 없는 노드, 가장 위의 노드 - 잎새 노드(Leaf) : 자식이 없는 노드 (=단말) - 내부 노드(Internal) : 잎새 노드를 제외한 모든 노드 - 부모(Parent) : 연결된 두 노드 중 상위의 노드 - 자식(Child) : 연결된 두 노드 중 하위의 노드 - 형제(S..

학습 목표 힙 자료구조의 이해 최소 힙과 최대 힙의 삽입, 삭제 과정의 이해와 구현 힙(Heap) : 최소 값 또는 최대 값을 빠르게 찾아내는데 유용한 자료구조입니다. 1. Tree가 Complete or Nearly Complete.(중복 값 허용, 반 정렬 상태) 2. 최대 힙(Max Heap) : 부모 노드의 키 값이 자식의 키 값보다 크거나 같습니다. 최소 힙(Min Heap) : 부모 노드의 키 값이 자식의 키 값보다 작거나 같습니다. 최소 힙(Min Heap) - 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 형태입니다. Operation of Min Heap 최소 힙 - 삽입(Insertion) 1. 트리의 가장 끝 위치에 데이터 삽입합니다. 2. 부모 노드와 키 값을 비교한 후 ..

연결 리스트(Linked List) : 데이터 요소들이 노드(Node)들에 의해 연결된 자료 구조입니다. - 데이터를 링크로 연결해서 관리하는 자료구조입니다. - 자료의 순서는 정해져 있지만, 메모리상 연속성이 보장되지는 않습니다. 연결 리스트(Linked List) 기본 구조 노드(Node) : 데이터 저장 단위로, 값(Data)과 포인터(Link)로 구성되어있습니다. 포인터(Pointer) or Next or Link : 다음 노드나 이전 노드의 연결 정보 연결 리스트(Linked List)의 장점 - 데이터 공간을 미리 할당할 필요가 없습니다. - 즉, 리스트의 길이가 가변적이라 데이터 추가/삭제가 용이합니다. 연결 리스트(Linked List)의 단점 - 연결구조를 위한 별도 데이터 공간이 필요합..

해시 테이블(Hash Table) : 키(Key), 값(Value)을 대응시켜 저장하는 데이터 구조 - 키를 통해 해당 데이터에 빠르게 접근 가능합니다. 해싱(Hashing) : 키를 특정 계산식에 넣어 나온 결과를 사용하여 값에 접근하는 과정입니다. 키(key) : 해시 테이블 접근을 위한 입력 값입니다. 해시 함수(Hash Function) : 키를 해시 값으로 매핑하는 연산합니다. 해시 값(Hash Value) : 해시 테이블의 인덱스입니다. 해시 테이블(Hash Table) : 키-값(key-value)을 연관 시켜 저장하는 데이터 구조입니다. 해시 충돌 : 해시 함수를 통해 index값을 구했을 때 중복이 생기는 충돌입니다. - 해시 테이블의 같은 공간에 서로 다른 값을 저장하려는 경우입니다. ..

배열(Array) : 각각의 개별 항목을 위치 번호로 참조할 수 있도록 항목을 번호순으로 배열하는 데이터 구조입니다. - 많은 수의 데이터를 다룰 때 사용하는 자료구조입니다. - 각 데이터를 인덱스와 1:1 대응하도록 구성됩니다. - 데이터가 메모리 상에 연속적으로 저장됩니다. 데이터구조(Data Structure) : 하나의 단위로 취급될 수 있도록 여러 개의 데이터 항목을 뭉쳐서(chunked) 구성됩니다. 길이(Length) : 배열에서 항목들의 수 입니다. 기본 자료형(Base Type) : 배열의 개별 항목 자료형입니다. 인덱스(Index) : 배열에서 항목의 위치 번호 입니다. 배열(Array)의 장점 - 인덱스를 이용하여 데이터에 빠르게 접근 가능합니다. * 더 나아가기(OS) 배열은 Spa..

큐(Queue) : Queue is like waiting line rear : Insertion 하는 곳 front : Deletion 하는 곳 FIFO(First-In First-Out) 먼저 들어온 데이터가 먼저 나가는 구조 ex) 입력 순서대로 데이터 처리가 필요한 경우 사용 : 프린터 출력 대기열, BFS(Breath-First Search), 식당 웨이팅 등 Queue의 구조 - Enqueue : Queue에 데이터 추가 - Dequeue : Queue에 데이터 제거 (Queue) Front : retrieve the element at the front (Queue) Rear : retrieve the element at the rear Queue Operation - Enqueue : Qu..

스택(Stack) : To put things in a pile. Top : 모든 추가 및 삭제는 위 그림처럼 한쪽(Top)에서만 가능합니다. (* Queue는 two ends에서 사용가능) LIFO(Last In First Out) - Data Series를 스택에 삽입한 후, 제거하려고 한다면 제거되는 순서는 삽입한 순서의 반대가 됩니다. ex) 데이터 입력 순서 : {5, 10, 15, 20} 데이터 제거 순서 : {20, 15, 10, 5} 스택의 기본 용어 - Bottom : 가장 밑에 있는 데이터 - Top : 가장 위에 있는 데이터 - Capacity : 스택에 담을 수 있는 데이터의 총 용량 - Size : 현재 스택에 담겨있는 데이터의 개수 Basic Stack Operations - P..