순번 유형 01 배열 (Array) 배열 (Array) 배열 리스트 (ArrayList) 02 리스트 (List) 리스트 (List) 연결 리스트 (LinkedList) Array vs ArrayList vs LinkedList 03 스택 (Stack) 스택 (Stack) 04 큐 (Queue) 큐 (Queue) 우선순위 큐 (Priority Queue) 05 힙 (Heap) 힙 (Heap) 06 트리 (Tree) 트리 (Tree) 이진 트리 (Binary Tree) 이진 검색 트리 (Binary Search Tree) 레드 블랙 트리 (Red-Black Tree) B-트리 & B+트리 (B-Tree & B+Tree) 트라이 (Trie) 07 해시 (Hash) 해시 (Hash) 해시 함수 (Hash Fu..
✔ 그래프 그래프(Graph)란? 정점(노드)과 간선(엣지)의 집합 트리는 사이클이 허용되지 않는 그래프 그래프 용어 무방향 그래프 : 정점과 간선의 연결관계에 있어서 방향성이 없는 그래프 방향 그래프 : 정점과 간선의 연결관계에 있어서 방향성이 포함되어 있는 그래프 가중치 그래프 : 간선에 가중치 정보를 두어서 구성한 그래프 비가중치 그래프 : 모든 간선의 가중치가 동일한 그래프 부분 그래프 : 본래의 그래프의 일부 정점 및 간선으로 이루어진 그래프 차수 : 각 정점에 연결된 엣지의 개수 방향 그래프에서는 간선에 방향성이 존재하기 때문에 차수가 두 개로 나뉘게 됨 각 정점에서 나가는 간선의 개수는 진출차수 각 정점으로 들어오는 간선의 개수는 진입차수 그래프를 구현하는 방법 인접 행렬 : 정방 행렬로 그..
✔ 해시 해시(Hash)란? 해시 테이블이라고도 불림 내부적으로 배열을 이용하여 데이터를 저장 해시의 특징 key와 value를 1:1로 연관지어 저장 key를 이용하여 value를 도출 데이터의 고유 인덱스로 접근하여 값을 검색하므로 시간 복잡도가 O(1) 해시 함수를 이용하여 저장할 데이터와 연관된 고유한 숫자인 해시 코드를 만들어낸 뒤 이를 인덱스로 사용 특정 데이터가 저장되는 인덱스는 그 데이터만의 고유한 위치이기 때문에 삽입 연산 시 다른 데이터의 사이에 끼어들어나, 삭제 시 다른 데이터로 채울 필요가 없으므로 연산에 추가적인 비용이 없음 해시 함수 고유한 인덱스 값을 설정하기 위한 특별한 알고리즘 임의의 길이의 데이터를 수학적 연산을 통해 고정된 길이의 데이터로 매핑 해시 함수를 이용해 반횐된..
✔ 트리 트리(Tree)란? 노드와 엣지로 연결된 그래프의 특수한 형태 비선형 자료구조이며 계층적 관계를 표현 트리의 특징 순환 구조(사이클)를 지니고 있지 않고, 1개의 루트 노드가 존재함 (방향성이 있는 비순환 그래프) 루트 노드를 제외한 노드는 단 1개의 부모 노드를 가짐 노드가 N개인 트리는 항상 N - 1개의 간선을 가짐 트리에서 임의의 두 개의 노드를 연결하는 경로는 유일함 트리를 순회하는 방식으로는 전위 순회, 중위 순회, 후위 순회, 레벨 순회가 존재 트리의 부분 트리 역시 트리의 모든 특징을 따름 트리의 구성 요소 노드 : 데이터의 index와 value를 표현하는 요소 엣지 (간선) : 노드와 노드의 연결 관계를 나타내는 선 루트 노드 : 트리에서 가장 상위에 존재하는 노드 부모 노드 ..
✔ 힙 힙(Heap)이란? 배열을 기반으로 한 완전 이진 트리의 일종이므로 이진 힙(Binary Heap)이라고도 불림 여러 값 중, 최대값과 최소값을 빠르게 찾아내도록 만들어진 자료구조 우선순위 큐 구현을 위해 만들어진 자료구조 데이터들이 우선순위를 가지고 있으며, 우선순위가 높은 데이터가 큐에서 먼저 빠져나가게 됨 힙의 특징 힙의 종류로는 최대 힙과 최소 힙이 존재 최대 힙은 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진 트리 최소 힙은 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진 트리 반정렬 상태를 유지 새로운 요소가 들어오면 일단 새로운 노드를 힙의 마지막 노드에 삽입한 후, 새로운 노드를 부모 노드들과 교환하여 힙을 재구성 최대 힙(최소 힙)에서 최대..
✔ 큐 큐(Queue)란? 배열에서 발전된 형태의 선형 자료구조 삽입과 삭제 연산이 선입선출로 이루어지는 자료구조 큐의 특징 먼저 들어간 원소(First In First Out, FIFO)가 먼저 나옴 또는 나중에 들어간 원소(Last In Last Out, LILO)가 나중에 나옴 새 값 추가는 큐의 rear에서 이루어지고, 삭제는 큐의 front에서 이루어짐 O(N)의 시간 복잡도와 공간 복잡도를 가짐 삽입과 삭제가 양방향에서 이루어짐 큐는 빈 메모리가 남아 있어도, rear가 끝에 도달할 경우 꽉 차있는 것으로 판단할 수 있으므로 이를 개선하기 위해 처음과 끝이 연결되어 있도록 간주하는 원형 큐, 연결리스트 큐가 존재 큐 용어 rear : 큐의 가장 끝 데이터를 가리키는 영역 front : 큐에서 ..
✔ 스택 스택(Stack)이란? 배열에서 발전된 형태의 선형 자료구조 삽입과 삭제 연산이 후입선출로 이루어지는 자료구조 스택의 특징 나중에 들어간 원소(Last In First Out, LIFO)가 먼저 나옴. 또는 먼저 들어간 원소(First In Last Out, FILO)가 나중에 나옴 새 값이 스택에 들어가면 top이 새 값을 가리킴 스택에서 값을 빼낼 때 pop은 top이 가리키는 값을 스택에서 빼게 됨 O(N)의 시간 복잡도와 공간 복잡도를 가짐 해당 위치를 기억하고 있는 스택 포인터가 필요함 스택 포인터는 값이 들어갈 위치를 가리킴 스택 포인터가 최대 크기와 같으면 스택이 꽉 찬 것이며 스택이 꽉 찬 것이 아니라면 스택의 최상위 위치에 값을 저장 스택 포인터가 0이 되면 스택이 빈 것이며 스..
✔ 리스트 리스트(List)란? 값과 포인터를 묶은 노드라는 것을 포인터로 연결한 자료구조 트리 구조의 근간이 되는 자료구조 리스트의 특징 인덱스가 없어 값에 접근하려면 Head 포인터부터 순서대로 접근해야 하므로 속도가 느림 논리적 저장 순서와 물리적 저장 순서가 일치하지 않음 원하는 위치를 Search 하기 위해 첫 번째 원소부터 다 확인하며 순회 O(N)의 시간 복잡도로 해당 원소에 접근 포인터로 연결되어 있으므로 데이터를 삽입하거나 삭제하는 연산 속도가 빠름 각각의 원소들은 자기 자신 다음에 어떤 원소인지만을 기억하므로 이 부분만 다른 값으로 바꿔 삭제와 삽입이 가능 O(1)의 시간 복잡도로 삽입, 삭제 가능 선언할 때 크기를 별도로 지정하지 않아도 됨 추가할 때마다 동적으로 메모리 할당을 받게 ..
