넘치게 채우기

기본적인 브루트 포스 방법은 O(2^n)이 걸린다.그래서, n=20인 경우에만 시간 효율적으로 사용할 수 있다. 개선해서, n MITM, Meet-in-the-Middle알고리즘이다. n길이의 배열 arr이 주어지고, 합이 s인 부분배열의 개수를 구한다고 해보자. 핵심 아이디어는 다음과 같다:배열을 절반으로 나눠서, 각각 브루트 포스로 모든 조합을 구한다. 각각 left, right라 한다.이진탐색을 이용할 것이기에, right를 정렬해준다.  left의 조합들에서 각각 right에서  target = s-leftsum값에 대해 upper_bound(target보다 초과인 큰 요소의 첫 인덱스), lower_bound(target이상인 요소의 첫 인덱스)를 구해서 upper_bound - lower_bo..

O(nlogn)으로 LIS의 길이를 구하는 가장 간단한 코드는 다음과 같다:#include using namespace std;int main(int argc, char *argv[]) { arr = {10, 9, 2, 5, 3, 7, 101, 18}; vector lis; for (int i = 0; i 그러나 이는 길이만 구할 뿐, 순서가 뒤섞여서 실제 LIS는 아니다. 아래 코드는 실제 LIS를 구하는 가장 빠른 코드이다.#include using namespace std;vector findLIS(const vector &nums) { if (nums.empty()) return {}; int n = nums.size(); vector tails; vector tails_indi..

오일러 경로와 오일러 회로오일러 경로는 그래프에서의 모든 간선을 단 한번씩만 통과하는 경로이다.오일러 경로의 출발점과 종료점의 구분이 없다면, 오일러 회로이다. 오일러 경로는 다음의 특징을 가진다:무방향 그래프인 경우, 두 노드를 제외한 모든 노드가 짝수 개의 차수를 가진다. 두 노드는 홀수 개의 차수를 가진다.어디서든 순회를 시작해도 오일러 경로이다.방향 그래프인 경우, 두 노드를 제외한 모든 노드가 같은 진출차수 및 진입차수를 가진다. 두 노드는 진출차수가 하나 더 많은 노드 하나와, 진입차수가 하나 더 많은 노드로 루성된다.진출차수가 하나 더 많은 노드가 출발점이고, 진입차수가 하나 더 많은 노드가 도착점이다. 오일러 회로는 다음의 특징을 가진다:무방향 그래프인 경우, 모든 정점의 차수가 짝수이다...

설명Knuth, Morris, Pertt이 만든 문자열 패턴 검색 알고리즘인 KMP 알고리즘은O(n+m)에 문자열 패턴을 검색해낼 수 있다. 이 알고리즘의 핵심은 lps 배열이다.lps = Longest Prefix Suffix.각 위치까지의 부분 문자열에서 자기 자신의 접두사이면서 접미사인 가장 긴 길이를 저장한 배열이다.패턴 내에서 일치하지 않는 문자가 발견되면, 이전에 계산한 lps를 이용하여 패턴을 적절히 이동한다.lps[i]는 0부터 i-1까지는   LPS 배열의 생성방법은 다음과 같다:lps[0]와 len을 0으로 초기화한다. len은 가장 긴 접두사와 접미사 값의 길이이다.pat[len]과 pat[i]가 일치하면, len을 1 증가하고, 증가된 값을 lps[i]에 할당한다.일치하지 않고 le..

설명Naive 패턴 검색에서는, 우리는 모든 pattern의 길이와 같은 부분문자열들을 원본 문자열에서 추출해서 각각 한 글자씩 비교했다. Rabin-Karp 알고리즘에서도, 모든 부분문자열을 검사하지만, 대신 패턴의 해시 값와 현재 부분문자열의 해시 값을 비교한다.그리고 해시 값이 매칭되면, 패턴이 맞는 것이다.Rabin-Karp 알고리즘은 다음의 해시 값들을 계산할 필요가 있다:패턴의 해시 값더미 문자열(haystack)에서의 길이가 m인 모든 부분문자열해시 값은 문자열에서 패턴을 찾는 데 효율적으로 사용된다.해시 값은 rolling hash function으로 계산되는데, 기존의 글자를 하나 버리고 새 글자를 가져오면서 해시 값을 업데이트하면 된다.롤링 해시 함수의 과정은 다음과 같다:기저 수 b와..

