목록CS/자료구조 알고리즘 (20)
bdfgdfg
탐색 의미는 '데이터를 찾는 방법' 여기서 얘기할 탐색은 선형 탐색, 이진 탐색 등이 아닌 이진 트리에 관련된 탐색이다. 효율적인 탐색을 위해서는 어떻게 찾을까만을 고민해서는 안되고, 그보다는 효율적인 탐색을 위한 저장방법이 무엇일까를 우선 고민해야한다.(자료구조) 이진 탐색 트리 이진트리의 구조를 보면 최대 자식 노드를 2개까지 가질 수 있는 구조로, 1024개의 데이터를 저장한다 할지라도, 트리의 높이는 10을 넘지 않고 레벨을 내려가면서 값의 비교를 통해 비교 연산을 레벨당 한 번씩 하면 될 테니깐. 물론 값의 비교를 위해 이진트리의 저장 규칙이 있어야 한다. 그것이 지금 배울 이진 탐색 트리. 이진 탐색 트리에는 데이터를 저장하는 규칙이 있다. 그리고 그 규칙은 특정 데이터의 위치를 찾는 데 사용..
본문은 오름차순을 기준으로 정렬을 설명합니다. 힙 정렬 힙 정렬은 앞서 구현한 자료구조인 '힙(heap)' 자료구조를 이용한 정렬 알고리즘이다. 정렬은 특성은 힙의 다음 특성을 활용하여 정렬하는 알고리즘이다. "힙의 루트 노드에 저장된 값이 가장 커야 한다." - 최대 힙의 특징. 즉 이 특성을 이용해 힙의 루트 노드에 저장된 값이 정렬순서상 가장 앞선다. 앞서 힙을 제대로 공부했다면 바로 이해가 가능하니 코드를 통해 확인해본다. template void Sort::HeapSort(T* ptr, int len) { Heap hp(Sort::PriComp); int i; for (i = 0; i < len; ++i) hp.Insert(ptr[i]); for (i = 0; i < len; ++i) ptr[i..
기본적으로 오름차순으로 정렬합니다. 버블 정렬 모든 정렬 알고리즘중 매우 간단하고 이해하기 쉬운 정렬 알고리즘이다. 이해와 구현이 쉬운 만큼 성능에는 아쉬움이 존재한다. 매번 옆의 요소와 비교를 하며 오름차순으로 정렬하고 있다. 한번의 정렬과정에서 3241을 2314라는 정렬결과를 보여준 것.(정렬이 끝난것은 아님) 그림을 보면 알겠지만 한번 정렬이 완성된 상태에서 제일 큰 요소가 제일 뒤에 위치한다는것을 알 수 있다. 이렇듯 한번의 정렬에서 요소중 가장 큰 값을 뒤로 보낸다는 특징이 존재한다. 간단하니 바로 코드를 통해 확인한다. template class Sort { public: static void BubbleSort(T* ptr, int len); }; template void Sort::Bub..
우선순위 큐 간단하게 말해서 "들어간 순서에 상관없이 우선순위가 높은 데이터가 먼저 나온다" 이 우선순위의 판단 근거는 프로그래머가 결정할 일이다. 즉 목적에 맞게 우선순위를 결정하면 된다. 따로 우선순위정보를 넣어줄 수 있고, 저장할 데이터를 근거로 우선순위를 판단할 수 있다.(ex 사전순서) 우선순위 큐를 구현하는 방법은 여러가지가 될 수 있지만 순수 배열을 통한 구현을 할 시 데이터를 삽입 및 삭제하는 과정에서 데이터를 한 칸씩 뒤로 밀거나 한 칸씩 앞으로 당기는 연산을 수반해야한다. 그리고 삽입의 위치를 찾기 위해서 배열에 저장된 모든 데이터와 우선순위의 비교를 진행해야할 수 있다. -> 이 문제점은 연결리스트도 마찬가지. 그렇기에 우선순위 큐를 구현한다고 하면 '힙(heap)'이라는 자료구조를 ..