공부 정리

Priority Queue (우선순위 큐)? - 우선순위를 가지고 있는 큐 - 우선순위에 따라서 처리된다. (Not FIFO) - 우선순위 큐가 힙인 것이 아니라 우선순위 큐를 구현하는 것 중 대표적이고 효율적인 방법이 힙인 것 - 노드 하나의 추가/삭제가 시간 복잡도가 O(logN)이고 최대값/최소값을 O(1)에 구할 수 있다. - 완전 정렬보다 관리 비용이 적다. - 배열을 통해 트리 형태를 쉽게 구현할 수 있다. - 부모나 자식 노드를 O(1)연산으로 쉽게 찾을 수 있다. - n위치에 있는 노드의 자식은 2^n과 2^(n+1) 사이에 위치한다. - 완전 이진 트리의 특성에 의해 삽입/삭제의 위치는 자료의 시작과 끝 인덱스로 쉽게 판단할 수 있다. 힙 정렬 힙 정렬은 힙 자료구조를 이용해서 이진트리와..

Heap? 완전이진트리에 있는 노드 중에서 키 값이 가장 큰 노드나 키 값이 가장 작은 노드를 찾기 위해서 만든 자료구조 최대 힙(max heap) - 키 값이 가장 큰 노드를 찾기 위한 완전 이진 트리 - 부모 노드의 키 값 > 자식 노드의 키 값 - 루트 노드 : 키 값이 가장 큰 노드 최소 힙(min heap) - 키 값이 가장 작은 노드를 찾기 위한 완전 이진 트리 - 부모 노드의 키 값 < 자식 노드의 키 값 - 루트 노드 : 키 값이 가장 작은 노드 Heap에서의 삽입과 삭제 - 삽입 - 새 원소를 저장할 수 있도록 힙의 크기를 1만큼 늘린다. 힙 끝에 새 요소를 삽입한다. 새로 삽입된 원소를 힙의 성격에 맞게 재정렬한다. 최대 힙: 10 / \ 5 3 / \ 2 4 15를 새로 삽입하려고 한..

이진탐색트리 탐색작업을 효율적으로 하기 위한 자료구조. 모든 원소는 서로 다른 유일한 키를 갖는다. key(왼쪽 서브트리) 루트 노드의 키 값)인 경우 : 루트 노드의 오른쪽 서브트리에 대해서 탐색연산 수행 서브트리에 대해서 순환적으로 탐..

배열을 이용한 이진 트리의 표현 이진 트리에 각 노드 번호를 다음과 같이 부여 루트의 번호를 1로 함 레벨 n에 있는 노드에 대하여 왼쪽부터 오른쪽으로 2^n부터 2^(n+1) -1까지 번호를 차례대로 부여 배열을 이용한 이진 트리의 표현 노드 번호의 성질 노드 번호가 i인 노드의 부모 번호는 i / 2 노드 번호가 i인 노드의 왼쪽 자식 노드 번호는 2 * i 노드 번호가 i인 노드의 오른쪽 자식 노드 번호는 2 * i + 1 레벨 n의 노드 번호 시작 번호는 2^n 노드 번호를 배열의 인덱스로 사용, 레벨 i의 최대 노드 수는 2^i 높이가 h인 이진 트리를 위한 배열의 크기는 2^(h+1)+1 배열을 이용한 이진 트리 표현의 단점 편향이진트리의 경우에 사용하지 않는 배열 원소에 대한 메모리 공간 낭..

트리의 개념 비선형 구조 원소들 간에 1:n 관계를 가지는 자료구조 원소들 간에 계층관계를 가지는 계층형 자료구조 상위 원소에서 하위 원소로 내려가면서 확장되는 트리(나무)모양의 구조 노트(node) - 트리의 원소 ex) 트리 T의 노드 - 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 14 간선(edge) - 노드를 연결하는 선으로 부모 노드와 자식 노드를 연결 루트 노드(root node) - 트리의 시작 노드 ex) 트리 T의 루트 노드 - 1 형제 노드 (sibling node) - 같은 부모 노드의 자식 노드들 ex) 2, 3은 형제 노드 조상 노드 - 간선을 따라 루트 노드까지 이르는 경로에 있는 모든 노드들 ex) 8의 조상 노드: 4, 2, 1 서브 트리(subtr..

* List? 순서를 가진 데이터의 집합을 가리키는 추상자료형(abstract data type) 동일한 데이터를 가지고 있어도 상관 없다. (원소 중복 허용) 구현 방법에 따라서 1) 순차리스트ArrayList: 배열을 기반으로 구현된 리스트. 원소의 물리적 저장 순서와 원소의 논리적 순서가 같다. 2) 연결리스트Linked List: 메모리의 동적 할당(객체 생성)을 기반으로 구현된 리스트. 원소의 물리적 저장 순서와 원소의 논리적 순서는 다르다. 원소 하나하나를 객체로 만들어서 연결하는 자료구조 1. 순차 리스트(Array List) 구현 방법: 1차원 배열에 항목들을 순서대로 저장한다. 데이터의 종류와 구조에 따라 구조화된 자료 구조를 만들어 배열로 사용할 수도 있다. 데이터의 접근은 배열의 인덱..

