Programming/Algorithm (17) 썸네일형 리스트형 다익스트라 알고리즘(Dijkstra Algorithm) 1. 개념 다익스트라 알고리즘은 어떤 노드에서 다른 노드까지의 거리(가중치)가 주어졌을 때 특정 노드에서 다른 모든 노드까지의 최단 거리를 구하는 알고리즘이다. 이때 음의 가중치가 존재해서는 안되고, 방향-무방향 그래프 모두 가능하다. 2. 구현 Distance[i] : 출발점(S)에서 i 정점까지의 최단거리를 저장하는 배열 --> 초기화 과정에서 Distance[S] = 0 을 제외한 나머지는 모두 무한대로 초기화한다. 방문하지 않은 정점 중에서 Distance가 최소인 정점 I를 선택한다. 정점 I와 인접한 모든 정점 J에 대해서 현재까지 저장된 최단거리보다 새로운 정점을 거쳐서 가는 거리가 더 작을 경우에는 D[j] = D[i] + 새로운 정점까지의 거리로 갱신한다. 말로만 설명해서는 알기 힘들고 .. 서로소 집합(Disjoint Set: Union-Find) 1. 개념 Disjoing Set란 공통 원소가 없는 "상호 배타적"인 부분 집합들로 나누어진 원소들에 대한 정보를 저장하고 조작하는 자료구조이다. 서로소 집합을 만드는 과정을 Union-Find 라고 한다. 2. 구현 Union-Find는 3가지 과정을 통해 진행된다. 1) 초기화 : N 개의 원소가 각 정해진 초기 집합에 있도록 설정 2) Union : 두 원소 a,b가 주어졌을 때 이들이 속한 두 집합을 하나로 합함 3) Find : 원소 a가 주어졌을 때 이 원소의 속한 집합을 찾음 1234567891011121314151617vector parent, rank_cnt; for(int i=0; i rank_cnt[v]) swap(u,v); parent[u] = v; if(rank_cnt[u] ==.. 라빈 카프 알고리즘(Rabin-Karp Algorithm) 1. 개념 해싱을 사용해 일대일 매칭을 하는 알고리즘이다. 어떠한 S에서 W를 찾을때 S의 길이를 N, W의 길이를 M으로 가정하자. 제일 무식한 방법으로 W를 찾을 때에는 O(N*M)의 시간복잡도를 가지고 찾아야한다. (KMP 글 참고) 라빈 카프 알고리즘은 문자열을 모든 위치에서 비교해보는데, 먼저 해당 위치의 해시값을 비교하고 같다면 그 후에 단순 비교를 시작한다. 해당 위치의 부분 문자열과 찾으려는 단어가 다르면서 해시값이 같을 수는 있지만, 같은데 해시값이 다른 경우는 불가능한 점을 이용한 것이다. 여기서 중요한 점은 문자열을 해싱하려면 적어도 문자열 길이만큼 O(M)의 소요시간이 들어간다. 매번 해시값을 계산하다보면 시간 복잡도가 O(N*M)이 되어서 알고리즘이 쓸모가 없어진다. 그렇기 때문에.. 문자열 검색 알고리즘(KMP) 1. 개념 KMP 알고리즘은 문자열 검색 알고리즘으로 알고리즘을 만든 사람의 이름 Knuth, Morris, Prett의 글자를 와서 이름이 붙었다. 우선 이 알고리즘을 왜 사용하는지를 보기 위해 단순한 문자열 검색의 예를 들어보겠다. 문자열 abcdefghijklmnop 이 있을때 ghi 문자열을 찾아보자. 단순하게 검색한다면 다음과 같이 검색할 것이다. abcdefghijklmnop (1) ghi(2) ghi(3) ghi... 이런 식으로 한 자리씩 이동하면서 비교하는 방법이 있다. 만약 이러한 방법으로 검색을 한다면 문자열의 길이만큼 비교횟수가 증가해서 시간 복잡도가 굉장히 커진다. ( O(N*M), N : 텍스트의 길이, M : 비교 문자열의 길이) 하지만 KMP 알고리즘을 사용하면 O(N+M)의.. 강한 연결 요소(Strongly Connected Component) 1. 개념 위 그래프는 큰 그래프를 3개의 SCC(Strongly Connected Component)로 분할한 것을 보여준다. SCC는 일종의 서브그래프로, 하나의 SCC안에 있는 어떤 두 정점 u,v를 고르면 SCC 내부에서 u에서 v로 가는 직/간접적인 경로가 존재하는 것을 뜻한다. 또한, SCC는 maximal한 성질을 가져서 가능한 SCC가 커야한다. 위 그래프에서 오른쪽의 SCC인 {c,d,h}의 하위 집합 중 {c, d} 또한 SCC의 첫번째 성질은 만족하지만, 정점 h를 추가해도 여전히 성질이 만족하므로 h는 반드시 추가되어야한다는 뜻이다. 즉, 유향 그래프에서는 항상 파티션을 분할해 SCC를 만들 수 있고, O(n)안에 모든 SCC를 분리하는 것이 가능하다. *출처 : http://blo.. 위상정렬(topological sorting) 1. 개념 위상 정렬은 유향 그래프의 꼭짓점들(vertex)을 변의 방향을 거스르지 않도록 나열하는 것을 의미한다. 위상정렬을 가장 잘 설명해 줄 수 있는 예로 대학의 선수과목(prerequistie) 구조를 예로 들 수 있다. 만약 특정 수강과목에 선수과목이 있다면 그 선수 과목부터 수강해야 하므로, 특정 과목들을 수강해야 할 때 위상 정렬을 통해 올바른 수강 순서를 찾아낼 수 있다. 이와 같이 선후 관계가 정의된 그래프 구조 상에서 선후 관계에 따라 정렬하기 위해 위상 정렬을 이용할 수 있다. 정렬의 순서는 유향 그래프의 구조에 따라 여러 개의 종류가 나올 수 있다. 위상 정렬이 성립하기 위해서는 반드시 그래프의 순환이 존재하지 않아야 한다. 이 점에서 비순환 유향 그래프이다. *출처 : 위키디피아 .. 이분 매칭(Bipartite Matching) 1. 개념 이분 그래프에서 A 그룹의 정점으로부터 B 그룹의 정점으로 간선을 연결할 때, A 그래프 하나의 정점이 B 그래프 하나의 정점만 가지도록 구성된 것을 뜻한다. *이분 그래프 : 정점을 두 개의 그룹으로 나누었을 때, 존재하는 모든 간선의 양 끝 정점이 서로 다른 그룹에 속하는 형태의 그래프 2. 구현 그림을 잘 못그려서 설명하기가 어려운데 (다른 블로그의 그림들을 참조하면 이해가 더 빠를듯) A 그래프의 정점을 하나씩 순서대로 방문해서 B 그래프의 정점 하나와 연결해준다. 만약 A 그래프의 n번째 정점이 방문하는 B 그래프의 노드에 이미 A 그래프의 이전 정점에서 방문했다면 B 그래프의 정점을 뺏어서 n번째 정점이 가져오고, 이전 정점은 다시 자신이 방문할 수 있는 B 그래프의 정점을 찾는다... 플로이드 와샬 알고리즘(Floyd-Warshall Algorithm) 1. 개념 정점 V개가 있고, 거리가 모두 주어져 있을 때 단 한 번의 시행으로 모든 정점 쌍 사이의 거리를 모두 구하는 알고리즘이다. 음의 가중치가 있는 간선 그래프에서도 사용이 가능한 것이 특징이다. 2. 구현 플로이드 알고리즘은 전형적인 3중 for문의 형태를 하고 있고, 시간 복잡도가 O(n^3)이다. 각 정점 a, b 쌍에 대해서 a에서 b로 가는 최단 경로를 한 번에 다 구해야하므로 2차원 배열 ary를 준비한다. 초기값은 자기 자신에게 가는 ary[i][i] = 0 , 나머지는 ary[i][j] = ∞ 로 초기화한다. 그리고 간선 정보를 받은 후에 a->b로 가는 거리가 w라면 ary[a][b] = w로 갱신한다. 만약 a->b로 가는 거리가 여러 개라면 그 중 가장 작은 값을 사용한다. 플.. 이전 1 2 3 다음