그래프란? 그래프는 정점과 간선으로 구성하는 자료구조를 뜻한다. 그래프와 관련된 용어 정리 정점 (Vertex) : Node라는 용어를 사용하기도 한다. 위 사진에서 숫자가 있는 동그라미 즉, 각 지점을 의미한다. 간선 (Edge or Link) : 보통 Edge라고 한다. 두 정점끼리의 연결된 선을 의미한다. 화살표 표시가 된 선도 있고, 없는 것도 있는데, 둘 다 간선이다. 가중치 : 간선 위에 표시된 숫자이다. 보통 간선을 타고 이동할 때, 얼마나 중요한지 순서를 나타냈다고 보면 된다. 비용 같은 것들을 예시로 들 수 있다. 가중치가 없는 그래프들은 모두 가중치가 동일한 그래프이다. Directed Graph (유향 그래프) : 위 사진에서 오른쪽 그래프처럼 간선에 방향성이 있는 그래프이다. Und..

Dp란? 하나의 큰 문제를 여러개의 작은 문제로 나누어서 결과를 저장하여 다시 큰 문제를 해결할 때 사용하는 것이다. (코딩테스트 단골 문제이며, 숫자의 범위가 크거나 경우의 수가 엄청 많은 문제들이 나올 때, 써야 하는 방법이다.) Dp를 사용하는 이유 Dp는 재귀의 업그레이드 버전이라고 볼 수 있다. 동일한 함수를 다시 불러서 사용하는 건데, 다만 점화식 형태처럼 계산이 복잡하다. 그래서 수행해야 할 명령들이 기하급수적으로 늘어날 수 있다. (ex. 피보나치 수를 계산하는 방법은 return f(n)=f(n-1)+f(n-2)이다. n이 100일 때를 구한다면 함수 호출 횟수는 엄청나게 많을 것이고, 약 90만년 정도가 소요된다.) 요약하면, 재귀를 응용하는 것보다 시간 복잡도를 낮출 좋은 방법이 Dp..

설명 : Heap의 구조 힙은 큐에서 변형된 것이라고 생각하면된다. Priority Queue(우선순위 큐)라고 불린다. 큐가 앞으로 빼고 뒤로 넣는 자료 구조(First in First out)이면, 우선순위 큐는 그렇지 않고, 우선순위를 가진다. 힙(Heap)은 크게 두 가지로 나뉜다. 1. 최대 힙 : 루트 노드에서 단말 노드까지 우선순위가 높은 순서대로 내려오는 것 2. 최소 힙 : 루트 노드에서 단말 노드까지 우선순위가 낮은 순서대로 내려오는 것 위 사진을 배열로 나타내면 [11 , 7, 10 , 1, 3, 5, 9]와 같다. 여기서 자료를 넣는 방법과 빼는 방법을 구현해야 하는데 알고 있어야 하는 공식은 다음과 같다. 자식 노드에서 부모 노드로 가는 공식 : (Index-1)/2 부모 노드에서..

설명 : Dequeue의 구조 덱은 큐의 진화 버전이라고 생각하면 된다. 큐가 앞으로 빼고 뒤로 넣는 자료 구조이면, 덱은 앞으로 뒤로도 뺴고 뒤로 넣는 자료구조이다. 코드 : Dequeue.cpp : #include #define maxsize 5; using namespace std; class Dequeue { private: int front; int rear; int size; int *values; int number; public: Dequeue() //생성자 함수 { size = maxsize; values = new int[size]; //최대크기만큼 동적 배열 생성 front = 0; //앞을 나타내는 변수 rear = 1; //뒤를 나타내는 변수 number = 0; //현재 들어가 ..

설명 : queue의 구조 큐는 "줄을 서다"라는 의미를 가지고 있다. 선입선출, 먼저 들어온 것이 먼저 나간다라는 구조를 생각하면 된다.. (First In, First Out) 흡사 은행 창구나 식당을 생각하면 된다. 먼저 무언가 요청하면 먼저 실행된다. 실생활 어느 곳에 쓰이는 지 예시를 들어보면, 대표적인 것으로 게임을 돌릴 때 "큐를 잡는다"라고 한다. 게임에서도 먼저 돌리면 먼저 잡게 해주는 큐 구조이다. 원형 큐 선형 큐(원래 큐 형태)의 단점을 보완하기 나온 형태이다. 선형 큐를 구현하면 문제점이 나오게 될 것이다. 그것은 바로 빈 공간이다. 데이터를 들여보내는 Enequeue와 내보내는 Dequeue를 하면, 어떤 데이터 안에 빈 공간이 있을 수 있다. 그러나 이것을 차 있다고 생각할 것..

설명 : 스택(stack)은 "쌓아놓은 더미"를 의미한다. 방금 들어온 것이 먼저 나가는 그런 구조를 생각하면 된다. (Last In, First Out) 흡사 "프링글즈 통"을 생각하면 이해하기 쉽다. 실생활 어느 곳에 쓰이는 지 예시를 들어보면, 대표적인 곳으로 문서나 인터넷 사용 시 되돌리기 기능을 사용할 떄라고 생각하면 된다. 코드 : stack.cpp : #include using namespace std; class Stack { private: int top; int MaxSize; char* stack; public: //1. 기본 구조와 상태를 판단 해주는 함수 Stack(int size); //생성자 함수 bool isFull(); //스택 구조가 가득 차 있는지 bool isEmpty..