자료구조

배열

Linked List img 연속적인 메모리 위치에 저장되지 않는 선형 데이터 구조 (포인터를 사용해서 연결된다) 각 노드는 데이터 필드와 다음 노드에 대한 참조를 포함하는 노드로 구성 왜 Linked List를 사용하나? > 배열은 비슷한 유형의 선형 데이터를 저장하는데 사용할 수 있지만 제한 사항이 있음 > > 1) 배열의 크기가 고정되어 있...

📌 Array, ArrayList, LinkedList 정리 1. Array (배열) 정의 : 배열은 고정된 크기의 연속적인 메모리 영역에 동일한 타입의 데이터를 저장하는 자료 구조다. 장점: 빠른 접근: 인덱스를 사용하여 데이터에 빠르게 접근한다. (O(1)의 시간 복잡도) 메모리 사용이 효율적이다. 단점: 고정된 크기: 크기가 미리 정해져 있...

스택(Stack) 입력과 출력이 한 곳(방향)으로 제한 LIFO (Last In First Out, 후입선출) : 가장 나중에 들어온 것이 가장 먼저 나옴 언제 사용? 함수의 콜스택, 문자열 역순 출력, 연산자 후위표기법 스택 구현 코드 동적 배열 스택 위처럼 구현하면 스택에는 MAX_SIZE라는 최대 크기가 존재해야 한다 (스택 포인터와 M...

📌 우선순위 큐: 우선순위의 개념을 큐에 도입한 자료 구조 데이터들이 우선순위를 가지고 있고 우선순위가 높은 데이터가 먼저 나간다. 우선순위 큐의 이용 사례 시뮬레이션 시스템 네트워크 트래픽 제어 운영 체제에서의 작업 스케쥴링 수치 해석적인 계산 우선순위 큐는 배열, 연결리스트, 힙으로 구현이 가능한데 힙으로 구현하는 것이 가장 효율적이다...

트리는 값을 가진 노드(Node)와 이 노드들을 연결해주는 간선(Edge)으로 이루어져있다. 그림 상 데이터 1을 가진 노드가 루트(Root) 노드다. 모든 노드들은 0개 이상의 자식(Child) 노드를 갖고 있으며 보통 부모-자식 관계로 부른다. 아래처럼 가족 관계도를 그릴 때 트리 형식으로 나타내는 경우도 많이 봤을 것이다. 자료구조의 트리도 ...

이진탐색트리 이진탐색트리의 목적은? > 이진탐색 + 연결리스트 이진탐색 : 탐색에 소요되는 시간복잡도는 O(logN), but 삽입,삭제가 불가능 연결리스트 : 삽입, 삭제의 시간복잡도는 O(1), but 탐색하는 시간복잡도가 O(N) 이 두가지를 합하여 장점을 모두 얻는 것이 '이진탐색트리' 즉, 효율적인 탐색 능력을 가지고, 자료의 삽입 삭제...

해시(Hash) 데이터를 효율적으로 관리하기 위해, 임의의 길이 데이터를 고정된 길이의 데이터로 매핑하는 것 해시 함수를 구현하여 데이터 값을 해시 값으로 매핑한다. > menu = {"Lee": 5, "Kim": 3, "Park": 2} 결국 데이터가 많아지면, 다른 데이터가 같은 해시 값으로 충돌나는 현상이 발생함 'collision' 현상 그...

📌 트라이(Trie) > 문자열에서 검색을 빠르게 도와주는 자료구조 트라이(Trie)는 문자열을 저장하고 효율적으로 탐색하기 위한 트리 형태의 자료구조이다. 우리가 검색할 때 볼 수 있는 자동완성 기능, 사전 검색 등 문자열을 탐색하는데 특화되어있는 자료구조라고 한다. 래딕스 트리(radix tree) or 접두사 트리(prefix tree) or...

📌 개요 > 이진 트리는 하나의 부모가 두 개의 자식밖에 가지질 못하고, 균형이 맞지 않으면 검색 효율이 선형검색 급으로 떨어진다. > B트리는 이진트리에서 발전되어 모든 리프노드들이 같은 레벨을 가질 수 있도록 자동으로 벨런스를 맞추는 트리입니다. 또한 정렬된 순서를 보장하고, 멀티레벨 인덱싱을 통한 빠른 검색을 할 수 있기 때문에 DB에서 사용하는...