WinCNT

자료 구조를 쓰는 이유는 결국 탐색해서 다시 사용하기 위해서이다 데이터를 넣을 때 정렬되고, 정렬된 데이터를 가져오는 것이 바로 알고리즘이다 이번에는 대표적인 자료 구조인 트리(Tree)와 힙(Heap)에 대해서 정리해보자 힙(Heap)은 무엇인가를 차곡차곡 쌓아올린 더미란 의미기 때문에 CS에서 다양한 곳에서 사용된다 여기서는 자료 구조로서의 힙(Heap)에 대해서 정리한다 트리(Tree) 수학, 특히 그래프 이론에서 회로(Cycle)가 없는 연결된 무향의 그래프를 트리라고 한다(by 나무위키) 트리 구조는 비선형적이지만 현실 세계에 있는 익숙한 구조이다 트리는 탐색기, 책의 목차 등에 주로 사용된다 용어 정리 노드(Node) : 트리를 구성하는 기본 원소, 값과 다음 노드에 대한 정보를 가짐 루트 노..

탐색 알고리즘 Linear Search 배열의 시작 부터 나올 때까지 탐색 정렬할 필요가 없음 Binary Search 정렬된 배열의 중간 부터 비교 검색 반경을 반으로 나누어 반복 Quick Search 퀵 정렬의 응용 버전 탐색이기 때문에 전체 정렬이 아니라 부분 정렬 정렬 알고리즘 캐시의 히트율을 높히기 위해 주로 배열을 사용하는 정렬 알고리즘에는 다음이 있다. 추가적으로 메모리 버퍼를 사용하지 않은 정렬 알고리즘(In_Place) Bubble Sort(버블 정렬) 두 인접한 원소를 검사하여 정렬하는 방법, 시간복잡도는 O(n^2) 비교, O(n^2) 교환 장점: 코드가 단순하여 자주 사용됨 단점: 상당히 느리다 Select Sort(선택 정렬) 처음부터 마지막까지 봐서 가장 작은 게 1번째, 2번..

Data Structure 데이터 집합 ⇒ 컨테이너 기능 ⇒ 삽입, 삭제, 조회 Array, List, Queue, Stack, Tree, Graph 데이터의 배치에 따라 선형적, 비선형적인 형태로 나눌 수 있다 선형적인 자료구조로는 배열과 리스트(더 나아가 스택과 큐)가 있음 비선형적인 자료구조의 대표적인 예로는 Tree와 Graph가 있음 Algorithm 문제 해결을 목적으로 하는 절차 공식 목적 ⇒ 탐색, 정렬, 최단 경로 순차 탐색, 이진 탐색, … 선택 정렬, 힙 정렬, … BFS, Dijkstra Algorithm 알고리즘의 조건 입력 : 0개 이상의 입력 값 ⇒ 입력 값은 없을 수 있다 출력 : 1개 이상의 출력, 입력에 따라 2가지 이상의 서로 다른 결과 ⇒ 입력에 따라 2가지 이상의 다..