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

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

/* 대표적인 문자열 매칭 알고리즘. 기본적으로 문자열 매칭 알고리즘이란 특정한 글이 있을 때, 그 안에서 하나의 문자열을 찾는 알고리즘. 단순 비교 문자열 매칭 알고리즘은 말그대로 하나하나 모두 확인하는 알고리즘으로 가장 간단한 형태의 알고리즘. 하지만 최악의 경우 시간이 많이 소요됨으로 비효율적. KMP 알고리즘은 접두사와 접미사의 개념을 활용하여 반복되는 연산을 얼마나 줄일 수 있는지 판별하여 매칭할 문자열을 빠르게 점프하는 기법. 접두사와 접미사를 구하게 됐을 때, 접두사와 접미사가 일치하는 경우에 한해서는 점프하여 수행. */ #include #include using namespace std; vector makeTable(string pattern) //접두사와 접미사의 최대길이를 포함하는 ..

/* 이분 매칭은 네트워크 플로우 알고리즘과 연계되는 개념. A 집단이 B 집단을 선택하는 방법에 대한 알고리즘. 효과적으로 매칭시키다라는 말은 최대매칭을 의미. 이분 매칭 알고리즘은 각 용량을 1로 설정한 네트워크 플로우문제로 표현 가능. 네트워크 플로우 에드몬드 카프 알고리즘은 시간복잡도가 O(V * E^2). 하지만 이분 매칭에 한해 더 빠르고 효율적으로 알고리즘 설계 가능. DFS 사용. 이분 매칭을 간단히 풀 때의 시간 복잡도는 O(V * E). */ #include #include #define MAX 101 //정점의 갯수 using namespace std; vector a[MAX]; int d[MAX]; //특정한 정점을 점유하고 있는 노드의 정보를 담는 배열. bool c[MAX]; /..

/* 네트워크 플로우는 특정한 지점에서 다른 지점으로 데이터가 얼마나 많이 흐르고 있는가를 측정하는 알고리즘. 일반적으로 최대 유량(Max Flow) 문제라고 정의함. 최대 유량 문제는 각 간선에 정해진 용량이 있을 때, A 에서 B로 최대로 보낼 수 있는 유량의 크기를 구하는 문제. 기본적으로 최대 유량 문제는 단순하게 가능한 모든 경우의 수를 탐색하는데, 이 때 BFS(너비 우선 탐색)을 일반적으로 이용. 이것을 에드몬드 카프(Edmonds-Karp) 알고리즘이라 함. 최대 유량 알고리즘은 순서가 상관 없음. 남아있는 양이 1이 넘으면 계속해서 흘려 보내주면 알아서 최적화. 기본적으로 BFS를 사용하여 모든 가능한 경로를 다 찾아서 남아있는 용량만큼 유량을 흘려 보내주는 것을 반복. 음의 유량도 함께..

/* 유향 그래프에서 모든 정점이 모든 다른정점에 대해 도달 가능한 경우, 강하게 연결 되었다라고 함. 강한 결합 요소는 부분 그래프의 모든 정점이 강하게 연결된 임의의 유향그래프의 분할임. 그래프가 강하게 연결되었는지, 그래프에서 강한 연결 요소를 찾는 것은 선형시간에 가능. SCC 알고리즘이라 불림. SCC는 같은 SCC에 속하는 두 정점은 서로 도달이 가능하다는 특징이 있음. 사이클이 발생하는 경우 무조건 SCC. SCC를 추출하는 알고리즘에는 코사라주 알고리즘과 타잔 알고리즘이 있음. 구현은 코사라주가 쉽고 적용은 타잔이 쉬움. 타잔 알고리즘은 모든 정점에 대해 DFS를 수행하여 SCC를 찾는 알고리즘. 부모에서 자식으로 나아가는 알고리즘으로 DFS알고리즘이 사용됨. SCC 자체로는 큰 의미가 없..