목록2025/06/20 (4)
컴퓨터공학 💻 도서관📚
힙(Heap) : 힙 조건을 만족하는 완전 이진 트리 (특수한 종류의 완전 이진 트리) 힙 조건 : 2가지 경우가 있다. (1) 부모 노드의 값 >= 자식 노드의 값 (최대 힙 , Max heap) (2) 부모 노드의 값 최소 힙 , Min heap) 각각의 부모 노드가 모두 이걸 충족해야 한다, 루트 노드 값이 최대or최소고 아래로 내려갈수록 작아지거나 커지는 구조 힙 트리 라고 부르지는 않는다자료구조에서 "힙"이라는 말 자체가 이미 트리 구조를 내포하고 있기 때문이다. 트리 --> 이진 트리 --> 완전 이진 트리 --> 포화 이진 트리
이진 트리 (binary tree) : 부모노드에 자식노드가 두 개 이하인 트리완전 이진 트리(Complete Binary Tree) : 노드가 왼쪽부터 채워지고, 마지막 레벨을 제외하고 모든 노드가 채워져 있는 이진 트리 완전 이진 트리는 2가지 조건을 충족해야 한다첫째, 마지막 레벨(level)을 제외하고 모든 노드가 채워져있어야 한다.마지막 레벨의 노드는 다 채워져 있을 수도 있고 아닐수도 있다.둘째, 노드는 왼쪽에서 오른쪽 방향으로 채워져야 한다. 그래서 어느 노드에 오른쪽 자식이 존재한다면 왼쪽 자식도 가지고 있어야 완전이진트리로 볼 수 있다. 포화 이진 트리 (표준 표현 : Perfect Binary Tree , 비표준 표현 : Fully Complete Binary Tree) 쉽게..
Array 의 특징 동일한 데이터 타입을 순서에 따라 관리하는 자료 구조정해진 크기가 있음요소의 추가와 제거시 다른 요소들의 이동이 필요함배열의 i 번째 요소를 찾는 인덱스 연산이 빠름jdk 클래스 : ArrayList, VectorArray 구현하기public class MyArray { int[] intArr; //int array int count; //개수 public int ARRAY_SIZE; public static final int ERROR_NUM = -999999999; public MyArray() { count = 0; ARRAY_SIZE = 10; intArr = new int[ARRAY_SIZE]; } public MyArray(int size) { co..
자료구조란 무엇인가?프로그램에서 사용할 많은 데이타를 메모리 상에서 관리하는 여러 구현방법들효율적인 자료구조가 성능 좋은 알고리즘의 기반이 됨자료의 효율적인 관리는 프로그램의 수행속도와 밀접한 관련이 있음여러 자료 구조 중에서 구현하려는 프로그램에 맞는 최적의 자료구조를 활용해야 하므로 자료구조에 대한 이해가 중요함 자료구조에는 어떤 것들이 있나? * 한 줄로 자료를 관리하기 (선형 자료구조 : 배열, 연결 리스트, 스택, 큐) * 선형 자료구조는 앞뒤의 요소가 1 대 1의 관계이다. (1 대 다 , 다 대 다 의 관계도 있다.) 배열 (Array) : 선형으로 자료를 관리, 정해진 크기의 메모리르 먼저 할당받아 사용하고, 자료의 물리적 위치와 논리적 위치가 같음 ..