거창한 시작

Union(X, Y) 연산 - 서로 중복되지 않는 두 개의 집합을 병합 - X가 속한 집합(부모)에 Y가 속한 집합(부모)을 병합 Find(X) 연산 - 하나의 원소가 어떤 집합(부모)에 속해있는지를 반환 - X가 속한 집합(부모)을 찾아 반환 동작 구현 - 배열로 구현 * Union(X, Y) 연산에서 모든 원소를 순회하면서 Y가 속한 집합 번호를 X가 속한 집합 번호로 변경 * Union(X, Y)의 시간복잡도 O(n) * Find(X) 연산에서 한 번에 X가 속한 집합을 찾음 * Find(X)의 시간 복잡도 O(1) - 트리로 구현 * Union(X, Y) 연산에서 X가 속한 집합의 자손으로 Y가 속한 집합을 붙임 * Union(X, Y)의 시간복잡도 O(logN) * Find(X) 연산에서 트리를..

Graph - 노드와 간선으로 구성된 자료구조 - 객체 간의 관계를 표현하는 자료구조 - root와 부모-자식 관계가 없음 - 트리는 그래프의 부분집합 - 네트워크 모델 용어 표현 - 정점(vertex) : 객체. 노드 - 간선(edge) : 객체를 연결하는 선. 노드를 연결하는 선 - 인접 정점 : A 정점에서 간선으로 연결된 다른 정점 - 진입 차수 : 방향 그래프에서 A 정점으로 들어오는 간선의 수 - 진출 차수 : 방향 그래프에서 A 정점에서 나가는 간선의 수 - 단순 경로 : 경로 중에 반복되는 정점이 없는 경로. 같은 간선을 포함하지 않는 경로 - 사이클(cycle) : 단순 경로의 시작 정점과 종료 정점이 동일한 경우 그래프의 종류 1) 무방향 그래프 - 간선을 통해서 양방향으로 이동 - (..

Tree - 하나의 root 노드를 갖음 - 사이클이 없음 - 계층적 모델 - 그래프의 한 종류로, 방향이 있는 연결 그래프 - N개의 노드와 N-1개의 간선이 존재 용어 표현 - 루트(root) : 부모가 없는 노드 - 단말 노드 (leaf) : 자식이 없는 노드 - 간선 : 노드를 연결하는 선 - 형제 : 같은 부모를 갖는 노드 - 차수 : 자식 노드와 연결된 간선의 개수 - 노드의 크기 : 자신을 포함한 모든 자손 노드의 개수 - 노드의 깊이 : 루트에서 어떤 노드까지 도달하는 데 가치는 간선의 수 트리의 종류 1) 이진 트리 - 자식 노드 개수(차수)를 최대로 2개를 갖는 트리 (1) 이진 탐색 트리 (Binary Search Tree) - 이진 검색을 위한 구조 - 왼쪽 서브 트리의 모든 키 값..

Hash table - 키(key)값에 해시값(hash value)를 연관지어 저장하는 자료구조 용어 표현 - Hash function : 임의의 길이를 갖는 임의의 데이터에 대해 고정된 길이의 데이터로 매핑하는 함수 - 해싱(Hashing) : 데이터를 매핑하는 과정 - 키(key) : 매핑 전 원래 데이터 값 - 해시값(hash value) : 해시 함수를 적용하여 나온 고정된 길이의 값 - bucket : 데이터가 저장되는 공간 - 값(value) : 데이터 값 장점 - 광대한 데이터를 유한한 해시값으로 매핑하므로써 작은 크기의 캐쉬 메모리로도 프로세스를 효율적으로 관리 * How? Hash function으로 임의의 데이터를 고정된 길이의 데이터로 매핑하기 때문이다. - 탐색에 index로 has..

Heap - 영어로는 '쌓아올리다.' 의미 - 형태 : 완전 이진 트리 - 원리 : 요소들 중에 최대값/최소값을 가져오기 고안된 트리형 자료구조 종류 - 최대 힙 * 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진 트리 * 부모 노드 key value >= 자식 노드 key value - 최소 힙 * 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진 트리 * 부모 노드 key value

Priority queue - 큐에 우선순위가 적용된 추상적 개념 - 우선순위가 높은 요소를 먼저 꺼내는 자료구조 특징 - 일반적으로 힙의 구조 - 힙 구조일 경우, 삽입과 삭제의 시간 복잡도 : O(logN) - 힙 구조를 알아보기 구현 - 배열 * 문제점 1 : 우선순위가 중간인 값을 삽입할 때, 삽입하는 위치 뒤에 있는 모든 요소를 옮겨야 함 * 문제점 2 : 요소를 찾을 때, 우선순위를 비교해야 하므로 최악의 경우에는 모든 요소와 비교해야 함. 시간복잡도 O(n) - 연결 리스트 * 문제점 1 : 요소를 찾을 때, 우선순위를 비교해야 하므로 최악의 경우에는 모든 요소와 비교해야 함. 시간복잡도 O(n) - 힙 * 장점 1 : 이진 트리의 깊이가 증가할 때마다 저장 가능한 자료의 개수는 2개가 되고..

Stack - 나중에 넣은 element가 먼저 나오는 (LIFO : Last In First Out) 자료구조 특징 - 삽입과 삭제 시간 복잡도 : O(1) 사용 - 재귀 알고리즘에서 back-tracking할 때 주로 사용 - 예시 : undo, 웹 페이지의 backward Queue - 먼저 넣은 element가 먼저 나오는 (FIFO : First In First out) 자료구조 특징 - 삽입과 삭제 시간 복잡도 : O(1) 사용 - 시간 순으로 입력된 데이터를 처리하는 알고리즘에서 주로 사용 - 예시 : 프로세스 관리, 프린터 종류 - 선형 큐 * 막대 모양 * 크기가 제한되어 빈 공간을 사용하려면 모든 자료를 꺼내거나 자료를 한 칸씩 옮겨야 하는 단점 * 오버플로우 : 큐가 꽉 차서 더 이상..

Array - index와 데이터들로 이루어진 자료구조 - 예시 * int grade[3]을 선언했을 때, 메모리 상에서 저장 모습 특징 - 정적 메모리 - element에 접근하는 시간 복잡도 : O(1) - 삽입과 삭제 시간 복잡도 : O(n) Linked list - 데이터와 포인터를 가진 노드들이 한 줄로 연결된 자료구조 특징 - element에 접근하는 시간 복잡도 : O(n) - 삽입과 삭제 시간 복잡도 : O(1) - 트리를 만드는 데 사용