Data structure11 [Data Structure] Priority Queue(우선순위 큐) 우선순위 큐큐의 변형된 자료구조로 각 요소에 우선순위가 부여되고 우선순위에 따라서 요소를 삽입하거나 삭제한다일반적인 큐의 선입선출(FIFO) 규칙을 따르지 않고 우선순위가 높은 요소가 먼저 처리된다. 최소 우선순위 큐 : 가장 낮은 우선순위의 요소가 먼저 처리최대 우선순위 큐 : 가장 높은 우선순위의 요소가 먼저 처리연산삽입 : 새로운 요소를 우선순위를 고려하여 큐에 추가삭제 : 우선순위가 가장 높은 요소를 큐에서 제거삽입 또는 삭제 후에도 항상 우선순위에 따라 정렬된 상태를 유지한다 일반 큐와 차이점선입선출 규칙을 따르지 않고 우선순위를 고려함일반 큐는 정렬되지 않지만 우선순위 큐는 정렬된 상태를 유지함구현 방법 배열 또는 리스트를 사용한 구현삽입 시 순차적으로 추가삭제 시 우선순위를 검색하여 제거삽입.. 2025. 1. 20. [Data Structure] Heap(힙) 힙힙은 항상 완전 이진 트리의 형태를 유지한다모든 레벨이 완전히 채워져 있어야 하며, 마지막 레벨은 왼쪽에서 오른쪽으로 순차적으로 채워진다힙 속성최대 힙(Max Heap)부모 노드의 값이 자식 노드의 값보다 항상 크거나 같다루트 노드에 트리의 최대 값이 저장된다최소 힙(Min Heap)부모 노드의 값이 자식 노드의 값보다 항상 작거나 같다루트 노드에 트리의 최소 값이 저장된다힙은 동일한 값을 가지는 노드를 허용한다삽입, 삭제 연산에 평균 및 최악의 경우 모두 O(log n)의 시간 복잡도를 가진다 주요 연산삽입새로운 값은 트리의 마지막 자리에 추가된다 이후 부모 노드와 비교하여 속성이 만족될 때까지 상향 조정(Bubble Up)을 한다최대 값 또는 최소 값 조회루트 노드를 조회하여 최대 값 또는 최소 값.. 2025. 1. 20. [Data Structure] Binary Search Tree(이진 탐색 트리) 이진 탐색 트리(BST)이진 탐색 트리란 정렬된 이진 트리로 다음과 같은 속성을 가지고 있다. 왼쪽 자식 노드에 있는 값은 부모 노드의 값 보다 작아야 한다오른쪽 자식 노드에 있는 값은 부모 노드의 값 보다 커야 한다** 일반적으로 BST는 중복 값을 허용하지 않는다 데이터를 삽입, 삭제, 검색할 때 평균적으로 O(log n)의 시간 복잡도를 가진다한쪽으로 치우친 편향 트리인 경우 O(n)의 시간 복잡도를 가질 수 있다 주요 연산탐색(Search)트리의 루트 부터 시작하여 특정 값을 찾는다특정 값이 현재 노드보다 작으면 왼쪽 크면 오른쪽원하는 값을 찾거나 탐색할 노드가 없으면 종료한다삽입(Insertion)루트부터 시작하여 새로운 값을 삽입한다현재 노드보다 작으면 왼쪽, 크면 오른쪽빈 자리를 발견하면 그.. 2025. 1. 20. [Data Structure] Graph(그래프) Graph(그래프)정점(vertex)와 간선(edge)으로 구성된 자료 구조로 객체 간의 관계를 표현하는데 사용된다. 구성요소정점 : 객체(데이터)를 저장하는 노드간선 : 객체 간의 관계, 두 정점 간의 연결선 사용 예시 : 소셜 네트워크, 지도, 컴퓨터 네트워크 그래프의 종류방향 그래프간선에 방향이 있어 A > B는 가능하지만 B > A는 별도로 정의해야 한다ex : 웹 페이지 링크, 종속성 관계종속성 관계란 의존성을 의미한다 하나의 노드가 다른 하나의 노드에 의존하거나 영향을 받는 관계를 나타낼 때 사용한다. ex : 작업 A를 완료해야 B를 시작, 모듈 A가 모듈 B를 참조할 때(B가 없으면 A가 동작하지 않음), 어떤 과목을 학습할 때 다른 과목의 선행학습(기초 수학 > 미적분 > 공학 수학)무방.. 2025. 1. 19. CS 자료구조 B-Tree와 B+Tree B-트리는 균형이진탐색트리에서 파생된 자료구조다. 데이터베이스와 파일 시스템에서 대용량 데이터를 효율적으로 관리하는데 사용된다. B-트리는 2개 이상의 더 많은 자식 노드를 가질 수 있으며, 디스크 I/O를 최소화하도록 설계되었다. ㅇ B-Tree의 특징B-트리는 이진트리와 다르게 하나의 노드에 많은 수의 정보를 가지고 있을 수 있다. 최대 M개의 자식을 가질 수 있는 B트리를 M차 B트리라고 하며 다음과 같은 특징을 갖는다. 규칙노드는 최대 M개부터 M/2개의 자식을 가질 수 있다.노드에는 최대 M - 1부터 M/2 -1개의 키가 포함될 수 있다.노드의 키가 n개라면 자식의 수는 n + 1이다.최소차수는 자식의 하한값을 의미하며 최소차수가 t라면 M = 2t - 1을 만족한다.(최소차수 t가 2라면 3.. 2024. 10. 10. CS 자료구조 Trie(트라이) 트라이는 주로 문자열 검색에 사용되는 특수한 형태의 자료구조다. 많은 문자열이 공통된 접두사를 가질 때 효율적인 탐색을 제공하도록 설계되어 있다. 트라이는 사전(Dictionary)처럼 동작하며, 문자열의 삽입, 검색, 삭제 등의 연산을 빠르게 수행할 수 있다. ㅇ 트라이의 특징노드 구조트라이의 각 노드는 하나의 문자(Character)를 나타내며, 자식 노드들로 연결된다.각 경로는 특정 문자열의 접두사를 나타낸다.루트 노드트라이의 시작점으로, 빈 문자열을 표현하거나 의미 없는 노드로 시작한다. 모든 문자열의 경로가 이 루트에서부터 시작 된다.삽입 연산문자열을 삽입할 때는 문자열의 각 문자를 노드로 변환하여 차례대로 삽입한다. 공통된 접두사를 가진 문자열은 동일한 경로를 공유하며, 공통 접두사 이후부터 .. 2024. 10. 9. [자료구조] Hash(해시), Hash Table, HashMap ㅇ Hash개념해시는 임의 길이의 입력 데이터를 고정 길이의 해시 값 또는 해시 코드로 매핑하는 과정 혹은 그 결과물을 의미한다해시 함수를 사용하여 매핑하고, 이 함수는 입력 값(Key)을 특정 규칙에 따라 연산해 일정한 길이의 정수로 변환한다 특징고속성키를 즉시 특정 값으로 매핑할 수 있으므로 연산 속도가 매우 빠르다결정론적 성질같은 입력은 항상 같은 해시 값을 반환한다해시충돌서로 다른 입력에 대해 서로 다른 해시 값을 주는 것이 이상적이나, 해시충돌이 발생할 수 있다균등 분포성우수한 해시 함수는 가능한 한 해시 값을 균등하게 분포시켜 충돌을 최소화한다 ㅇ Hash Table개념해시 테이블은 (키, 값) 쌍을 저장하는 자료구조로 키를 해시 함수에 통가시켜 해시 값을 얻고 이를 배열의 인덱스로 사용하여 .. 2024. 10. 8. CS 자료구조 Priority Queue(우선순위 큐) 우선순위 큐는 일반적인 큐와 다르게 데이터를 우선순위에 따라 처리하는 자료구조다. 큐에 들어오는 데이터가 삽입된 순서가 아닌 각 데이터에 지정된 우선순위에 따라 먼저 처리된다. ㅇ 우선순위 큐의 특징우선순위에 따라 처리일반적인 큐에서는 선입선출(FIFO) 방식으로 데이터를 처리하지만, 우선순위 큐에서는 우선순위가 높은 데이터가 먼저 처리된다. 우선순위가 높은 데이터가 먼저 빠져나오고, 낮은 데이터는 나중에 처리된다.우선순위의 종류최대 우선순위 큐(Max Priority Queue)가장 큰 우선순위를 가진 요소가 먼저 처리된다.최소 우선순위 큐(Min Priority Queue)가장 작은 우선순위를 가진 요소가 먼저 처리된다.구현 방법우선순위 큐는 일반적으로 힙(Heap) 자료 구조를 사용하여 구현된다. .. 2024. 10. 8. CS 자료구조 Heap(힙) 힙은 완전 이진 트리 형태를 따르는 자료구조다. 주로 우선순위 큐를 구현하는데 사용된다. ㅇ 힙의 특성완전 이진 트리(Complete Binary Tree) 힙은 모든 레벨이 꽉 차 있어야 하며(마지막 레벨은 제외), 마지막 레벨은 왼쪽에서부터 차례대로 채워져야 한다.항상 가장 왼쪽부터 빈 자리를 채워나가는 트리구조다. 힙 속성(Heap Property)최대 힙(Max Heap)부모 노드가 자식 노드보다 항상 크거나 같아야한다. 루트에 가장 큰 값이 위치한다.최대값을 빠르게 추출할 수 있다.최소 힙(Min Heap)부모 노드가 자식 노드보다 항상 작거나 같아야한다. 루트에 가장 작은 값이 위치한다.최소값을 빠르게 추출할 수 있다. ㅇ 힙의 주요 연산삽입(Insertion)새로운 값을 삽입할 때는 트리의.. 2024. 10. 8. 이전 1 2 다음
