본문 바로가기

Algorithm

 (24)
String Matching (2) - KMP 알고리즘 KMP algorithm navie string matcher를 다시 생각해보면, 위의 사진 같이 앞에 5개의 문자는 일치하지만 마지막 6번째 문자가 달라서 같지 않다고 나오는 경우, 앞에 5개의 문자는 일치한다는 정보를 버리고 한칸을 shift하고 처음부터 다시 비교하게 된다. KMP알고리즘은 앞에 5개는 일치한다라는 정보를 저장하여 더욱 효율적으로 검색한다는 메인 아이디어로 시작한다. 설계 패턴 자체를 비교하여 필요한 정보를 미리 계산할 수 있습니다. 전체 문자열은 같지 않지만 부분문자열은 같은 경우, 얼마만큼 비교를 skip할 수 있을지 정보를 제공해주는 함수입니다. 위 예시의 경우 ababa까지 일치하였고 앞뒤로 ababa / ababa 3개의 문자가 일치하고 2개의 문자가 일치하지 않으므로 2칸..
String Matching (1) - Navie, Rabin-Karp 알고리즘 String Matching Notation & Terminology T [1 .. n]: n개의 문자의 텍스트 P [1 .. m]: m개의 문자의 패턴 1≤ j ≤m에 대해 T[s+j] = p[j]인 경우 T에서 시프트 s와 함께 P가 발생합니다. P가 T의 시프트 s와 함께 발생하면 s를 유효한 시프트라고 합니다. 그렇지 않으면 잘못된 시프트입니다. Navie algorithm 패턴을 한칸을 옮기며 텍스트가 끝날 때 까지 비교해 보는 방식 의사코드 Navie-String-Matching (T, P) n > P; int n = T.length(); int m = P.length(); for (int s = 0; s < n-m; s++) { int count = 0; for (int i = 0; i < ..
슬라이딩 윈도우 알고리즘 슬라이딩 윈도우 배열이나 리스트의 요소의 일정 범위의 값을 비교할때 사용하면 유용한 알고리즘이다. 예를들어 정수로 이루어진 배열 [4, 25, 64, 1, 23, 2, -10, 3, 2] 에서 길이가 3인 서브배열의 합계가 가장 큰 서브배열은 무엇인가? 같은 문제에서 사용될 수 있다. 설계 하나씩 다 더해보면 아래와 같다. 서브 배열 합계 체크 (브루트 포스) #include #include using namespace std; int main() { int n, k; cin >> n >> k; vector v; for (int i = 0; i > input; v.push_back(input); } int sum, max = -1; for (int i =..
투 포인터 알고리즘 Two pointer 어떤 특정 조건을 만족하는 연속 구간을 구할 때 $ O(N) $ 으로 풀 수 있도록 도와주는 알고리즘 리스트에 순차적으로 접근해야 할 때 두 개의 점의 위치를 기록하면서 처리하는 알고리즘 정렬되어있는 두 리스트의 합집합에도 사용됨. 병합정렬(merge sort)의 counquer 영역의 기초가 되기도 합니다. 2 개의 포인터를 사용하여 구간의 길이를 가변적으로 잡아가며 특정 조건을 만족하는 구간을 찾는다. 모든 연속 구간을 잡는다면 $ O(N^2)$ 이 될 것이지만 투 포인터 알고리즘을 사용하면 O(N) 의 시간복잡도로 풀 수 있다. 두 포인터 각각 N번 움직이기 때문에 N + N = 2N 번의 연산이 있는 셈이다. 즉, $ O(2N) = O(N) $ 이 된다. (중요) : 항상 e..
MST (최소 신장 트리) MST (Minimum Spanning Trees) 선수지식: Disjoint-set, union-find 신장 트리란? : 그래프 내의 모든 정점을 포함하는 트리 최소 신장 트리 문제 : Connected, Undirected, Weighted 그래프에서 가중치가 가장 적게 신장 트리를 만드는 문제 N개의 정점을 모두 포함하며 (Connected) Cycle이 없게 하려면 필요한 간선의 최소 갯수는 N-1개이다. 모델 설계, 의사코드 GENERIC-MST(G, w) { // G: graph, w: weight // 아무 간선도 없는 빈 트리 A를 하나 만든다. Tree A = null; // A에 safe한 간선을 한 개씩 추가함으로서 MST를 구성한다. while (A != a spanning tre..
이항계수 알고리즘 이항계수 이항계수란 n개의 원소에서 k개의 원소를 뽑아내는 경우의 수를 의미하며, 공식은 다음과 같다. $ \binom{n}{k} = \left\{\begin{matrix} \frac{n!}{k!(n-k)!} & (0\leq k \leq n) \\ 0& (kn) \end{matrix}\right. $ 혹은 $ _nC_k $ 로 나타낸다. 이항계수를 구하기 위한 알고리즘은 여러 종류가 있는데, 이중 몇가지를 정리하겠다. 이항계수의 성질 $ 1. \binom{n}{k} = \binom{n}{n-k} \\ 2. \binom{n}{k} = \binom{n-1}{k} + \binom{n-1}{k-1} \\ 3. \sum_{k=0}^n \binom{n}{k} = 2^n $ 1. 팩토리얼-재귀 방법 $ \binom{..
[STL] Algorithm header STL - algorithm PS에 자주 쓰이는 #include 헤더파일에서 메소드들을 정리해보았습니다. 1. prev_permutation, next_permutation 벡터, 어레이, 리스트 등으로 이루어진 수열을 순열로 취급하여 이전 순열 혹은 다음 순열을 보여준다. 사용법: next_permutation(Iterator first, Iterator last) 시간복잡도: $ O(N) $ return type: boolean, 다음 순열이 없으면 false, 있으면 true를 반환한다. 예제 코드 #include #include #include using namespace std; int main () { int myInts[] = { 1, 2, 3 }; vector myInt (myInts, m..
소수 판별 소수 찾기 소수 (Prime number): 어떤 자연수 N에 대하여 1과 N으로 밖에 나누어 떨어지지 않는 수 1. 소수의 성질을 이용한 구현 bool isPrime (int N) { for (int i = 2; i*i < N; i++) { if (N % i == 0) return false; } return true; } N이 소수인지 판별하기 위해서는 N-1까지 모두 나눠볼 필요 없이 $ \sqrt(N) $ 까지만 나눠보면 된다. 왜 why? $ N $이 만약 합성수라면 $ p*q $로 표현이 되기 때문에 두 수 중 한개는 항상 $ \sqrt(N) $ 이하, 다른 한 수는 항상 $ \sqrt(N) $ 이상이기에 $ i < N $ 까지 순회하지 않고, $ i \leq \sqrt(N) $까지 순회해도 ..

티스토리툴바