CS/자료구조7 [자료구조] 힙(Heap) 🟡 힙(Heap) - 최댓값 및 최솟값을 찾아내는 연산을 빠르게 하기위해 고안된 자료구조 - 다음과 같은 힙 속성을 만족해야 한다. A가 B의 부모노드이면, A의 key값과 B의 key값 사이에는 대소관계가 성립한다. 🟡 힙의 종류 ① 최대 힙 - 부모노드의 키 값이 자식노드의 키 값보다 항상 큰 힙 ② 최소 힙 - 부모노드의 키 값이 자식노드의 키 값보다 항상 작은 힙 * 키 값의 대소관계는 오로지 부모노드와 자식노드 간에만 성립하며, 특히 형제 사이에는 대소관계가 정해지지 않는다. 🟡 힙의 시간 복잡도 - 힙에서의 데이터 삽입과 삭제에 대한 시간 복잡도는 O(log n) 🟡 힙의 연산 ① 삽입 - 새로운 요소를 힙에 추가한다. - 일반적으로 맨 마지막 위치에 요소를 추가한 후, 부모노드와 비교하여 위.. 2023. 8. 25. [자료구조] 우선순위 큐(Priority Queue) 🟡 우선순위 큐(Priority Queue) - 원소들이 우선순위를 가지고 있을 때 사용되는 자료구조 - 높은 우선순위를 가진 원소는 낮은 우선순위를 가진 원소보다 먼저 처리된다. - 만약 두 원소가 같은 우선순위를 가진다면 그들은 큐에서 그들의 순서에 의해 처리된다. - 작업 스케줄링, 그래프 알고리즘 등 다양한 분야에서 활용된다. 🟡 우선순위 큐의 연산 ① 삽입: 하나의 원소를 우선순위를 지정하여 큐에 추가한다. ② 삭제: 가장 높은 우선순위를 가진 원소를 큐에서 제거하고 이를 반환한다. 🟡 우선순위 큐의 구현 - 우선순위 큐는 추상적인 개념이다. 그러므로 다양한 방법들을 이용해 구현될 수 있다. - 대표적인 방법들 ① 힙: 가장 많이 사용되는 방법. 이진 트리 자료구조의 일종이다. O(logN)의 .. 2023. 8. 24. [자료구조] 덱(Deque) 🟡 덱(Deque) - double-ended queue 의 줄임말 - 양쪽 끝에서 삽입과 삭제가 모두 가능한 자료 구조의 한 형태 2023. 6. 22. [자료구조] 그래프(Graph) 🟡 그래프(Graph) - 공집합이 아닌 꼭짓점의 집합 V와 서로 다른 꼭짓점의 쌍(Vi, Vj)을 연결하는 모서리의 집합 E로 구성된 구조 🟡 그래프의 종류 ① 가중치 그래프 - 그래프 G=(V, E)에서 각 모서리에 가중치가 부여된 그래프 ② 방향 그래프 - 화살표로 모서리를 표현해 인접하는 꼭짓점 간의 순서를 알 수 있는 그래프 ③ 완전 그래프 - 그래프 G=(V, E)내에 있는 모든 꼭짓점 u, v간에 변이 있는 그래프 2023. 1. 18. [자료구조] 연결 리스트, 링크드 리스트(Linked List) 🟡 연결 리스트, 링크드 리스트(Linked List) - 각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식으로 데이터를 저장하는 자료구조 - 데이터를 담고 있는 노드들이 연결되어 있는데, 노드의 포인터가 다음이나 이전의 노드와의 연결을 담당 - 종류에는 단일 연결 리스트, 이중 연결 리스트 등이 있다. - 연결 리스트는 자료의 추가와 삭제가 O(1)의 시간 안에 가능하다는 장점 보유 - 배열, 트리 구조와는 다르게 특정 위치의 데이터를 검색해 내는데에는 O(n)의 시간이 걸린다는 단점 보유 🟡 연결 리스트의 종류 ① 단일 연결 리스트 - 단일 연결 리스트는 각 노드에 자료 공간과 한 개의 포인터 공간이 있고, 각 노드의 포인터는 다음 노드를 가리킨다. ② 이중 연결 리스트 - 이중 연결 .. 2023. 1. 9. [자료구조] 큐(Queue) 🟡 큐(Queue) - 삽입과 삭제 연산이 선입선출(FIFO: First-in First-out)로 이뤄지는 자료구조 - 은행에서 번호표를 받고 업무를 처리하는 것과 같은 원리 - 삽입과 삭제가 양방향에서 일어남 - 너비 우선 탐색(BFS) 문제 풀이에 효과적 🟡 큐 용어 · 위치 - front: 큐에서 가장 앞 데이터를 가리키는 영역 - rear: 큐에서 가장 끝 데이터를 가리키는 영역 · 연산 - add(Enqueue): rear 부분에 새로운 데이터를 삽입하는 연산 - poll(Dequeue): front 부분에 있는 데이터를 삭제하고 확인하는 연산 - peek: 큐의 맨 앞(front)에 있는 데이터를 확인할 때 사용하는 연산 2022. 12. 21. 이전 1 2 다음
