정리/알고리즘 (15) 썸네일형 리스트형 [알고리즘] 정점 선인장 https://www.acmicpc.net/problem/10891 정점 선인장의 정의에 대해서는 해당 문제에 나와있습니다. 이중 연결 요소를 이용합니다. 그래프의 모든 정점을 이중 연결 요소로 묶어버리면 3가지 유형으로 구분할 수 있습니다. 정점이 두 개인 BCC (단절선) 단순 사이클 단순 사이클이 아닌 사이클 우선 단절선은 단순 사이클에 해당되지 않으므로 무시해주면 됩니다. edge가 한 개 담긴 이중 연결 요소를 만나면 continue하는 식으로 구현하면 됩니다. 단순 사이클의 경우, 문제에서 나온 것처럼 하나까지만 허용해 줍시다. 사이클이면서 단순 사이클이 아닌 경우, 존재만으로 선인장을 만들 수 없습니다. 단순 사이클은 정점의 개수와 간선의 개수가 같다는 특징이 있습니다. 위의 그림에서도 간선.. [알고리즘] 이분매칭 [알고리즘 소개] 이분 그래프에서 최대 매칭을 구하는 알고리즘 [코딩 방법] A, B그룹이 어디에 매칭됐는지를 기록할 A[i], B[i], dfs마다 쓸 visited[i], 인접그래프 2차원 배열 adj (A는 안 쓰는 경우가 많음) 인접그래프를 채워주고 A그룹의 모든 정점들에 대해 dfs를 시작. 시작 전에 visited는 전부 false로 초기화 재귀에 들어오면 먼저 visited[cur]을 true로 변환 cur의 모든 인접한 정점인 next에 대해 if (B[next] == -1 || !visited[B[next]] && dfs(B[next])이면 B[next] = cur, A[cur] = next로 바꾸고 true반환 그렇지 않다면 false반환. 재귀를 마치고 true가 돌아왔으면 매칭 성공.. [알고리즘] 쾨닉의 정리 (Kőnig's theorem) (최소 정점 커버) = (최대 매칭) [최소 정점 커버] 위 그림처럼 정점에 색칠을 하면 인접한 간선들이 색칠될 때, 최소한의 정점만 색칠하여 모든 간선을 색칠하는 것. [쾨닉의 정리] https://kangwlgns.tistory.com/120 위 링크에서 상어의 저녁식사를 푸는 스킬에 대해 설명했었습니다. 쾨닉의 정리에서도 해당 스킬을 사용한다고 볼 수 있습니다. 위 링크에 자세한 설명을 적었지만 여기서 간단하게 설명하자면, 우선 이분 매칭으로 최대 매칭을 구하고, 후에 생각을 끼워 맞추는 겁니다. 최소 정점 커버에 사용한 것과 같은 그래프입니다. 위 그래프를 최대 매칭하면 위 그림과 같습니다. (다르게 나올 수도 있습니다.) 최소 정점 커버가 최소한의 정점만 색칠하여 간선을 색칠하는 것이라고 했었습.. [알고리즘] 마나허 (Manacher) [알고리즘 소개] 전체 문자열에서 회문의 개수 및 길이를 구하는 알고리즘 [코딩 방법] 현재 시점에서 최대 길이 회문의 인덱스 c, 최대 길이 회문의 최고 인덱스 r, 그리고 i번째를 중심으로 하는 회문의 반지름 P[i] 짝수 회문도 검사하기 위해 문자열 사이사이에 문자 삽입 (ex. abcde → #a#b#c#d#e#) 반복문을 돌면서 i > r 이라면 P[i] = 0, else라면 가장 긴 회문 안에 현재 인덱스가 들어 있는 것이므로 대칭인 P'[i]( = P[2 * c - i] )에 대해 P[i] == P'[i]임이 보장됨. 즉, P[i] = P'[i]가 되어야 하지만, r안에 들어와 있어야만 P[i] == P'[i]가 보장되므로 P[i] = min(P'[i], r - i) P[i]의 초기값을 빠르.. [알고리즘] KMP [알고리즘 소개] 전체 문자열에서 부분 문자열을 효율적으로 찾는 알고리즘. [코딩 방법 - 실패 함수] 실패 테이블 만들기. table[i]는 0부터 i까지에서 접두사, 접미사가 겹치는 최대 길이 부분 문자열 pattern을 1부터 N까지 for문으로 순회, j는 0에서 시작 j > 0 이거나 pattern[i] != pattern[j]이면 j = table[j - 1] 반복 (이전까지 계속 맞았다면 table[j - 1]에는 0이 아닌 값이 들어 있을 것이고 접미사 부분까지 맞았음이 확인됐으므로 처음부터 다시 비교할 필요가 없이 접미사와 같았던 접두사 부분까지는 생략하고 확인 가능) pattern[i] == pattern[j] 이면 table[i] = ++j [코딩 방법 - KMP] 전체 문자열 par.. [알고리즘] 이분 탐색 (Binary Search) [알고리즘 소개] 배열 내에서 특정 요소 k를 $O(logn)$으로 찾는 알고리즘. [알고리즘 특징] 배열을 미리 정렬 해야 함. [코딩 방법] 배열 arr을 정렬. 결과 인덱스 idx = N으로 설정(일치하는 값이 없는 경우 lower bound를 출력하기 위함). 최소 인덱스 0부터 최대 인덱스 N - 1까지의 중간값 mid를 구함 left는 0부터, right는 N - 1부터 시작해서 left = k면 idx = mid, right = mid - 1; else left = mid + 1 idx가 lower bound이면서 결과 인덱스가 됨. [응용] k 이상이 처음 나오는 lower bound, k 초과가 처음 나오는 upper bound. 꼭 배열이 아닌 구간에 대해 실행해도 됨. (나무 자르기).. [알고리즘] 크루스칼 (Kruskal) 최소 스패닝 트리 [알고리즘 소개] 정점들과 가중치가 존재하는 간선들이 존재할 때, 해당 간선들을 이용하여 최소 스패닝 트리를 얻을 수 있는 알고리즘. [알고리즘 특징] 그리디 우선 순위 큐 사용 분리 집합 사용 [코딩 방법] 우선 순위 큐와 분리 집합용 배열 생성. 배열의 크기는 정점의 개수 최소 스패닝 트리의 가중치를 저장할 result, 반복문 종료조건을 위한 count 변수 생성 두 정점과 가중치를 저장할 간선 클래스(구조체) 생성 [알고리즘] 뤼카의 정리 (Lucas' Theorem) 정수론, 조합론 [알고리즘 소개] 음이 아닌 정수 n, k와 작은 소수 p에 대해 빠르게 $\dbinom{n}{k} \, mod \; p$를 구하는 알고리즘 [정리 소개] n과 k를 p진법으로 나타낸 표기가 $n = n_mp^m + n_{m-1}p^{m-1} + \cdots + n_1p^1 + n_0$ $k = k_mp^m + k_{m-1}p^{m-1} + \cdots + k_1p^1 + k_0$ 위와 같을 때, $\dbinom{n}{k} \equiv \Pi_{i = 0}^{m} \dbinom{n_i}{k_i} (mod \; p)$ [코딩 방법] 파스칼의 삼각형을 이용하여 $p * p$크기의 배열 dist에 이항 계수를 전부 저장 n과 k를 p진법으로 변환하면서 dist[$n_i$][$k_i$]를 계속 .. 이전 1 2 다음
