![]()
힙(Heap) 특징 1. 완전 이진 트리의 일종으로 우선순위 큐를 위해 만들어진 자료구조이다. 2. 여러개의 값들 중에서 최대값이나 최소값을 빠르게 찾아내도록 만들어진 자료구조이다. 3. 힙은 반 정렬 상태를 유지한다. 4. 힙 트리는 중복 값을 허용한다. 우선순위 큐 1. 데이터들이 우선순위를 가지고 있어 우선순위가 높은 데이터가 먼저 나가는 구조 2. CPU 작업 스케쥴링, 시뮬레이션 시스템에서 사용 3. 우선순위 큐는 배열, 연결리스트, 힙으로 구현이 가능한데, 힙으로 구현하는게 가장 효율적. 힙 종류 1. 최대 힙: 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진트리 2. 최소 힙: 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진트리 힙 구현 특징 1. 힙을..
![]()
그래프: 하나 이상의 정점(혹은 노드)을 포함하는 집합 정점(v)와 두 정점의 쌍으로 구성되는 간선을 포함하는 집합 E를 가진다. 정점간의 관계를 표현하는 자료구조이다. 등장 배경 - 수학자 오일러가 쾨니히스베르크 다리 문제를 해결하기 위해 그래프를 고안 * 쾨니히스베르크 다리 문제: 모든 다리를 단 한 번씩 지나 다시 출발점으로 되돌아 올 수 있는가? - 육지를 점으로 다리를 선으로 표현하여 문제를 추상화함 - 육지의 건물이나 다리 같은 불필요한 요소는 다 버리고 육지와 다리의 '관계'만을 점과 선으로 나타낸 것이 그래프의 시초 그래프 표기법 G = (V, E) 1. G: 그래프(Graph) 2. V: 노드 또는 정점(Vertex) 3. E: 간선(Edge) 그래프의 용어 1. 정점: 간선이 연결되는 ..
![]()
해시함수: 데이터의 정보를 보장하고 효율적으로 관리하기 위해, 임의의 길이 데이터를 고정된 길이의 데이터로 매핑하는 함수, 보통 key, value값이 있는 Set이나 Map을 이용하여 매핑을 하는데, 매핑 전 원래 데이터 값을 key로 매핑 후 데이터 값을 value, 매핑하는 과정 자체를 해싱이라 한다. 해시함수를 사용하는 목적 - 메시지의 오류나 변조를 탐지할 수 있는 무결성을 제공하기 위해서 사용된다. 해시함수를 이용해 해시값으로 바꾸는 과정 * 데이터를 문자열로 받게 되었을 때 문자 한글자의 아스키 코드 값을 더하는 과정을 통해 문자열을 정수 값으로 바꿔나는 과정을 예시를 통해 기록하겠습니다. 1. 'hello'라는 문자열이 데이터 값으로 들어옴 2. 'h=104,' 'e=101' , 'l=10..
![]()
Stack(스택) 1. LIFO(후입선출) - 가장 나중에 들어온 값이 가장 먼저 나오는 구조 2. 스택이 사용되는 곳 가. 함수의 콜 스택 나. 연산자 후위 표기법 다. 시스템 스택 라. 뒤로가기 버튼 3. 스택이 가지고 있는 함수 가. push(): 데이터를 넣는다. 나. pop(): 데이터를 꺼낸다. 다. isEmpty(): 스택이 비어있는지 확인한다. 라. isFull(): 스택이 꽉 차있는지 확인한다. 4. 스택포인터 가. push(), pop()을 할 때 해당 위치를 알고 있어야 하므로, 해당위치를 기억하고 있는 포인터 나. 스택 포인터의 초기화 값은 -1 Queue(큐) 1. FIFO(선입 선출) - 가장 먼저 들어온 값이 가장 먼저 나오는 구조 2. 큐가 사용되는 곳 가. 이벤트 큐 나. ..
