넘치게 채우기

세그먼트 트리References:https://youtu.be/-dUiRtJ8ot0?si=SRjeBHChrzUaN-id  세그먼트 트리란, 1차원 배열에서의 구간 연산에 대해 빠르게 구하는 자료구조이다.구간 [l, r]에 대해서 기존의 naive하게 업데이트 및 연산하는 것은 O(N)의 시간이 걸리지만,세그먼트 트리를 이용하면 O(log N)의 시간이 걸린다. 세그먼트 트리는 트리이지만, 배열 기반의 이진트리로 간단하게 표현될 수 있다.이진트리의 특성상, 0-based의 기준, 인덱스 i 노드의 왼쪽 자식은 i*2+1, 오른쪽 자식은 i*2+2에 위치한다.1-based의 기준, i노드의 왼쪽 자식은 i*2, 오른쪽 자식은 i*2+1이다. 세그먼트 트리에서,루트 노드는 모든 구간에 대한 연산 결과를 저장한..

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

스택은 LIFO, 큐는 FIFO 자료구조이다. 어떻게 하면 두 개의 스택으로 하나의 큐를 구현하는데, 대부분의 경우에서 O(1)으로 구현할 수 있을까? 하나를 입력용 스택, 하나를 출력용 스택이라고 해보자. 입력용 스택은 입력만 받는다. 출력용 스택은 출력만 한다. 단, 출력용 스택이 empty인 경우, 입력용 스택의 원소들을 pop하여 출력용 스택에 push하면 된다. 이때 출력용 스택에는 입력의 역순으로 들어오게 되어 기존의 출력 순서가 반대로 되어 FIFO가 된다. 이 경우만 제외하고는, O(1)의 시간복잡도를 가진다. class MyQueue { stack i,o; public: MyQueue() { } void push(int x) { i.push(x); } int pop() { int x; i..

프로그래밍 언어에서 if문을 자주 이용하곤 한다. 아래의 코드에서 어떤 결과가 나올까? def funcA(): print("A") return False def funcB(): print("B") return True if funcA() and funcB(): print("참") else: print("거짓") A B 거짓 A 거짓 거짓 정답은 2번이다. and논리연산을 할 때, 앞의 오퍼랜드가 false인 경우, 뒤의 오퍼랜드를 확인하지 않는다. 이 방법을 통해서 더 간결하고 가독성이 좋은 코딩을 할 수 있다. 반대로, or의 경우도 그렇다. or논리연산을 할 때, 앞의 오퍼랜드가 true인 경우, 뒤의 오퍼랜드를 확인하지 않는다. 실제 사용 예시: 알고리즘 문제풀이에서 슬라이딩 윈도우를 구현할 때 L..

#include int countOnesInDecimal(int n) { int count = 0; while (n) { std::cout