프로그래밍/Algorithm & Data Structure10 [Data Structure]그래프(Graph) 그래프란, 오일러가 만들어 낸 연결 관계를 단순화하여 표시한 도구이다. 정점(Vertex)와 간선(Edge)로 이뤄져 있으며 시각화하면 다음과 같다. 정확하게 정의하면 그래프는 '정점의 모음'과 이를 잇는 '간선의 모음'의 결합이다. 위 사진처럼 간선을 통해 서로 이웃된 각 정점은 그래프 안에서 경로를 형성한다. 이 경로는 한 정점에서 다른 정점으로 이동할 수 있는 길을 의미하고, 위처럼 정점 사이의 이동은 간선을 통해서만 가능하다. 또한 어느 한 경로가 정점 하나를 두 번 이상 거치도록 되어 있다면 그 경로를 일컬어 '사이클'을 형성한다고 말한다. 경로는 방향성을 가지기도 한다. 방향성이란, 두 정점 간의 이동 방향을 의미하며 한 쪽으로만 방향이 정해져 있으면 반대로는 이동이 불가능하고 이런 방향성을 .. 2023. 6. 21. [Data Structure] 해시 테이블(Hash Table) 리스트 기반의 이진 탐색 트리의 경우, 특정 데이터의 검색의 시간복잡도는 O(logn)이다. 매 탐색에서 전체 데이터를 절반으로 나눠서 검색을 행하기 때문이다. 하지만 우리는 여기서 아쉬움을 느낀다. 배열의 경우 주소인 이름으로 접근해서 인덱스로 주소를 계산해서 접근하기 때문에, 임의 접근이 가능하면서 상수의 시간복잡도를 가진다. 우리는 이 장점을 활용할 방법이 없을까? 답은 바로 해시 테이블에 있다. 해시 테이블이 무엇인지 알기 위해 우선 해시에 대한 정의를 알아야 한다. 단어의 뜻을 찾아보면 다음과 같은 문장들을 확인할 수 있다. If you make a hash of a job or task, you do it very bably. Hash is a dish made from meat cut int.. 2023. 5. 29. [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. 이전 1 2 3 다음