설명Naive 패턴 검색 알고리즘은, 문자열에서 패턴을 찾는 가장 단순한 방법이다.패턴을 텍스트 위로 하나씩 밀어서 일치하는지 확인하고, 일치하는 것이 발견되면, 1개씩 다시 밀어서 다음에 일치하는 항목을 확인한다. 코드(C++)#include #include using namespace std;void search(string &pat, string &txt) { int M = pat.size(); int N = txt.size(); for (int i = 0; i   Example 1: pattern found at: 0pattern found at: 9pattern found at: 12Example 2: pattern found at: 1  복잡도 분석시간 복잡도: O(n * m)..

https://www.geeksforgeeks.org/introduction-to-disjoint-set-data-structure-or-union-find-algorithm/ Introduction to Disjoint Set (Union-Find Algorithm) - GeeksforGeeks A Computer Science portal for geeks. It contains well written, well thought and well explained computer science and programming articles, quizzes and practice/competitive programming/company interview Questions. www.geeksforgeeks.o..

벨만-포드 알고리즘이란? 한 노드에서 다른 노드까지의 최단 거리를 구하는 알고리즘이다. 다익스트라 알고리즘과의 비교 다익스트라 알고리즘은 양수일 때에만 사용이 가능하지만, 벨만포드 알고리즘은 음수에서도 사용이 가능하다. 시간 복잡도는 다익스트라 알고리즘이 더 효율적이다. 벨만포드 알고리즘 1. 시작 노드를 설정한다. 2. 시작 노드를 제외한 모든 노드의 거리를 INF로 구성한다. 3. 현재 노드의 모든 인접 노드를 탐색하며 기존의 연결 관계보다 현재 노드를 거치고 가는 것이 더 짧을 경우 갱신한다. 4. 모든 노드에 대해 반복한다. 5. 모든 노드에 대해 반복하고 나서도 갱신된다면, 그건 음수 사이클이 존재한다는 의미이다. 벨만포드 알고리즘 예시 1.노드 A에서부터 시작한다. 2 < INF, 4 < IN..

순서가 정해져 있는 일련의 알고리즘을 수행해야 할 때 사용되는 알고리즘이다. '사이클이 없는 방향 그래프의 모든 노드를 순서대로 나열하는 것' 이다. 대표적으로 선수학습 과목 등의 예시가 있다. 진입차수와 진출차수 진입차수(indegree): 특정 노드로 들어오는 간선의 개수(노드로 오기 전의 조건) 진출차수(outdegree): 특정 노드에서 나가는 간선의 개수 위상 정렬 알고리즘 1. 진입차수가 0인 노드를 큐에 넣는다. 2. 큐가 빌 때까지 다음의 과정 반복: 큐에서 원소를 꺼내서 그 노드가 향하는 노드의 진입차수를 1 낮추기(그 간선 방문처리) 진입차수가 0이 된 노드를 큐에 넣기 위상 정렬 알고리즘의 예시 1. 진입차수가 0인 노드부터 큐에 넣고 시작한다. 큐에서 요소를 하나 꺼낸다. 꺼내진 요..

컴퓨터는 이진수를 사용한다. 비트 연산을 통해서 우리는 더 빠른 연산을 할 수 있다. 비트마스킹의 장점 1. 빠른 연산 - 비트마스킹 연산은 상수 시간에 연산된다. 2. 간결한 코드 - 비트마스킹을 통해 간결한 코드 표현이 가능하다. 3. 적은 메모리 사용 - 큰 크기의 숫자를 적은 메모리로 표현이 가능하다. 비트 연산들 and(&) 둘 다 참일 때에만 1 반환 ex) 1010 & 1111 = 1010 or(|) 둘 중 하나만 참일 때 1 반환 ex) 1000 | 1101 = 1101 xor(^) 둘이 서로 다를 때 1반환 ex) 1010 ^ 1111 = 0101 not(~) 반대 값을 반환 ex) ~1010 = 0101 시프트 연산() 비트 자릿수를 옮김. 001101