지나가던 컴공생

Rabin-Karp 알고리즘은 항상 빠르지는 않지만 일반적으로 빠르게 작동하는 간단한 구조의 문자열 매칭 알고리즘이라는 점에서 자주 사용된다. Ⅰ. 라빈카프 알고리즘은 해시(Hash) 기법을 사용하여 연산속도가 O(1) 이라는 장점이 있다. (시간복잡도는 O(n) cf) 해시는 긴 데이터를 그것을 상징하는 짧은 데이터로 바꾸어 주는 기법 ex) abaca의 해시 값 = 97 * 2^4 + 98 * 2^3 + 97 * 2^2 + 99 * 2^1 + 97 * 2^0 Ⅱ. 해시값이 중복되는 경우(==collision) 포인터를 이용해 연결자료 구조를 이용해 해결한다. Ⅲ. 해시값은 거의 일치하는 일이 없기 때문에 'parent string'과 'pattern string'의 해시값이 일치하는 경우에만 문자열을..

SSC(강한결합요소)는 같은 SCC에 속하는 두 정점은 서로 도달이 가능하다는 특징이 있다. 즉 사이클이 발생할 경우 무조건 SCC에 속한다. 이는 Directed Graph에서만 의미가 있는데, Undirected Graph는 그래프 전체가 무조건 SCC이기 때문이다. SCC를 추출하는 알고리즘에는 코사라주 알고리즘과 타잔 알고리즘이 있는데 코사라주 알고리즘이 구현은 쉽지만 타잔 알고리즘이 더 적용하기 좋다는 점에서 타잔 알고리즘을 사용하여 구현 할 것이다. 1. dfs를 할 때, 처음 정점 x의 부모에게 고유한 번호인 id를 부여한다. 예를들어 d[x] = ++id; 로 작성하면 x의 부모인 d[x]에게 현재 id값에 1을 더한 번호를 부여하는 것이다. 즉 부모==id값이라고 생각하면 됨 2. 정점 ..

이분매칭(bipartite match)은 A집단이 B집단을 선택하는 방법에 대한 알고리즘이다. 사람의 집단을 A, 노트북의 집단을 B라고 할 때 이를 그래프로 나타내면 아래와 같다. 위와 같이 각 집단에 원하는 항목이 있을대 가장 효과적으로 매칭 시키는 알고리즘, 즉 최대 매칭(Max Matching)을 수행하는 알고리즘이다. 다시 말해서 모든 사람이 각각 노트 북을 선택하여 가장 많이 연결 되는 경우의 수를 찾는 것이다. 이는 용량(Capacity)가 1인 네트워크 플로우 문제로도 해석 할 수 있다, 다만 에드몬드 카프 알고리즘은 시간 복잡도가 O(V + E^2) 이기 때문에 이분매칭에 한해 더 빠르고 효율적인 DFS를 활용한 방법으로 구현 할 것이다. 1. 동빈은 A를 선택한다. 2. 태일은 A를 선..

위상정렬(Topolgy sort)는 순서가 정해져있는 작업을 차례로 수행 할 때 그 순서를 결정해 주기 위해 사용하는 알고리즘이다. 위상 정렬은 DAG(Directed Acyclic Graph == 사이클이 발생하지 않는 방향 그래프)에서만 사용가능하다. 여기서는 큐(Queue)를 이용하여 구현할 것이다. Ⅰ. 진입차수(화살표 받는 개수)가 0인 정점을 큐에 삽입한다. Ⅱ. 큐에서 원소를 꺼내 연결된 모든 간선을 제거. Ⅲ. 간선 제거 후 진입차수가 0이 된 정점을 큐에 삽입, 위 과정을 반복. -> 모든 원소를 방문하기 전에 큐가 빈다면 사이클이 존재하는 것이다 (위상정렬 불가능) 모든 원소를 방문했다면 큐에서 꺼낸 순서가 위상 정렬의 결과이다. #include #include #include #def..

Ⅰ. Floyd Warshall 알고리즘은 '모든 정점'에서 '모든 정점'으로의 최단 경로를 구하는 알고리즘이다. Ⅱ. Dijkstra 알괴즘은 가장 적은 비용을 하나씩 선택했다면, Floyd Warshall 알고리즘은 '거쳐가는 정점' 을 기준으로 알 고리즘을 수행한다. 위 테이블은 '현재까지 계산된 최소 비용' 이다. 예를들어, 노드 1을 거쳐가는 경우 대각선과 1이 포함된( (1,n), (n,1) )을 제외한 부분을 갱신시키면 된다. 다시말해 x -> y 로 가는 최소비용과 X -> 1 -> Y로 가는 비용을 비교하여 더 작은 값으로 갱신시킨다. ex) D[2,3] vs D[2,1] + D[1,3] 위와 같은 방법으로 2를 거쳐가는 경우, 3을 거쳐가는 경우등을 계산하면 된다. n을 입력받아 n x..

