Data structure

힙 / 힙 정렬 [Heap / Heap Sort] 힙 (Heap) [n 더미] : 완전 이진 트리의 일종으로, 우선 순위 큐를 위하여 만들어진 자료 구조 여러 값 중에서 가장 큰 값이나 가장 작은 값을 빠르게 찾아 내도록 만들어진 자료 구조이다. ※ 힙 트리에서는 중복된 값을 허용 이러한 특징으로 힙 트리에서는 두 종류가 존재한다. 1. 최대 힙 (Max Heap) : key(부모노드) >= key(자식노드) (부모노드의 키 값이 자식노드의 키 값 보다 크거나 같음) 2. 최소 힙 (Min Heap) : key(부모노드)

[Shell , Merge , Quick Sort] 4. 쉘 정렬 (Shell Sort) : 요소간의 특정 간격 ‘k’에 해당하는 요소들을 하나의 부분 리스트로 하고 이를 삽입 정렬을 사용하여 정렬한다. ‘k’ 값을 1까지 줄여가며 이를 반복하여 정렬하는 방법 쉘 정렬은 ‘도날드 쉘’이 제안한 정렬로 삽입 정렬이 어느 정도 정렬된 배열에 대해서는 처리 속도가 빠르다는 것에 착안 하여 만들어 졌다. 기존 삽입 정렬의 문제점인 “요소들간의 교환(swap)이 이웃한 것끼리만 일어난다.” 라는 것을 개선하여 쉘 정렬은 요소들이 멀리 떨어진 위치로도 한번에 이동 가능 하다. 쉘 정렬은 특정 간격 ‘k’의 요소들을 가진 부분 리스트를 삽입 정렬하고 이 ‘k’ 값을 1까지 줄여가는 방법으로 정렬한다. 우리가 쉘 정렬..

[Bubble / Selection / Insertion Sort] sorting : n 구분 / 분류 정렬(Sorting)이란, 항목을 체계적으로 정리하는 과정이다. 알고리즘에서의 정렬은 요소들을 요소에 종류에 따라 오름차순/내림차순, 사전 순서대로 열거하는 알고리즘을 뜻한다. 1. 버블 정렬 (Bubble Sort) : 연속으로 맞닿아있는 데이터를 비교하고 즉시 교환 해나가는 배열 [배열의 2개의 아이템을 선택 -> 2개의 아이템을 비교 -> 왼쪽 > 오른쪽 이면 교환 -> 배열 끝날 때 까지 반복] => 하나의 사이클 이와 같은 사이클을 모든 데이터가 정렬 될 때 까지 반복한다. 배열 [40, 20, 50, 30, 10]을 버블 정렬을 사용하여 오름차순으로 정렬 하여 보았다. 인덱스 0과 1에 위치..

배열(Array)은 동일한 자료형의 여러 데이터를 하나의 이름으로 그룹핑을 하여 관리하기 위한 자료구조이다. 수학적으로 표현 한다면, “(index, value)로 이루어진 순서쌍들의 집합”으로 할 수 있다. 배열은 거의 모든 프로그래밍 언어에서 지원하는 자료형으로 많은 자료 구조들이 배열을 사용하여 구현된다. 배열은 데이터가 적을 때는 거의 사용하지 않는다. -> 각각의 변수를 선언해주면 됨 데이터가 많은 때 -> 모든 데이터가 각각 존재하게 되는 경우 데이터를 이용하기 어려워짐 -> 데이터를 그룹관리 해야 할 필요성이 생기게 됨 -> 배열 사용 배열 사용의 장점 배열을 사용하면 “연속적인 메모리 공간”이 할당되고 인덱스(index) 번호를 사용하여 쉽게 접근이 가능하기 때문에 반복루프를 이용하여 여러..