넘치게 채우기

기본적인 브루트 포스 방법은 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..

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

https://leetcode.com/problems/extra-characters-in-a-string/description/?envType=daily-question&envId=2024-09-23leetcode - Extra Characters in a String문제 유형 : 문자열 처리, 재귀, dp문제 난이도 : Medium 문제You are given a 0-indexed string s and a dictionary of words dictionary. You have to break s into one or more non-overlapping substrings such that each substring is present in dictionary. There may be some ex..

설명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://leetcode.com/problems/path-with-maximum-probability/description/?envType=daily-question&envId=2024-08-27leetcode - Path with Maximum Probability문제 유형 : 최단거리, 다익스트라, bfs, 우선순위 큐, 그래프문제 난이도 : Medium 문제You are given an undirected weighted graph of n nodes (0-indexed), represented by an edge list where edges[i] = [a, b] is an undirected edge connecting the nodes a and b with a probability of..

https://leetcode.com/problems/strange-printer/description/?envType=daily-question&envId=2024-08-21leetcode - Strange Printer문제 유형 : 문자열 처리, 재귀, 다이나믹 프로그래밍, 투 포인터문제 난이도 : Hard 문제There is a strange printer with the following two special properties:The printer can only print a sequence of the same character each time.At each turn, the printer can print new characters starting from and ending at any..

https://leetcode.com/problems/magnetic-force-between-two-balls/description/leetcode - Magnetic Force Between Two Balls문제 유형 : 이진 탐색문제 난이도 : Medium 문제In the universe Earth C-137, Rick discovered a special form of magnetic force between two balls if they are put in his new invented basket. Rick has n empty baskets, the ith basket is at position[i], Morty has m balls and needs to distribute the bal..