Hyul_code

Deque는 Double-end Queue로 배열과 유사하지만 벡터와는 달리 양쪽 끝에서 삽입과 삭제가 가능하다 Doubly Linked List에 배열의 요소가 들어가 있다고 생각하면 이해하기 편하다. Deque의 ADT는 push_back() : 뒤쪽에 data 추가 push_front() : 앞쪽에 data 추가 pop_back() : 뒤쪽의 data 삭제 pop_front() : 앞쪽의 data 삭제 at() : 인덱스를 통해 접근 operator[] : 배열과 같이 인덱스를 통해 접근 resize() : 크기 조절 size() : 원소의 개수 return empty() : 비어있는지 확인 아래는 사용 예시이다. #include #include using namespace std; int main..

Priority Queue는 각 요소가 특정 우선 순위를 가지고 있는 큐이다. 높은 우선순위를 가진 data가 낮은 우선 순위를 가진 data보다 먼저 처리된다. Priority Queue의 ADT를 보면 insert(): 우선순위 큐에 새로운 data를 추가 deleteMax() or deleteMin() : 우선순위가 가장 높은(낮은) 항목을 제거 getMax() or getMin(): 우선순위가 가장 높은(낮은) 항목을 return isEmpty() : 비어있는지 확인 size() : 우선순위 큐에 저장된 data의 개수를 return clear() : 우선순위 큐의 모든 data 제거 Priority Queue 같은 경우 작업 스케줄링, 그래프 알고리즘, 네트워크 라우팅 등에서 활용된다. 구현 방..

Vector는 C++ 표준 라이브러리에서 동적 배열 즉, 크기가 고정되지 않은 배열을 의미한다. (Array와 비슷하게 생각해도 된다.) 한 번에 한 타입만 저장이 가능하다. 저장공간보다 많은 양의 데이터를 추가시킬 경우 현재 보유하고 있는 메모리의 두 배만큼 할당한다. 이때, Vector는 메모리가 연속적인데 연속적으로 할당하지 못할 경우 다른 공간 모든 원소를 하나하나 복사한다. 이때 속도가 느려지기에 메모리 할당을 중간에 바꾸게 된다면 이 부분을 조심해야한다. Vector의 ADT를 보면 push_back(): 벡터의 끝에 요소를 추가한다. pop_back(): 벡터의 끝에서 요소를 제거한다. at(): 주어진 인덱스에 해당하는 요소를 return size(): 벡터에 저장된 요소의 개수를 retu..

1. Queue Queue는 FIFO구조 즉, 최근에 입력된게 나중에 나오는 구조이다. Queue의 ADT를 보면 enqueue(): 가장 뒤에 data input dequeue(): 가장 앞에 있는 data output front(): 큐의 가장 앞에 있는 항목 return isempty(): 큐가 비어있는지 확인 size(): 큐에 저장된 data 수 return 밑에 코드는 queue를 활용해서 구현한 예시 코드이다. #include #include using namespace std; int main() { // 큐 생성 queue myQueue; // Enqueue (추가) myQueue.push(10); myQueue.push(20); myQueue.push(30); // Size (크기) c..

BFS(Breadth-First Search)은 그래프나 트리와 같은 자료 구조에서 사용되는 탐색 알고리즘이다. 시작 노드로부터 거리에 따라 레벨 단위로 탐색하고 같은 레벨의 노드들을 모두 방문하면 다음 레벨의 노드들을 방문한다. BFS는 Queue를 사용하여 구현한다. BFS Algorithm Pseudocode 를 보면 Algorithm BFS(G,s) L_0

DFS(Depth-First Search)은 그래프나 트리와 같은 자료 구조에서 사용되는 탐색 알고리즘이다. 하나의 경로를 따라 최대한 깊이 파고들면서 탐색하고 더이상 탐색할 노드가 없을 때 까지 해당하는 경로를 따라간다. DFS는 Stack or Recursion을 사용하여 구현한다. DFS Algorithm Pseudocode를 보면 Algorithm DFS(G, V) Input graph G and a start vertex v of G Output labeling of the edges of G in the connected component of v as discovery edges and back edges v.setLabel(VISITED) for all e in G.incidentEdges..

1. Linear Search : Array or List의 처음부터 끝까지 순차적으로 탐색 시간 복잡도 : O(n) - 최악의 경우 2. Binary Search : Array or List가 정렬되어 있는 경우 중간 항목과 비교하면서 탐색 시간 복잡도 : O(log n) - 정렬되었을 때 최악의 경우 3. Hash Search : Hash function을 활용해 키와 값을 연결하는 방법으로 탐색 시간 복잡도 : O(1) - 평균의 경우 4. Tree Search : Binary Tree, Binary Search Tree, AVL, B-Tree 등 구조를 활용해 탐색 시간 복잡도 : O(log n) - Binary Search Tree 의 경우 5. Graph Search : DFS (Depth-F..

1. Array - Array List : https://hyul-code.tistory.com/2 ADT : begin(), end(), size(), empty(), insertFront(), insertBack(), removeFront(), removeBack(), insert(), remove() - Vector : https://hyul-code.tistory.com/61 ADT : at(), set(), insert(), erase(), size(), empty() 2. Linked Lists - Singly Linked List : https://hyul-code.tistory.com/3 ADT : front(), addFront(), removeFront(), addBack(), remo..

Algorithms을 분석 할 때 아래의 내용들을 고려해야한다. - Space 사용량 - Running Time Pseudocode의 예시로 max값을 찾는 code를 보면 Algorithm arrayMax(A[], n) Input array A of n integers Output Max element of A currentMax

Stack은 LIFO구조 즉, 최근에 입력된게 먼저 나오는 구조이다. Stack에는 기본적으로 .push(), .pop() 함수가 존재하고 필요에 따라 .top(), empty() 가 있다. push는 말 그대로 이 구조에 입력하는 것이고 pop은 제일 위에 있는 것을 꺼내는 것이다. top은 제일 위에 있는 것에 대한 정보를 출력하고 empty는 현재 비어있는지 확인하는 함수이다. 밑에 코드는 Wikipedia에서 공유된 C 코드이다. 다음은 윈도우 기준의 C언어로 제작된 스택의 예제이다. /* Stack Example */ #include #include #include int Stack[10]; int top=-1; int push(int dat); int pop(void); int printsta..