선형 자료구조 1:1의 관계를 표현한다. 한 줄로 줄세울 수 있다. 비선형 자료구조 1:1 아닌 관계 1대다 다대다 ex) 계층적 트리, 그래프 트리는 넓은 의미에서 그래프의 특별한 형태다 Graph? 그래프는 아이템(사물 또는 추상적 개념)들과 이들 사이의 연결 관계를 표현한다. 정점(Vertex): 그래프의 구성 요소로 하나의 연결점 - 트리에서의 node 간선(Edge): 두 정점을 연결하는 선 차수(Degree): 정점에 연결된 간선의 수 그래프는 정점(Vertex)들의 집합과 이들을 연결하는 간선(Edge)들의 집합으로 구성된 자료 구조 * V: 정점의 개수, E: 그래프에 포함된 간선의 개수 * V개의 정점을 가지는 그래프는 최대 V*(V-1)/2 간선이 가능 => 무향그래프일 경우 예) 5개..

리스트란 순서를 가진 데이터의 집합을 가리키는 추상자료형이다.(abstract data type) 동일한 데이터를 가지고 있어도 상관 없고, 순서 또는 위치를 가진다. 구현 방법에 따라 크게 두 가지로 나뉜다. 1) 순차 리스트: 배열을 기반으로 구현된 리스트 1차원 배열에 항목들을 순서대로 저장한다. 데이터의 종류와 구조에 따라 구조화된 자료구조를 만들어 배열로 만들 수도 있다. 데이터 접근은 배열의 인덱스를 이용해 원하는 위치의 데이터에 접근할 수 있다. 단순 배열을 이요해 순차리스트를 구현하는 경우, 자료의 삽입/삭제 연산 과정에서 연속적인 메모리 배열을 위해 원소들을 하나씩 미는 작업이 필요하다. 따라서 원소의 개수가 많고 삽입/삭제 연산이 빈번하게 일어날수록 작업에 소요되는 시간이 크게 증가한다..

큐는 선형 자료구조로 먼저 들어온 데이터가 먼저 나가는 선입선출(FIFO: First In First Out)의 구조를 가지고 있다. 큐는 뒤에서 새로운 원소가 추가되고 앞에서 새로운 데이터가 하나씩 삭제되는 구조를 가지고 있다. 구조상으로 큐가 스택과 다른 점은 스택의 경우, 삽입과 삭제가 같은 쪽에서 일어나지만 큐에서는 삽입과 삭제가 다른 쪽에서 일어난다는 것이다. 큐의 연산 큐의 삽입 연산은 enqueue연산이라고 불리우며, 큐에 요소를 추가하는 연산으로서 큐의 맨 뒤에 원소를 추가한다. 이때 큐의 제일 뒤를 가리키는 용어를 rear이라고 한다. 큐의 삭제 연산은 dequeue연산이라고 불리우며, 큐에 요소를 삭제하는 연산으로서 큐의 제일 앞의 원소를 삭제한다. 이때 큐의 제일 앞을 가리키는 용어를..

스택이란 물건을 쌓아 올리듯 자료를 쌓아올린 형태의 자료구조이다. 선형 자료구조(자료 간의 관계가 1대 1인 관계)를 가지며 후입선출(LIFO: Last In First Out) 의 특성을 가진다. 즉 제일 나중에 들어온 데이터가 제일 먼저 나가게 된다. 스택에서 입출력이 이루어지는 부분을 스택 상단(top)이라고 하고 아랫 부분을 스택 하단(bottom)이라고 한다. 자료가 하나도 들어있지 않은 스택을 공백 스택(empty stack)이라고 하며, 스택에 저장되는 데이터를 요소(element)라고 부른다. 스택은 자료의 출력 순서가 입력 순서의 역순으로 이루어져야 할 경우 매우 요긴하다. 시스템 스택을 이용한 함수 호출 함수는 실행이 끝나면 자신을 호출한 함수로 돌아가야 한다. 이 때, 스택은 복귀할 ..