본문 바로가기

분류 전체보기

 (312)
우선순위 큐 ∙ 우선순위 큐 (priority queue) - 각각의 데이터에 우선순위가 정의되어 있어서, 입력 순서에 상관없이 우선순위가 가장 높은 데이터가 먼저 출력되는 형태의 자료 구조 - 우선순위의 예 : 응급 자동차, 네트워크 트래픽 우선순위, 운영체제에서 프로그램 우선순위 - 일반 선출(FIFO) 큐 : 큐에 머무른 시간을 우선순위로 설정하면 일반 큐와 같이 동작 - C++에서 우선순위 큐 사용하기 > STL에서 제공하는 std::priority_queue 컨테이너 사용 ∙ std::priority_queue - 우선순위 큐의 기능을 제공하는 컨테이너 어댑터 - 삽입 순서에 상관없이 우선순위가 가장 높은 원소가 먼저 출력됨 - 사용자 정의 타입을 저장할 경우, 비교 연산을 지원해야 함 - 에 정의되어 있음..
힙 ∙ 힙 (heap) - heap 더미, 무더기, 퇴적물, (무엇인가를 차곡차곡) 쌓아 올린다. - 자료 구조에서 힙은 완전 이진트리의 한 형태로서 힙 속성을 만족하는 자료 구조. 이진 힙 (binary heap) - 힙 속성 (heap property) > 최대 힙 속성 (max heap property) : 부모 노드의 키 값은 항상 자식 노드의 키 값보다 크거나 같다. > 최소 힙 속성 (min heap property) : 부모 노드의 키 값은 항상 자식 노드의 키 값보다 작거나 같다. ∙ 힙의 특징 - 루트 노드는 항상 최댓값 또는 최솟값을 가짐 - 부모 - 자식 사이의 크기 관계만 있고, 왼쪽 자식 - 오른쪽 자식 사이의 크기 관계는 없음 - 완전 이진트리이기 때문에 트리의 높이는 h = [lo..
이진 탐색 트리 이진 탐색 트리 ∙ 이진 탐색 트리 (BST : binary search tree) - 효율적인 자료의 탐색을 위한 이진트리 기반의 자료구조 > 자료의 계층적인 구조를 표현하기 위해 트리를 사용하는 것이 아니라, 자료의 효율적인 관리를 위해 트리 구조를 사용 - 모든 노드 N에 대해 왼쪽 서브트리에 있는 모든 노드의 키(key) 값은 노드 N의 키 값보다 작고, 오른쪽 서브트리에 있는 모든 노드의 키 값은 노드 N의 키 값보다 크다 ∙ 이진 탐색 트리의 특징 - 자료의 탐색, 삽입, 삭제가 모두 O(log n) 시간 복잡도로 동작 - 이진 탐색 트리를 중위순회하면 오름차순으로 정렬된 값을 얻을 수 있음 ∙ 이진 탐색 트리에서 탐색 - 소스 코드 #include #include using namespace..
19 일차 트리과 이진 트리 ∙ 트리 (tree) - 계층적인 구조를 나타내는 자료 구조 - 보통 뿌리가 위에, 나뭇가지와 잎이 아래로 자라는 형태로 표현 ∙ 트리의 구성 요소 - 노드 (node, vertex) > 트리의 데이터를 저장하는 원소 단위 - 에지 (edge, link) > 노드와 노드를 연결하는 선 > 트리의 에지는 부모-자식 계층 관계만을 나타냄 > 노드의 개수가 N이면 항상 N - 1개의 에지가 존재 ∙ 이진트리 - 모든 노드가 최대 두 개의 자식을 갖는 트리 > 모든 노드의 차수가 2 이하인 트리 > 모든 노드가 2개의 서브트리를 가지고 있는 트리 (서브트리는 빈 트리(empty tree) 일 수 있음) - 각각의 자식 노드는 부모의 왼쪽 자식 또는 오른쪽 자신으로 지정됨 ∙ 정 이진트리 (pr..
18 일차 선형 탐색과 이진 탐색 ∙ 선형 탐색 (linear search) - 전체 자료를 처음부터 마지막까지 순서대로 탐색하는 방법. -> 순차 탐색 - 시간 복잡도 : O(n) - 선형 탐색의 장단점 > 장점 : 가장 간단하고 직관적인 방법이며, 정렬되지 않은 데이터에도 적용 가능 > 단점 : 비효율적(최악의 경우 배열 전체를 탐색해야 함) bool liner_search(int data[], int n, int target) { for (int i = 0; i < n; i++){ if (data[i] == target) return true; } return false; } ∙ 이진 탐색 - 정렬된 배열에 대해 검색 단계별로 검색 범위를 반으로 줄여가면서 데이터를 탐색하는 기법 - 시간 복잡도 : O(log..
17 일차 정렬과 탐색 (std::sort() 함수 사용) ∙std::sort() 함수 - 순차 컨테이너에 대해 (first, last) 범위의 원소들을 정해진 방법으로 정렬(기본값 : 오름차순) - 같은 값을 갖는 원소의 순서는 보장되지 않음(순서를 유지하려면 std::stable_sort() 함수 사용) - std::sort() 함수는 O(n log n)으로 동작해야 하며, 실제 구현은 컴파일러에 따라 다를 수 있음 - C 스타일 배열, vector, deque, array를 정렬할 때 주로 사용 (list, forward_list는 자체 멤버 함수 사용) - comp 인자에 비교 함수 객체를 전달할 수 있음 - 에 정의되어 있음 ∙ 소스 코드 (오름차순 정렬) #include #include int main(..
16 일차 정렬과 탐색 (분할 정복과 정렬 알고리즘) ∙ 분할 정복 (divide and conquer) - 주어진 문제의 규모가 커서 한 번에 해결하기 어려운 경우, 이를 작은 부분 문제로 나워서 해결하는 방식 - 분할(divide) : 주어진 문제를 동일한 방식으로 해결할 수 있는 부분 문제로 나누기 - 정복(conquer) : 각 부분 문제에 대한 솔루션 구하기 - 결합(combine) : 각 부분 문제의 솔루션을 결합하여 전체 문제에 대한 솔루션 구하기 ∙ 분할 정복을 이용한 정렬 알고리즘 - 병합 정렬(merge sort) > 분할 정복에 의한 정렬 알고리즘의 하나 > 입력 배열을 두 개의 부분 배열로 분할 > 각 부분 배열의 원소가 하나가 될 때까지 반복 > 부분 배열을 병합 > 이때 병합된 배열의 원소..
codeengn 보호되어 있는 글입니다.

티스토리툴바