• 그래프 임의의 두 개체의 연결 관계를 표현하는 자료구조이다.추천 시스템, 검색 시스템, 지식 표현 및 추출에 사용될 수 있다. • 그래프의 정의 그래프는 정점 집합과 간선 집합의 쌍으로 정의한다 G = (V, E) V(정점) : 하나의 노드는 고유한 key로 식별된다.E(간선) : E = {(u, v) | u, v ∈ V} • 그래프의 종류 방향 그래프 간선에 방향이 있어서 한쪽 방향으로만 갈 수 있다.(u → v)로 표현한다.(u → v) ≠ (v → u) 무방향 그래프 간선을 통해 양방향으로 갈 수 있다.(u, v) 또는 (u ↔ v)로 표현한다.(u, v) = (v, u) 가중치 그래프 간선에 비용(cost) 또는 가중치(weight)가 할당된 그래프이다. • 그래프 용어 인접 정점하나의 정점에..

• Disjoint set (서로소 집합) 두 집합의 교집합이 empty하면 disjoint하다고 한다.입력을 여러 개의 상호 배타적인 그룹으로 나누어 관리할 때 사용한다. • 주요 연산 make-set(u) : 원소 u가 주어졌을때 u만을 담는 새로운 집합을 생성한다.find-set(u) : 입력 원소 u를 담고 있는 집합을 반환한다.union(u, v) : u를 가지고 있는 집합과 v를 가지고 있는 집합을 합친다. Disjoint set에서는 교집합 연산을 고려할 필요가 없다. • Disjoint Set의 표현 Disjoint set은 non-binary tree로 표현한다. 부모 노드를 가리키는 parent pointer tree를 사용한다.(각 자식 노드는 부모를 가리키고, 루트 노드는 자기 자신..

• MaxHeap Classclass MaxHeap {private: static const int root_index = 1; // 루트 노드의 인덱스는 1로 설정 static const int HEAP_SIZE = 200; // 힙의 최대 크기는 200으로 설정 int nodes[HEAP_SIZE]; // 힙 노드를 저장할 배열 int size; // 현재 힙의 크기 // 주어진 인덱스의 왼쪽 자식 노드의 인덱스를 반환 int LEFT(int i) { return i * 2; } // 주어진 인덱스의 오른쪽 자식 노드의 인덱스를 반환 int RIGHT(int i) { return i * 2 +..

• 우선순위(Priority) 어떤 일을 먼저 처리할지 순서를 정하는 것이다.  • 우선순위 큐 우선순위의 개념을 큐에 적용한 자료구조이다.우선순위를 가진 데이터를 저장하며 우선순위가 높은 데이터가 먼저 나가게 된다.  • 우선순위 큐의 ADT 데이터item = (여기서는 key = value = priority라고 심플하게 하자.) 주요 연산insert(item) : 우선순위 큐에 item을 추가remove: 우선순위가 가장 높은 요소를 삭제하고 반환find() : 우선순위가 가장 높은 요소를 삭제하지 않고 반환 우선순위 큐의 종류최소 우선순위 큐 :  우선순위가 작을수록 우선순위가 높음최대 우선순위 큐 : 우선순위가 클수록 우선순위가 높음  • 우선 순위 큐의 구현 방법 1. 배열을 이용해서 구현 ..

BST(1)에서 슈도코드로 다뤘던 것들을 이제 C++ 코드로 살펴보자. • BinaryNode Classclass BinaryNode { // BinarySearchTree 클래스가 BinaryNode의 private 멤버에 접근할 수 있도록 설정 friend class BinarySearchTree;private: int key; // 노드의 키 값 int value; // 노드의 데이터 값 BinaryNode* left; // 왼쪽 자식 노드에 대한 포인터 BinaryNode* right; // 오른쪽 자식 노드에 대한 포인터public: // 생성자: 키, 값, 왼쪽 자식 포인터, 오른쪽 자식 포인터를 초기화 BinaryNode(int key = 0..

• 탐색(Search) 특정 자료구조 내에 저장된 정보를 찾아내는 일이다.방대하게 저장된 데이터에서 원하는 정보를 효율적으로 찾아내는 것은 중요하다. n개의 아이템을 가지는 1차원 배열에서 원하는 값을 찾기 위해 가장 간단한 방법은 순차 탐색이다.그러나 순차 탐색은 최악의 경우 O(n)의 시간 복잡도를 요구한다.(마지막에 있거나 아예 없거나) 그렇다면 Insert/remove/search 등을 O(n) 보다 더 빠르게 할 수 있는 방법은 없을까? 탐색을 위해 특화된 이진 트리인 이진 탐색 트리에 대해 알아보도록 하자. • Key & Value 트리에서 노드는 key와 value를 가진다.Key : 해당 노드를 다른 노드와 구분 짓게 하는 식별자(ID)를 의미한다.Value : key에 대응되는 데이터 값..

• 이진 트리의 순회 순회는 자료구조 내의 데이터를 특정 순서대로 방문하는 것을 의미한다. 선형 자료구조에서의 순회선형적인 순서로 조회한다.이진 트리에서의 순회트리는 비선형 자료구조이기 때문에 여러가지 순서로 노드를 방문할 수 있다. • 이진 트리의 순회 방법 전위 순회(pre-order traversal)루트 출력 → 왼쪽 서브트리 → 오른쪽 서브트리def preorder(node): if node is not NULL: # 현재 노드가 NULL이 아닌 경우에만 수행 print(node.data) # 현재 노드의 데이터를 출력 preorder(node.left) # 왼쪽 자식 노드를 전위 순회 preorde..

• Tree 트리는 계층적인 구조를 나타낼 수 있는 자료구조이다.부모-자식 관계의 노드들로 이루어져 있다. • 트리의 용어 노드(node) : 트리의 구성요소루트(root) 노드 :  제일 상단에 있는 노드(부모가 없는 노드)간선(link, edge) : 노드와 노드를 연결하는 선서브트리(subtree) : 하나의 노드와 자손들로 이루어짐 단말노드(terminal, leaf, external) : 자식이 없는 노드비단말노드(brach, internal) : 자식을 가지는 노드 자식, 부모, 형제, 조상 노드특정 노드를 기준으로 가족 관계를 따진다. 노드의 차수(degree) : 노드의 자식 노드 수노드의 깊이(depth) : 루트 노드에서 특정 노드까지의 간선의 수노드의 레벨(level) : 트리의 계층..

• Recursion Recursion = 재귀함수단 몇개의 문자만으로 문제의 solution을 구할 수 있다.다만 반드시 효율적이지는 않으며, 모든 문제가 재귀적으로 풀리지는 않는다. • 일반적인 Format 1) Simple base case : 더 이상 재귀호출을 진행하지 않고 정답을 생성한다.2) Recursive step : 함수가 재귀적으로 호출된다.모든 재귀함수는 점진적으로 base case로 이동한다. 아니면 무한 loop에 빠진다. 만약 base case가 없다면?스택이 용량이 초과되어 overflow error가 발생할 것이다. • Recursion 푸는 방법 Divide & Conquer : 작은 문제로 나눠주고 각각 풀어준다.우선 가정을 하고 설계한다! 그럼 어떻게 올바른 계산이 되..

• List vs Deque(Stack or Queue) 공통점 : 1차원 배열에 데이터를 저장한다.차이점 : 임의의 포지션에서 연산이 가능하다.(Index로 주어지는 위치에서 삽입/삭제 가능) • 부가연산empty(): 리스트가 비어있으면 true를 반환한다.full() : 리스트가 가득 차있으면 true를 반환한다.size() : 리스트의 아이템들의 개수를 반환한다.  • 메인연산insert(i, item) : 새로운 아이템을 i번째 위치에 삽입한다.remove(i) : i번째 위치의 아이템을 삭제한다.get(i) : i번째 위치의 아이템을 반환한다.replace(i, item) : 아이템과 i번째 위치의 아이템을 교체한다.find(item) : 아이템의 인덱스(위치)를 반환한다.*find(itme)..