a번째 수 부터 b번째 수 까지의 합 구하기 7개의 수 1, 10, 3, 6, 5, 6, 4가 있을 때 a번째 수 부터 b번째 수 까지의 합을 구하는 상황을 생각해봅시다. 2번째 수 부터 4번째 수 까지의 합을 구하라는 질의가 들어오면 10+3+6 = 19 2번째 수 부터 7번째 수 까지의 합을 구하라는 질의가 들어오면 10+3+6+5+6+4 = 34 처럼 a번째 수에서 b번째 수까지를 순회하면서 합을 구하면 됩니다. 이와 같은 방법으로 a번째 수 부터 b번째 수까지의 합을 구하면 숫자의 개수가 N개, 질의의 개수가 M개일 때 M개의 질의 각각에 대해 최대 N번 순회해야하므로 시간복잡도는 O(NM)이 됩니다. 이 보다 더 빠르게 할 수 있을까요? 다음과 같이 배열을 sum을 정의합시다. sum[i] = ..
Articulation Point : 단절점 앞으로의 논의는 하나의 컴포넌트(connected component)로 구성된 무방향 그래프에 대해서 진행됩니다. 먼저 아래 무방향 그래프에서 단절점(절단점)을 파란색 테두리로 나타내었습니다. 그림을 보고 직관적으로 알 수 있듯이 단절점은 그 정점을 제거했을 때 그래프가 두개 이상으로 나누어지는 정점을 말합니다. 즉 제거했을 때 그래프의 connected component가 증가하는 정점을 말합니다. 그럼 어떻게 이 단절점을 찾을 수 있을까요? 가장 단순하게 생각해보면 점을 하나씩 없애보고 컴포넌트가 둘로 나눠졌는지 조사하는 것입니다. N : 정점의 개수, M : 간선의 개수라 할때 이 방법의 시간 복잡도는 없앨 정점을 선택하는데 N, 그래프 전체를 dfs탐색..
Lucas Theorem : 뤼카 정리는 음이 아닌 정수 n, k 소수 p에 대해 를 구하는 효율적인 계산 방식을 제공하는 정리입니다. 이항계수는 이므로 n과 k가 크면 계산하기가 상당히 부담스럽습니다. 식에 Factiorial이 포함되기 때문에 숫자가 조금만 커져도 int나 long long 자료형에 담을 수 없어 n!과 k!, (n-k)!을 다 계산한 후 나누어주는 방식을 취할 수 없습니다. 따라서 이항 계수를 구할 때 다음 정리를 이용해서 배열에서 파스칼 삼각형을 구성하거나 메모제이션방식으로 얻게 됩니다. 그러나 위 방식으로 다음 문제처럼 (M은 소수) n이 매우 큰 문제에 대해 접근하면 엄청난 메모리 사용과 연산량으로 인해 해결할 수 없습니다. 위 문제는 뤼카의 정리를 이용해서 해결할 수 있습니다..
다음과 같이 어떤 방향 그래프가 주어졌을 때그래프를 깊이 우선 탐색하면서 따라가는 간선들만 모으면 트리 형태를 띠게 됩니다. 0번 정점에서 dfs함수를 호출해서 dfs함수가 따라가는 간선들을 오렌지 색으로 나타내고 각 정점의 방문 순서를 괄호로 표시했습니다. 이런 트리를 주어진 그래프의 DFS 스패닝 트리(DFS Spanning Tree)라고 합니다. 그래프의 DFS 스패닝 트리를 생성하고 나면 그래프의 모든 간선을 네가지 중 하나로 분류할 수 있습니다. 1. 트리 간선(tree edge) : 스패닝 트리에 포함된 간선2. 순방향 간선(forward edge) : 스패닝 트레에서 선조에서 자손으로 연결되지만 트리 간선이 아닌 간선3. 역방향 간선(backward edge) : 스패닝트리에서 자손에서 선조..
- Total
- Today
- Yesterday