그래프란 정점과 간선으로 이루어진 자료구조 그래프 용어 정점(vertex) : 노드(node)라고도 하며 데이터가 저장 됨 간선(edge): 링크(arcs)라고도 하며 노드간의 관계를 의미 인접 정점(adjacent vertex) : 간선에 의해 연결된 정점 단순 경로(simple-path): 같은 간선을 자나가지 않는 경로 차수(degree): 무방향 그래프에서 하나의 정점에 인접한 정점의 수 진출 차수(out-degree) : 방향그래프에서 사용되는 용어로 한 노드에서 외부로 향하는 간선의 수 진입차수(in-degree) : 방향그래프에서 사용되는 용어로 외부 노드에서 들어오는 간선의 수 그래프 구현 방법 -인접 행렬 -인접 리스트 인접 행렬 그래프의 노드를 2차원 배열로 만든 형식 인접 정점인 경우..

덱 (Deque) 삽입과 삭제가 양쪽 끝에서 모두 발생할 수 있는 자료구조 큐의 장점과 스택의 장점을 합쳐놓은 자료구조이다. 특징 크기가 가변적 중간요소가 삽입, 삭제될 때 , 요소들을 앞/ 뒤로 밀 수 있으므로 vector보다 좋은 성능을 가짐 앞/뒤 삽입 삭제 성능은 좋지만 중간의 삽입/삭제 성능은 좋지 않음 시간복잡도 삽입/삭제 : 원소를 앞,뒤에 삽입하는 경우 : O(1) 탐색 : 원소를 탐색하는 경우 O(1) 인덱스 접근 단점 중간에서 삽입 삭제가 어려움 구현이 어려움

우선순위 큐 들어온 순서와 상관없이 우선순위가 높은 데이터가 먼저 출력 되는 방식의 큐 우선 순위 큐 구현 방법 비교 구현 방법 삽입 삭제 순서 없는 배열 O(1) O(n) 순서 없는 연결 리스트 O(1) O(n) 정렬된 배열 O(n) O(1) 정렬된 연결 리스트 O(n) O(1) 힙 O(logn) O(logn) 일반적으로 힙을 이용하여 구현 우선순위가 낮은 데이터가 빠져나오지 못하는 기아현상이 일어날 수 있음 | j3sung.tistory.com/740 [자료구조] 힙 (Heap) 힙 (Heap) 완전 이진 트리의 일종으로 우선순위 큐를 위하여 만들어진 자료구조 여러 개의 값들 중에서 최댓값이나 최솟값을 빠르게 찾아내도록 만들어진 자료구조 힙은 일종의 반정 j3sung.tistory.com

큐 (Queue) 한쪽 끝(rear)에서는 삽입연산만 이루어지며 다른 한쪽 끝(front)에서는 삭제연산만 이루어지는 FIFO(First In First Out) 형식의 자료구조 큐의 연산 - enqueue : 큐에 데이터를 넣는 작업 - dequeue : 큐에서 데이터를 꺼내는 작업 - front : 데이터를 꺼내는 부분에 데이터를 반환 - rear : 데이터를 넣는 부분에 데이터를 반환 시간복잡도 삽입/삭제 : 원소를 삽입 삭제하는 경우 O(1) 검색 : 탐색을 하려면 원소를 하나하나 꺼내 확인해야 한다. O(n) 선형 큐 일반적인 큐의 형태 push가 될 때 rear(back) 포인터를 하나 증가, pop이 될 때마다 front 포인터를 증가하는 방식으로 구현 큐에 데이터를 넣는 경우: 프론트는 고..

스택이란 한 쪽 끝에서 자료의 삽입과 삭제가 이루어지는 LIFO 형식의 자료구조 스택의 연산 - push(item) 삽입 : 스택에 자료를 넣음 - pop() 삭제 : 스택의 자료를 제거 - top() = peak 읽기 : 스택의 맨 위 요소 반환 - empty() : 스택이 비어있는지 확인 시간복잡도 삽입/ 삭제 : O(1) 맨 위 원소 접근 검색 : O(n) 원소를 꺼내서 확인 과정이 필요

힙 (Heap) 완전 이진 트리의 일종으로 우선순위 큐를 위하여 만들어진 자료구조 여러 개의 값들 중에서 최댓값이나 최솟값을 빠르게 찾아내도록 만들어진 자료구조 힙은 일종의 반정렬 상태를 유지 (부모 노드의 키 값이 자식 노드의 키 값보다 항상 큰(작은) 이진 트리) 힙 트리에서는 중복된 값을 허용한다. (이진 탐색 트리에서는 중복된 값을 허용하지 않는다.) 힙(heap)의 구현 힙을 저장하는 표준적인 자료구조는 배열 이다. 구현을 쉽게 하기 위하여 배열의 첫 번째 인덱스인 0은 사용되지 않는다. 특정 위치의 노드 번호는 새로운 노드가 추가되어도 변하지 않는다. 힙에서의 부모 노드와 자식 노드의 관계 왼쪽 자식의 인덱스 = (부모의 인덱스) * 2 오른쪽 자식의 인덱스 = (부모의 인덱스) * 2 + 1..

트리란 트리는 부모-자식 관계의 노드들로 이루어져있으며, 계층적인 구조를 나타내는 자료구조 노드가 N개인 트리는 항상 N-1개의 간선을 가짐 트리 용어 노드(node): 트리를 구성하는 기본 원소 루트 노드(root node/root): 트리에서 부모가 없는 최상위 노드, 트리의 시작점 부모 노드(parent node): 상위 레벨로 직접 연결된 노드 자식 노드(child node): 하위 레벨로 직접 연결된 노드 형제 노드(siblings node): 같은 부모 노드를 갖는 노드들 리프 노드(leaf (node))/단말 노드(terminal node): 자식이 없는 노드 간선(edge): 노드간의 연결선 레벨(level): 깊이가 같은 노드끼리의 집합 높이(height): 가장 긴 루트 경로의 길이 차..

단순 연결 리스트 (Simple List) 시작부분에 head가 있으며 노드에 값과 다음 노드를 가리키는 주소값을 가지고 있습니다. 단방향으로 진행되는 리스트를 의미합니다. 장점 : 추가 삭제시 O(1)의 시간복잡도를 가짐 단점 : 배열이나 트리 구조와는 달리 특정 위치 검색시 O(n) 의 시간이 걸림 이중 연결 리스트 (Doubly List) 양방향으로 이동할 수 있는 리스트로 노드에서 다음 노드를 가리키는 주소값과 이전 노드를 가리키는 주소값 두개를 가지고 있습니다. 양방향으로 이동할 수 있다는 장점으로 데이터를 삭제할 때 이전 노드를 찾기위해 한번 더 탐색을 하지 않아도 됩니다. 단순 - (B를 지우기 위해서 B까지 탐색, B이전에 있는 노드를 찾기위해 A를 찾을때까지 탐색, A와 C를 연결) 이중..