- 다익스트라 알고리즘은 다이나믹 프로그래밍을 활용한 최단 경로 탐색 알고리즘이다. 흔히 GPS 소프트웨어에서 많이 사용된다. 다익스트라 알고리즘은 특정한 하나의 정점에서 다른 모든 정점으로 가는 최단 경로를 알려준다. - 다익스르타 알고리즘이 다이나믹 프로그래밍 문제인 이유는 "최단 거리는 여러 개의 최단 거리로 이루어져 있기 때문이다." 하나의 최단 거리를 구할 때 그 이전까지 구했던 최단 거리 정보를 그대로 사용 한다. Ⅰ. 출발 노드를 설정한다. Ⅱ. 출발 노드를 기준으로 각 노드의 최소비용을 저장한다. Ⅲ. 방문하지 않은 노드 중에서 가장 비용이 적은 노드를 선택한다. Ⅳ. 해당 노드를 거쳐서 특정한 노드로 가는 경우를 고려하여 최소 비용을 갱신하고 이를 3, 4번을 반복한다. 위와 같은 그래프..

Ⅰ. 하나의 숫자가 소수인지 판별 bool isPrimeNumber(int x) { // 어떤 수 x의 "제곱근" 까지만 검사하는 것이 효과적임 int end = (int) sqrt(x); cout

선형 자료구조 : queue, stack, array 등 비선형 자료구조 : binary tree 등 이진트리는 트리 자료구조를 활용해 데이터 탐색 속도 증진을 위해 사용하는 구조이다. 완전 이진트리인 경우 힙정렬(Heap sort)를 이용해 배열을 사용해도 괜찮았지만, 완전 이진트리가 아닌 경우에는 데이터의 낭비를 줄이기 위 해 포인터를 사용하는 것이 좋음. 이진트리에 사용되는 자료구조에 따라 각 탐색, 삽입, 삭제의 시간 복잡도는 아래와 같다. 이진트리에서 데이터를 참색하는 방법은 크게 3가지가 있다. Ⅰ. 전위순회(Preorder Traversal) (1) 자기 자신을 처리 (2) 왼쪽 자식을 처리 (3) 오른쪽 자식을 처리 Ⅱ. 중위순회(Inorder Traversal) (1) 왼쪽 자식을 처리 ..

ㅇ 크루스칼 알고리즘은 가장 적은 비용으로 모든 노드를 연결 하는 알고리즘 -> 최소 비용 신장트리를 만들기 위함 ex) 여러 개의 도시들을 연결 하고자 할 때 비용을 최소한으로 하기 위해 사용 - 거리(cost)가 짧은 순서대로 그래프에 포함 시키면 됨 - 모든 노드를 최소비용으로 연결만 시키면 되기에 모든 간선 정보를 오름차순으로 정렬 한 뒤에 비용이 적은 간선부터 그래프에 포함 - 최소 비용 신장트리에서는 사이클이 발생하면 안 됨 1. 정렬된 순서에 맞게 그래프에 포함 2. 포함시키기 전에 사이클 테이블 확인 3. 사이클을 형성하는 경우 간선을 그래프에 포함시키지 않음 ★ 사이클이 발생하는지 여부는 Union-Find 알고리즘을 사용 #include #include #include using nam..

Union-Find는 그래프 알고리즘으로써, '합집합 찾기'라는 의미를 가진다. 여러개의 연결되지 않은 노드 집합들이 있다고 가정하자. (1) - (2) - (3) - (4) (5) - (6) - (7) - (8) 1,2,3,4와 5,6,7,8을 각각 연결되어있는 노드들이다. 여러한 그래프에서 '연결성'을 프로그래밍 언어로 표현하는 것이 Union-Find 알고리즘이다. Union-Find 알고리즘의 원리는 노드의 집합중 가장 작은 값을 가지는 노드가 부모 노드라고 가정하고, ex) 1,2,3,4의 부모노드는 모두 1이다. 부모노드가 같으면 연결되어 있다고 생각하는 것이다. find는 해당 노드의 부모 노드를 찾는 알고리즘이고 ex) find(3)을 하면 1을 반환 union은 노드의 집합을 연결하는 알..