윈도우 API는 프로세스 생성을 위한 여러 함수를 제공한다. 프로세스를 생성하는 프로세스와 동일한 접근 토큰으로 프로세스의 생성을 시도하는 CreateProcess 다른 토큰이 필요한 경우 사용하는 CreateProcessAsUser 이외 CreateProcessWithToken, CreateProcessAsL...

상호 배타적인 집합을 효율적으로 표현하기 위한 자료구조?이다. 서로 다른 두 개의 집합을 병합하는 union_find + 원소가 어떤 집합에 속해 있는지 판단하는 find로 구성된다. parent 배열에는 각 원소의 최상위 부모를 표현한다. Basic find 함수 int find(int parent[], int k) { ...

에라토스테네스의 체는 고대 그리스의 수학자 에라토스테네스가 만들어 낸 소수를 찾는 방법으로, 체로 치듯이 수를 걸러낸다고 하여 ‘에라토스테네스의 체’라고 부른다. 방법 1부터 원하는 숫자 범위까지 숫자를 쓴다. 소수도 합성수도 아닌 1을 지운다. 다음에 만나는 2를 제외한 2의 모든 배수들을 지운다. 4,6,8,… 다음에 만나는 3...

일반적인 큐는 연산의 결과로 먼저 들어간 데이터가 먼저 나오는 선입선출 구조이지만, 우선순위 큐는 들어간 순서에 상관없이 우선순위가 높은 데이터가 먼저 나온다. 두 가지 연산을 가진다. enqueue: 우선순위 큐에 데이터를 삽입하는 행위 dequeue: 우선순위 큐에서 데이터를 꺼내는 행위 배열로 ...

피보나치 수를 K로 나눈 나머지는 항상 주기를 갖는다. 주기의 길이를 P라고 하면, N번째 피보나치를 M으로 나눈 나머지는 N%P번째 피보나치 수를 M으로 나눈 것과 같다. 주기는 \( M=10^k (k>2) \)일 때 항상 \( 15*10^{k-1} \) 이다. \( n(n\le1,000,000,000,000,000,0...

오일러의 체는 에라토스테네스의 체를 개선한 것으로, N 이하의 소수를 O(N)만에 찾고, N 이하의 자연수 소인수분해를 O(logN)에 할 수 있다. 개념 소수가 아닌 수를 합성수라고 한다. 에라토스테네스의 체 구현에서 합성수는 두 번 이상 검사되므로 시간이 더 소모된다. 합성수는 x = i * prime 으로 나타낼 수 있다. 이때 i는...

어떤 임의의 수열이 주어질 때, 이 수열에서 몇 개의 수를 제거하여 부분 수열을 만들 수 있다. 이때 만들어진 부분 수열 중 오름차순으로 정렬된 가장 긴 수열을 가장 긴 증가하는 부분 수열(LIS)라고 한다. \( O(N^2) \) 알고리즘 배열의 i번째 값으로 끝나는 가장 긴 증가하는 부분 수열의 길이를 dp[i]에 저장한다. dp[i]...

최소 공통 조상(LCA; Lowest Common Ancestor) 문제는 두 노드의 공통된 조상 중에서 가장 가까운 조상을 찾는 문제이다. 방법 모든 노드에 대한 깊이(depth)를 계산한다. 이는 DFS로 구현한다. 최소 공통 조상을 찾을 두 노드를 확인한다. 먼저 두 노드의 깊이가...

다익스트라 알고리즘(Dijkstra Algorithm)은 한 정점으로부터 다른 모든 정점으로의 최단 경로를 구하는 알고리즘이다.

백트래킹은 여러 후보해 중 특정 조건을 충족시키는 모든 해를 찾는 알고리즘이다. 후보해는 해가 될 수 있는 가능성을 가진 부분해의 조합이다. 해를 찾는 비용을 줄이기 위해 방문할 노드의 수를 최소화하는 것이 중요하다. 이는 보통 DFS로 구현된다. 과정 해를 찾아가는 과정은 뿌리부터 출발한다. ...