/* 백준 1931번. 그리디 알고리즘 이용. 그리디 알고리즘 문제이기 때문에, 어떻게 하면 최대한 많이 우겨넣을 수 있을 지 생각 해봄. 반례가 없어야함. 공책에 예를 들어서 써보기로 함. 회의가 일찍 시작하는 순으로 정렬해도 늦게 끝나는 회의 때문에 안됨. 회의가 짧은 순으로 정렬하더라도 겹치는 경우엔 해당시키지 못함. 일찍 끝나는 순으로 정렬하면 될 것 같아서 해봄. 시간복잡도가 O(n^2)이므로 일반적으로 반복문을 돌리게 되면 시간 초과가 나올 수 있음. */ /* 한개의 회의실에서 이를 사용하고자 하는 N개의 회의에 대하여 사용표를 만들고자 함. 각 회의 I에 대해 시작시간과 종료시간이 주어져 있고, 각 회의가 겹치지 않으면서 회의실을 이용할 수 있는 최대 개수를 찾는 것. 회의가 끝나는 동시에..

/* 그리디 알고리즘은 당장 눈 앞에 보이는 최적의 상황만을 쫒는 알고리즘. 항상은 아니지만, 어느정도는 최적의 해에 근사한 값을 빠르게 구할 수 있다는 장점이 있음. 특정한 상황에서는 그리디 알고리즘이 최적의 해를 보장할 수도 있음. 그리디 알고리즘의 대표적인 예는 거스름 돈 문제. 가장 적은 양의 화폐를 주는 것이 편하므로, 무조건 더 큰 화폐 단위부터 거슬러 준다는 알고리즘만 지키면 최적의 해를 보장. 이러한 그리디 알고리즘은 기본적으로 무조건 큰 경우대로, 무조건 작은 경우대로, 무조건 긴 경우대로 등 극단적으로 문제에 접근 한다는 점에서 정렬(sort)기법이 함께 사용되는 경우가 많음. 대표적인 예시로 크루스칼 알고리즘.(모든 간선을 정렬한 이후, 짧은 간선부터 연결하는 최소 비용 신장 트리 알..

/* 특이한 문자열 매칭 알고리즘. 항상 빠르지는 않으나, 일반적인경우 빠르게 작동하는 간단한 구조의 문자열 매칭 알고리즘. 해시(Hash) 기법을 사용. Hash는 긴 데이터를 그것을 상징하는 짧은 데이터로 바꾸어주는 기법. 보통 문자열 매칭은 연속적인 문자열이 이어지는 경우에 기반하기 때문에 Hash또한 연속적인 경우에 더 빠르게 구할 수 있는 알고리즘을 채택하여 적용한다면 빠르게 연산 가능. 해시함수는 각 문자의 아스키코드 값에 2의 제곱 수를 차례로 곱하여 더해준 것. 문자열이 달라지면 결과로 출력되는 해시 값도 바뀜. 해시 값이 중복되어 충돌이 일어나는 경우도 있으나, 발생률이 높지 않아 무시. 충돌이 일어날 경우 포인터를 이용해 연결 자료구조로 해결. 즉, 라빈 카프 알고리즘은 여러 개의 문자..

/* 백준 1948번. 위상정렬이용. 모든임계경로를 다 구해야 하므로 역추적을 수행해야함. */ /* 첫째 줄에 도시의 개수 n(1 ≤ n ≤ 10,000)이 주어지고 둘째 줄에는 도로의 개수 m(1 ≤ m ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 도로의 정보가 주어진다. 처음에는 도로의 출발 도시의 번호가 주어지고 그 다음에는 도착 도시의 번호, 그리고 마지막에는 이 도로를 지나는데 걸리는 시간이 주어진다. 도로를 지나가는 시간은 10,000보다 작거나 같은 자연수이다. 그리고 m+3째 줄에는 지도를 그리는 사람들이 출발하는 출발 도시와 도착 도시가 주어진다. 모든 도시는 출발 도시로부터 도달이 가능하고, 모든 도시로부터 도착 도시에 도달이 가능하다. */ #incl..

/* 백준 1516번. 위상정렬이용. 모든 정점이 수행될 수 있는 최소 시간을 출력하는것이므로, 단순히 임계경로를 각각 출력하면 됨. 간선이 연결되는 순간을 기준으로 현재보다 더 시간이 오래걸리는 경우가 발생한다면 계속해서 갱신하는 방식으로 답을 구할 수 있음. */ /* 첫째 줄에 건물의 종류 수 N(1 ≤ N ≤ 500)이 주어진다. 다음 N개의 줄에는 각 건물을 짓는데 걸리는 시간과 그 건물을 짓기 위해 먼저 지어져야 하는 건물들의 번호가 주어진다. 건물의 번호는 1부터 N까지로 하고, 각 줄은 -1로 끝난다고 하자. 각 건물을 짓는데 걸리는 시간은 100,000보다 작거나 같은 자연수이다. */ #include #include #include #define MAX 501 using namespac..

/* 백준 2252번. 위상정렬을 이용한 가장 기본적인 문제. */ /* 첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 횟수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의미이다. 학생들의 번호는 1번부터 N번이다. */ #include #include #include #define MAX 32001 using namespace std; int n, inDegree[MAX], result[MAX]; //노드갯수, 진입차수갯수, 결과값갯수 vector a[MAX]; //정점마다 자신과 연결되어있는 간선 void topologySort() { queue q; //진입 차수..