프로그래밍79 [Data Structure] 힙(Heap) 구조 일반적인 힙이라는 단어는, 메모리 구조에서 동적할당 시 할당되는 공간을 의미한다. 하지만 자료구조 힙의 경우, 힙 순서 속성을 만족하는 트리를 의미한다. 이런 힙은 우선순위 큐를 구현하기 위해 만들어진 자료구조이다. 여기서 힙 속성이란 두 가지 조건을 충족해야 하는데 다음과 같다. 1. 힙 구조는 항상 완전 이진 트리여야 한다. 2. 모든 노드는 자신의 부모 노드보다 크다.(우선순위가 후순위다) 이 두 조건을 충족하는 트리 구조가 바로 힙 구조이다. 2번 조건을 만족하기만 하면 되기 때문에 힙 구조는 항상 반정렬 상태(느슨한 정렬 상태)를 유지한다. 또한 힙 구조는 이진 탐색 트리가 아니기 때문에 중복된 값을 허용한다. 우선순위 큐를 구현하기 위해 만들어진 만큼, 우선순위가 큰 것이 우선이면 최대 힙, .. 2023. 4. 30. [Data Structure] 우선순위 큐(Priority Queue) 일반적인 큐 자료구조는 뒤에서 자료를 추가하고, 앞에서 자료를 삭제한다. 우선순위 큐도, 이름이 큐인 만큼 기본적으로 이런 구조를 가진다. 단, 앞에 우선순위라는 말이 이 자료구조의 정체성을 나타낸다. 들어오는 자료구조에서 우선순위를 판별하여 우선순위가 높은 자료를 앞쪽에 배치한다. 따라서 우선순위 큐에서 항상 먼저 나오는 데이터는 우선순위가 가장 높은 자료이다. 구조 1. 데이터가 큐에 삽입이 되면 기본적으로 push_back되고, 삭제를 하면 pop_front가 된다. 이는 일반적인 큐와 동일하다. 2. 삽입되는 과정에서 각 자료들과 우선순위를 비교한다. 만약 먼저 삽입된 데이터들보다 우선순위가 높다면 그 데이터는 다른 데이터보다 앞쪽으로 배치가 된다. 3. 삽입을 enqueue, 삭제를 dequeu.. 2023. 4. 30. [Algorithm] DFS, BFS 트리 혹은 그래프를 탐색할 때, 두 가지 방법이 있다. 하나는 깊이 우선 탐색(DFS, Depth-First Search), 나머지 하나는 너비 우선 탐색(BFS, Breadth-First Search)이다. DFS 노드 혹은 그래프를 탐색할 때, 두 가지 이상 갈래 길(Branch)이 있을 경우, 한 길을 우선적으로 끝까지 탐색하여 탐색을 완료한 뒤, 다른 길을 탐색하는 알고리즘이다. 핵심은 한 길이다. 쉽게 설명하기 위해 트리로 나타낸 그림을 확인하면 다음과 같다. 그림으로 확인이 가능하듯이 탐색을 할 때 하나의 길을 우선적으로 탐색하고, 완료한 다음 다음 길을 탐색하는 알고리즘이다. 장점 단순하게 현 경로상의 노드만 기억하면 되기 때문에 저장공간의 수요가 비교적 적다. 목표 노드가 깊은 단계에 있을.. 2023. 4. 28. [Data Structure] BST(Binary Search Tree) 이진 트리는 한 노드의 자식 노드가 최대 2개로 이뤄진 트리를 의미한다. 그 중 이진 탐색 트리는 노드가 트리에 추가가 될 때, 자동으로 데이터들의 값을 비교하여 노드의 위치를 정하는 트리를 의미한다. 기본적인 원리는 다음과 같다. 1. 추가되는 노드는 루트 노드에서부터 비교가 된다. 2. 루트 노드의 데이터 보다 크면 오른쪽, 작으면 왼쪽 자식 노드로 간다. 3. 루트 노드의 자식 노드와 데이터를 비교하여 역시나 크면 오른쪽, 작으면 왼쪽 자식으로 향한다. 4. 3의 과정을 반복해서 더 이상 자식 노드가 없을 때까지 이동한 다음, 해당 노드의 자식 노드로 등록이 된다. 위와 같은 과정으로 데이터 20을 가진 노드는 24를 가진 노드의 왼쪽 자식으로 등록이 된다. 밑에는 데이터를 삽입할 때 사용하는 함수.. 2023. 4. 27. 이전 1 ··· 6 7 8 9 10 11 12 ··· 20 다음
