공부하자

이분 그래프란? 인접한 정점끼리 서로 다른 두가지 집합으로만 나눈 그래프를 의미한다. 위 그림과 같이 모든 정점이 두 집합으로 나뉘고(여기서는 서로 다른 두 색상으로 구별한다.) 같은 집합끼리는 인접하지 않는 그래프의 형태이다. 이분 그래프의 특징 한 간선의 양 끝 정점은 서로 다른 집합에 속해 있어야 한다. 같은 집합의 정점끼리는 하나의 간선으로 이어질 수 없다. Cycle이 발생했을 때, 그 Cycle을 잇는 간선의 개수는 짝수여야 한다. 간선이 없고 정점만 있는 그래프도 이분 그래프이다. 이분 그래프 판별볍 이분 그래프 여부를 판별하기 위해서는 보통 DFS나 BFS로 그래프를 탐색하면서 판별한다. 1. BFS , DFS 를 수행하며 각 정점을 방문할때 마다 인접한 그룹과 다른 색으로 칠한다. 2. ..

신장 트리란? (ST, Spanning Tree) 모든 임의의 정점이 연결된 그래프의 부분 그래프이다. 모든 정점이 간선으로 연결되어 있지만, 사이클은 존재하면 안된다. 최소 신장 트리란? (MST, Minimum Spanning Tree) 그래프의 간선에 가중치가 부여될때, 신장 트리를 구성하는 간선들의 가중치의 합이 가장 작은 신장 트리이다. 이 최소 신장 트리를 구할때엔 보통 2가지 알고리즘을 활용해 최소 신장 트리를 구하게 되는데, 크루스칼 알고리즘과 프림 알고리즘이 그것이다. 최소 신장 트리의 특징 - 신장 트리들 중 간선의 가중치 합이 최소이다. - N개의 정점을 갖는 그래프에 대해 N-1개의 간선만 사용해야 한다. - 사이클이 존재하면 안된다. - 항상 최단 경로를 보장하지는 않는다. => ..

이진탐색트리(Binary Search Tree, BST)는 널리 사용되는 형태의 이진트리이다. BST는 다음과 같은 속성있다. 부모 노드의 값 >= 왼쪽 자식 노드의 값 부모 노드의 값 left, value); } //생성할 값이 더 작으면 왼쪽 노드로 순회하여 재귀 else { if (!current->right) current->right = new node {value, NULL, NULL}; else insert_impl(current->right, value); } //생설할 값이 더 크면 오른족 노드로 순회하여 재귀 } //노드 삽입 public: void inorder() { inorder_impl(root); } private: void inorder_impl(node* start) { i..

Deque Queue는 선형 리스트로 선입선출(FIFO) 방식을 사용하고 시작과 끝을 가리키는 포인터로 삽입과 삭제를 한다. 이렇게 Queue는 앞으로는 삭제, 뒤로는 삽입을 할 때 사용하는데 Deque는 삽입과 삭제를 한쪽이 아닌 앞, 뒤 양쪽에서 할 수 있다. Deque의 특징 1. 크기가 가변적이다. 2. 앞과 뒤에서 삽입과 삭제가 좋다. 3. 중간에 데이터 삽입, 삭제가 용이하지 않다. 4. 구현이 쉽지 않다. 5. 랜덤 접근이 가능하다. Deque를 사용하는 경우 1. 앞과 뒤에서 삽입, 삭제를 한다. 2. 저장할 데이터 개수가 가변적이다. 3. 검색을 거의 하지 않는다. 4. 데이터 접근을 랜덤하게 하고 싶다. 아래 코드는 덱을 활용한 백준 #28279 덱2의 소스코드이다. #include #..

Queue queue의 사전적 의미는 무엇을 기다리는 사람, 차량 등의 줄 혹은 줄을 서서 기다리는 것을 의미하는데 이처럼 줄을 지어 순서대로 처리되는 것이 큐라는 자료구조이다. 큐는 데이터를 일시적으로 쌓아두기 위한 자료구조로 스택과는 다르게 FIFO(First In First Out)의 형태를 가진다. FIFO 형태는 뜻 그대로 먼저 들어온 데이터가 가장 먼저 나가는 구조이다. queue는 C++ 표준 라이브러리(Standard Template Library)에 있는 정의 되어 있어 필요할 때마다 만들어 사용하지 않고 include 하여 사용하면 편리하다. Queue의 특징 1. 먼저 들어간 자료가 먼저 나오는 구조 FIFO(First In FIrst Out) 구조 2. 큐는 한 쪽 끝은 프런트(fr..

Stack 자료 구조 중 하나인 stack의 사전적 정의는 '쌓다', '더미'이다. 상자에 물건을 쌓아 올리듯이 데이터를 쌓는 자료 구조라고 할 수 있다. stack은 나중에 들어간 것이 먼저 나오는 (Last In First Out)의 형태를 띠는 자료구조이다. 이 방식이 stack의 가장 큰 특징이자 스택을 사용하는 이유라고 할 수 있다. stack은 C++ 표준 라이브러리(Standard Template Library)에 있는 정의되어 있어 필요할 때마다 만들어 사용하지 않고 include 하여 사용하면 편리하다. Stack의 특징 1. 먼저 들어간 자료가 나중에 나옴 LIFO(Last In First Out) 구조 2. 시스템 해킹에서 버퍼오버플로우 취약점을 이용한 공격을 할 때 스택 메모리의 영..