정리 (20) 썸네일형 리스트형 [알고리즘] 정점 선인장 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]의 초기값을 빠르.. [자료구조] 트라이 (Trie) 문자열 [자료구조 소개] 문자열을 char단위로 쪼개서 트리에 저장한 자료구조. 문자열 검색에 용이함. [자료구조 특징] 트리 사용. 재귀, 포인터(C++ 사용 시), 트리에 대한 지식 필요 공간, 시간 복잡도를 효율적으로 개선함 (기존의 방식으로 문자열을 찾으려면 문자열 길이 M, 배열 길이 N으로 복잡도가 $O(NM)$, 트라이는 $O(M)$) [코딩 방법] 클래스(구조체) 생성, 현재 노드가 끝인지(문자열이 끝인지) 확인하는 bool타입 변수와 자식노드를 가리킬 객체포인터배열(C++) 혹은 객체배열(Java) 생성. 객체포인터배열은 nullptr(C++) 혹은 null(Java)로 초기화. C++의 경우 동적할당을 사용하므로 자식노드를 삭제할 소멸자도 생성. (!if (child[i]) delete.. [알고리즘] 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.. [자료구조] 트리, 이진 트리 그래프 이론 트리 [자료구조 소개] 정점이 V개일 때 모든 정점이 연결되어 있고 간선이 V - 1개인 그래프. [자료구조 특징] 순환하지 않는 그래프. [코딩 방법] 일반 양방향 그래프와 동일 [응용] 트리 동적 계획법 트라이 변형된 트리들 (이진 트리 등) 이진 트리 [자료구조 소개] 트리와 같으나, 하나의 루트 노드가 있고 자식 노드가 최대 두 개인 트리. [자료구조 특징] 일반 트리와 동일. 자식 노드가 최대 두 개. [코딩 방법] 자식 노드가 최대 두 개이므로 일반 그래프처럼 코딩할 이유가 없음. 보통 이진 트리를 사용하는 경우에는 루트 노드가 핵심이고 재귀를 사용하는 경우. 크기가 V이고 원소로 크기가 2인 배열을 갖는 2차원 배열을 생성하여 좌우 자식 노드를 저장하면 됨. [응용] 변형된 이진.. [알고리즘] 이분 탐색 (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. 꼭 배열이 아닌 구간에 대해 실행해도 됨. (나무 자르기).. 이전 1 2 3 다음
