728x90 개발새발/자료구조4 [자료구조] 스택(Stack) / 큐(Queue) 스택(Stack), 큐(Queue) 등은 자료구조에서 선형 구조라 한다. 선형 구조란 자료를 구성하고 있는 데이터들이 순차적으로 나열시킨 형태를 의미한다. ■ 스택 (Stack) 스택이란 쌓아 올린다는 것을 의미한다. 따라서 탑처럼 차곡차곡 쌓아 올린 형태의 자료구조를 말한다. 예를 들어 원형 통 과자에 마지막에 담긴 과자가 제일 먼저 꺼내지는 것처럼 스택 구조는 입구와 출구가 같아 마지막에 들어온 것이 가장 먼저 나간다 하여 후입선출(LIFO, Last-In-First-Out)법 이라고 한다. ※ 스택의 특징 스택의 입력과 출력은 맨 위에서만 일어나기 때문에, 스택의 중간에서는 데이터를 삽입하거나 삭제할 수 없다. 스택 구조의 맨 위를 가리키는 top 이라는 변수가 존재하며, 입력과 출력이 이루어지는 .. 2021. 4. 20. [자료구조] 힙(Heap) ■ Heap 힙(heap)은 완전 이진 트리(Completable Binary Tree) 를 기본으로 한 자료구조 (tree-based structure) 시간복잡도 : O(logn) 완전 이진 트리의 일종으로 우선순위 큐를 위하여 만들어진 자료구조이다. 여러 개의 값들 중에서 최댓값이나 최솟값을 빠르게 찾아내도록 만들어진 자료구조이다. 힙은 일종의 반정렬 상태(느슨한 정렬 상태)를 유지한다. 큰 값이 상위 레벨에 있고 작은 값이 하위 레벨에 있다는 정도 간단히 말하면 부모 노드의 키 값이 자식 노드의 키 값보다 항상 큰(작은) 이진 트리를 말한다. 힙 트리에서는 중복된 값을 허용한다. (이진 탐색 트리에서는 중복된 값을 허용하지 않는다.) ※ 힙의 특징 일반적으로 배열을 사용하여 구현한다.배열에 트리의.. 2021. 4. 20. [자료구조] 트리(Tree) ■ 트리 (Tree) 트리는 일반적으로 대상 정보의 각 항목들을 계층적으로 연관되도록 구조화시키고자 할 때 사용하는 비선형 자료구조이다. 데이터 요소들의 단순한 나열이 아닌 부모-자식 관계의 계층적 구조로 표현이 된다. 트리는 그래프의 한 종류이며 사이클이 없다. [Tree 구조] Node: 트리를 구성하고 있는 각 요소 Edge(간선): 트리를 구성하기 위해 노드와 노드를 연결하는 선 Root Node: 최상위 계층에 존재하는 노드 Level: 트리의 특정 깊이를 가지는 노드의 집합 Degree(차수): 하위 트리 개수 / 간선 수 (degree) = 각 노드가 지닌 가지의 수 Terminal Node ( = leaf Node, 단말 노드) : 하위에 다른 노드가 연결되어 있지 않은 노드 Interna.. 2021. 4. 20. [자료구조] 배열(Array) / 리스트(List) ■ 배열 (Array) 배열의 크기는 한 번 정하면 변경할 수 없다. 배열 초기화 시에 메모리에 할당되어 ArrayList보다 속도가 빠르다. 논리적 저장 순서와 물리적 저장 순서가 일치한다. 인덱스를 사용해 특정 원소에 접근이 가능하다. 즉, Random Access(비순차적 접급)가 가능하다. 인덱스를 알고 있다면 특정 원소에 접근하는 시간 복잡도는 O(1)이다. 생성할 때 데이터를 저장하는데 필요한 메모리를 한 번에 확보해서 사용한다. (연속된 메모리 사용) 배열의 크기를 바꿀 수 없다. 즉, 배열의 크기는 제한적이다. 배열의 원소를 삭제할 경우 삭제한 원소보다 큰 인덱스를 값을 갖는 원소들을 1씩 옮겨줘야 하기 때문에 시간 복잡도는 O(n)이다. 배열의 원소를 삽입할 경우 배열의 크기가 충분할 때.. 2021. 4. 20. 이전 1 다음 728x90 반응형
