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