전체 글

목차 1. 선택정렬 2. 거품정렬 3. 삽입정렬 4. 퀵 정렬 5. 병합 정렬 6. 힙 정렬 안정 정렬과 불안정 정렬 1. 안정 정렬: 동일한 값에 대해 기존의 순서가 유지되는 정렬 방식 ex) caBb -> aBbc (여기서 B==b 같은 값이다.) 2. 불안정 정렬: 동일한 값에 대해 기존의 순서가 유지되지 않는 정렬 방식 ex) caBb -> abBc (여기서 B==b 같은 값이다.) 선택정렬 - 불안정 정렬 1. 특징 가. 버블 정렬과 유사한 알고리즘이다 나. 해당 자리를 선택하고 그 자리에 오는 값을 찾는 알고리즘이다. 1) 주어진 배열 중에 최소값을 찾는다. 2) 그 값을 맨 앞에 위치한 값과 교체한다. 3) 맨 처음 위치를 뺀 나머지 배열을 같은 방법으로 교체한다. 다. 구현이 매우 간단하며..

힙(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..