/* 순서가 정해져 있는 작업을 차례로 수행해야 할 때, 그 순서를 결정해 주기 위해 사용하는 알고리즘. 위상 정렬 알고리즘은 두가지 답을 알 수 있음. 현재 그래프가 위상 정렬이 가능한 그래프인지 , 가능하다면 결과는 무엇인지. 예시) 대학생 되기 >> 학과 사이트 가입하기 >> 4학년 되기 >> 정보처리기사 합격하기 >> 자격 서류 제출하기 >> 졸업시험 신청하기 >> 졸업 위상 정렬은 여러 개의 답이 존재할 수 있다는 점에서 매력적. 위상 정렬은 DAG(Directed Acyclic Graph)에만 적용 가능. 즉, 사이클이 없는 방향 그래프. 위상 정렬은 스택, 큐 모두 이용가능. 1. 진입차수가 0인 정점을 큐에 삽입. 2. 큐에서 원소를 꺼내 연결된 모든 간선 제거. 3. 간선 제거 이후 진입..

/* 모든 정점에서 모든 정점으로의 최단 경로를 구할 때 쓰임. 가장 적은 비용을 하나씩 선택해야 했던 다익스트라 알고리즘과는 다르게 플로이드 와샬 알고리즘은 기본적으로 거쳐가는 정점을 기준으로 알고리즘을 수행. 플로이드 와샬 알고리즘 또한 다이나믹 프로그래밍 기술에 의거. */ #include using namespace std; const int number = 4; int INF = 10000000; //자료 배열 초기화. int a[4][4] = { {0, 5, INF, 8}, {7, 0, 9, INF}, {2, INF, 0, 4}, {INF, INF, 3, 0} }; void floydWarshall() { //결과 그래프 초기화. int d[number][number]; for (int i =..

/* 다이나믹 프로그래밍을 활용한 대표적인 최단 경로 탐색 알고리즘. 특정한 하나의 정점에서 다른 모든 정점으로 가는 최단 경로를 알려줌. 음의 간선은 포함할 수 없음. 다이나믹 프로그래밍을 이용하는 이유는 최단거리는 여러 개의 최단 거리로 이루어져 있기 때문. 하나의 최단 거리를 구할 때, 그 이전까지 구했던 최단 거리 정보를 그대로 사용.(갱신함) */ /* 1. 출발 노드 설정. 2. 출발 노드를 기준으로 각 노드의 최소 비용을 저장. 3. 방문하지 않은 노드 중에서 가장 비용이 적은 노드를 선택. 4. 해당 노드를 거쳐서 특정한 노드로 가는 경우를 고려하여 최소 비용 갱신. 5. 3 ~ 4 반복. */ ////선형 탐색으로 구현했을 때. 가장 간단히 구현할 수 있으나, 노드갯수에 비해 ////간선..

/* 소수를 판별하는 알고리즘. 기본 소수 판별 알고리즘의 시간 복잡도는 O(N). 모든 경우의 수를 판별해야 하기 때문에 비효율적. 결과적으로만 봤을 때, 특정한 숫자의 제곱근까지만 약수의 여부를 검증하면 됨. 에라토스테네스의 체는 대량의 소수를 한번에 판별하고자 할 때 사용함. */ #include using namespace std; int main() { int number = 100000; int a[100001]; for (int i = 2; i

/* 하나의 문제는 단 한번만 풀도록 하는 알고리즘. 단순 분할 정복으로 풀게 될 시 심각한 비효율성을 낳음.(정렬과 같은 몇몇 요소 제외) 피보나치 수열이 대표적. 큰 문제를 작은 문제로 나눌 수 있을 때 사용가능. 작은 문제에서 구한 답은 그것을 포함하는 큰 문제에서도 동일할 때 사용가능. 이미 계산한 결과를 배열에 잠시 저장. 동일한 계산 시 저장된 값 반환. */ #include using namespace std; //기본 피보나치 수열. //수가 커지면 에러가 난다.(연산횟수 약 2^n) int Fibonacci(int x) { if (x == 1) return 1; if (x == 2) return 1; return Fibonacci(x - 1) + Fibonacci(x - 2); } //d..

/* 가장 많이 사용되는 비선형 자료구조는 이진트리. 이진트리는 데이터의 탐색 속도 증진을 이해 사용하는 구조. 포인터를 사용해야함. 완전이진트리는 배열로 표현가능하지만, 다른 이진트리는 배열로 표현하기 어렵기 때문.(데이터의 낭비를 줄일 수 있음) 이진트리에서 데이터를 탐색하는방법은 전위순회, 중위순회, 후위순회가 있음. 수식기반형식은 후위순회방식이 사용됨. */ #include using namespace std; const int number = 15; //하나의 노드 정보를 선언. typedef struct node *treePointer; typedef struct node { int data; treePointer leftChild, rightChild; } node; //전위 순회. void..