분류 전체보기 (49) 썸네일형 리스트형 투 포인터 알고리즘 Two pointer 어떤 특정 조건을 만족하는 연속 구간을 구할 때 $ O(N) $ 으로 풀 수 있도록 도와주는 알고리즘 리스트에 순차적으로 접근해야 할 때 두 개의 점의 위치를 기록하면서 처리하는 알고리즘 정렬되어있는 두 리스트의 합집합에도 사용됨. 병합정렬(merge sort)의 counquer 영역의 기초가 되기도 합니다. 2 개의 포인터를 사용하여 구간의 길이를 가변적으로 잡아가며 특정 조건을 만족하는 구간을 찾는다. 모든 연속 구간을 잡는다면 $ O(N^2)$ 이 될 것이지만 투 포인터 알고리즘을 사용하면 O(N) 의 시간복잡도로 풀 수 있다. 두 포인터 각각 N번 움직이기 때문에 N + N = 2N 번의 연산이 있는 셈이다. 즉, $ O(2N) = O(N) $ 이 된다. (중요) : 항상 e.. MST (최소 신장 트리) MST (Minimum Spanning Trees) 선수지식: Disjoint-set, union-find 신장 트리란? : 그래프 내의 모든 정점을 포함하는 트리 최소 신장 트리 문제 : Connected, Undirected, Weighted 그래프에서 가중치가 가장 적게 신장 트리를 만드는 문제 N개의 정점을 모두 포함하며 (Connected) Cycle이 없게 하려면 필요한 간선의 최소 갯수는 N-1개이다. 모델 설계, 의사코드 GENERIC-MST(G, w) { // G: graph, w: weight // 아무 간선도 없는 빈 트리 A를 하나 만든다. Tree A = null; // A에 safe한 간선을 한 개씩 추가함으로서 MST를 구성한다. while (A != a spanning tre.. 이항계수 알고리즘 이항계수 이항계수란 n개의 원소에서 k개의 원소를 뽑아내는 경우의 수를 의미하며, 공식은 다음과 같다. $ \binom{n}{k} = \left\{\begin{matrix} \frac{n!}{k!(n-k)!} & (0\leq k \leq n) \\ 0& (kn) \end{matrix}\right. $ 혹은 $ _nC_k $ 로 나타낸다. 이항계수를 구하기 위한 알고리즘은 여러 종류가 있는데, 이중 몇가지를 정리하겠다. 이항계수의 성질 $ 1. \binom{n}{k} = \binom{n}{n-k} \\ 2. \binom{n}{k} = \binom{n-1}{k} + \binom{n-1}{k-1} \\ 3. \sum_{k=0}^n \binom{n}{k} = 2^n $ 1. 팩토리얼-재귀 방법 $ \binom{.. [STL] Algorithm header STL - algorithm PS에 자주 쓰이는 #include 헤더파일에서 메소드들을 정리해보았습니다. 1. prev_permutation, next_permutation 벡터, 어레이, 리스트 등으로 이루어진 수열을 순열로 취급하여 이전 순열 혹은 다음 순열을 보여준다. 사용법: next_permutation(Iterator first, Iterator last) 시간복잡도: $ O(N) $ return type: boolean, 다음 순열이 없으면 false, 있으면 true를 반환한다. 예제 코드 #include #include #include using namespace std; int main () { int myInts[] = { 1, 2, 3 }; vector myInt (myInts, m.. 소수 판별 소수 찾기 소수 (Prime number): 어떤 자연수 N에 대하여 1과 N으로 밖에 나누어 떨어지지 않는 수 1. 소수의 성질을 이용한 구현 bool isPrime (int N) { for (int i = 2; i*i < N; i++) { if (N % i == 0) return false; } return true; } N이 소수인지 판별하기 위해서는 N-1까지 모두 나눠볼 필요 없이 $ \sqrt(N) $ 까지만 나눠보면 된다. 왜 why? $ N $이 만약 합성수라면 $ p*q $로 표현이 되기 때문에 두 수 중 한개는 항상 $ \sqrt(N) $ 이하, 다른 한 수는 항상 $ \sqrt(N) $ 이상이기에 $ i < N $ 까지 순회하지 않고, $ i \leq \sqrt(N) $까지 순회해도 .. 순열과 조합 순열 $ _nP_r : \frac{n!}{(n-r)!} $ 서로 다른 원소를 가진 집합에서 대상들을 선택하여 순서 있게 배열하는 것 설계 단순히 $ _nP_r $ 을 구하고 싶다면 위의 공식을 이용해서 코드를 짜면 된다. 다만 유의할 점은 팩토리얼은 n이 조금만 커져도 수가 매우 커지기 때문에 위의 식 그대로 보다는 정리된 식을 사용하는 것이 효율적이다. long long permutation (int n, int r) { long long result = 1; for (int i = n; i > n-r; i--) { result *= i; } return result; } 혹은 재귀로 나타낼 수도 있다. long long permutation (int n, int r) { if (r == 0) retu.. 16. 그래프 탐색 (2) - DFS DFS (Depth-First Search) 개요 설계 모델 BFS와 같이 색깔로 정점의 상태를 구별해 보자. White: discover되지 않은 상태 즉, 처음에 모든 정점은 white 상태이다. Gray: discover는 되었지만 정점에 대해서 탐색이 끝나지 않은 상태 = Gray 정점의 인접 정점들 중 최소 한개는 white 정점인 상태 Black: discover되고 해당 정점에 대해 모든 탐색이 끝난 상태 = Black 정점의 인접 정점들은 모두 Gray 혹은 Black 상태일 것이다. DFS에서 Gray 정점은 약간 BFS와 다른데, 각 Gray 정점에서 2개의 타임스탬프를 가진다. d[v]: 정점 v의 discovery time f[v]: 정점 v의 finish time (방문할 수 있는.. 15. 그래프 탐색 (1) - BFS 그래프 탐색 그래프 탐색: 하나의 정점으로부터 시작하여 차례대로 모든 정점들을 한 번씩 방문하는 것 그래프 탐색은 크게 두가지 방법이 있다. BFS (Breadth-First Search, 너비우선탐색) 개요 한 시작 정점을 정해서 인접한 정점부터 모두 탐색하는 방식이다. 설계 모델 정의 Discover: 정점을 처음 방문한다. Explore: 간선을 처음 이용한다. 정점의 구분 White: discover되지 않은 상태 즉, 처음에 모든 정점은 white 상태이다. Gray: discover는 되었지만 정점에 대해서 Explore가 끝나지 않은 상태 = Gray 정점의 인접 정점들 중 최소 한개는 white 정점인 상태 Black: discover되고 해당 정점에 대해 모든 Explore가 끝난 상태 .. 이전 1 2 3 4 5 6 7 다음