알고리즘/자료구조
-
모듈러 나눗셈 연산 처리하기알고리즘/자료구조 2016. 12. 10. 12:14
프로그래밍 문제에서 가끔 이런 연산을 요구하는 문제들이 있다. (N/K) % MOD N과 K의 값이 작으면 N과 K의 값을 먼저 계산 하고 나서 모듈러 연산을 취해주면 문제가 없다. 하지만 N과 K값이 64bit 이상으로 변수에 넣을 크기를 초과하는 경우 앞의 나눗셈 계산은 정상적인 값을 내놓지 않을 것이고 모듈러 연산은 정상이 아닌 값을 받아 처리해 결론적으로 잘못된 값을 낸다. 주로 N과 K를 팩토리얼로 받는 조합의 경우의 수를 구할 때 난감하다 -> nCr % MOD 인 경우 이런 경우를 해결 하기 위해 모듈러 연산의 나눗셈을 계산하는 특별한 방법이 존재한다. 모듈러 연산에서 나눗셈 N/K는 K로 나누는 대신에 K의 곱셈 역원(multiple inverse)를 곱하는 방식으로 이뤄진다. 곱셈 역원은..
-
완전순열(교란순열)알고리즘/자료구조 2016. 12. 4. 20:52
어떤 배열의 원소 Xi의 위치가 i라고 할 때 모든 원소들이 자기의 위치에 존재하지 않을 때 이를 완전 순열이라고 한다. X2 X1 X4 X3 점화식을 통해 원소의 개수에 따라 완전순열의 개수를 구할 수 있다. 공식은 다음과 같다 a(n) = (n-1) * (a(n-1) + a(n-2)) 증명을 하면, 1 부터 N까지 오름 차순으로 이뤄진 배열이 있다고 하자 여기서 배열내의 원소중 1의 위치를 X로 옮기려고 한다. 이럴 경우 두가지 경우가 발생한다. - X를 1의 위치로 옮기는 경우 -> N-2의 개수로 완전순열을 구하는 경우와 같다.- X를 1의 위치로 옮기지 않는 경우 -> N-1의 개수로 완전순열을 구하는 경우와 같다. 1이 선택 할 수 있는 X 의 개수는 N-1개 이므로 이를 점화식으로 나타내면 ..
-
LCA(Lowest Common Ancestor)알고리즘/자료구조 2016. 7. 30. 13:24
트리 내부에 있는 두개의 노드 사이의 최저 공통 조상을 효율적으로 찾아주는 자료구조이다. 가장 간단히 생각 할 수 있는 구현방법(모든 모드를 일일히 탐색하는)으로는 최저 공통 조상을 찾는데 O(N)의 시간이 걸리지만 최적화된 LCA 알고리즘으로는 O(logN)시간만에 구할 수 있다. LCA 알고리즘에서 트리의 노드들은 자신의 부모노드에 대한 정보외에 현재 높이에서 2^i 위에 위치한 조상노드에 대한 정보도 가지고 있다.그림으로 표현하면 다음과 같다. (자신의 부모노드 뿐만 아니라 2^i위치에 해당하는 조상노드의 정보를 가지는 것은 빠른 탐색을 할 때 유용하게 쓰인다.) 알고리즘의 절차는 다음과 같다. 1. 두 노드의 depth가 다르다면 depth를 맞춰준다.* 이때 일일히 모든 부모노드를 방문하는 것이..
-
Count sort알고리즘/자료구조 2016. 7. 23. 19:47
quicksort나 mergesort처럼 일반적인 sorting알고리즘은 O(NlogN)을 가지나 sorting에 사용되는 값들을 사전에 알고 있는 경우에는 시간복잡도를 O(N)까지 단축 시킬 수 있다. 그중에서도 가장 강력하게 사용되는 알고리즘이 Count sorting이다. Count sorting은 정렬에 쓰이는 값이 충분히 작은 경우(배열의 최대 크기가 될 수 있는 값보다 작아야 한다)에 주로 사용할 수 있다. 배열의 인덱스는 이미 자동적으로 정렬되있으니 수열에 포함된 값 각각의 개수를 배열의 인덱스에 해당하는 값에 저장해둔 후 그 그 개수를 참고해서 정렬하는 방식이다. 글로 설명하기에는 어려우니 예를 들어보자. 5 3 6 7 4 5 인 수열을 정렬한다고 하자. 위 수열의 각 값의 개수를 관리하는..
-
Segment Tree알고리즘/자료구조 2015. 9. 7. 16:34
옛날에 min max Tree를 공부 할 때 배열 특정 구간 내에서의 최대값과 최소값을 미리 저장해두어 범위가 주어 질 때 O(logN)시간내에 해결 했었는데 이렇게 구간 내의 특정 값을 저장해두는 방식을 Segment Tree라고 하나 보다. 범위가 주어지면 위 배열을 이용해서 해결하면 된다. 만약 3~6사이의 범위에 대해 구하라고 하면 이렇게 풀면 된다. 사실 이건 생각하는 것은 책 한번 보면 어렵지 않은데 이걸 어떻게 구현 할 것인가가 문제이다. 예전에는 이차원 배열 사용하며 메모리 낭비도 심하고 코드도 지저분하게 풀었는데 코드포스에 깔끔한 구현이 있어 참조해본다 void build(int id = 1, int l=0, int r=n){ if(r-l=y)return 0; if(x
-
SQRT Decomposition알고리즘/자료구조 2015. 9. 5. 20:39
만약 알고리즘 문제에서 해당 배열의 특정 구간(L, R)에서 최소값을 구하라는 문제가 나왔다면 가장 일반적으로 생각 할 수 있는 방법은 L, R 구간을 모두 탐색해보는 방법일 것이다. 하지만 테스트 케이스의 개수가 많고 배열의 크기가 크다면 시간이 오래 걸릴 것이다. 여기서 사용 할 수 있는 방법이 sqrt decomposition이다. 크기 N인 배열을 sqrt(N)으로 쪼개서 최소값을 저장하는 배열(sqrt 배열)을 미리 만들어 둔 후 주어진 구간의 최소값 찾을 때는 구간 내에 포함된 sqrt배열에 해당하는 최소값과 그 이외의 부분들의 값을 비교해서 해결 할 수 있다 현재는 최소값을 구하는데 사용했는데 이것 말고도 다양한 정보를 저장하는데 사용 할 수 있을 것 같다
-
LIS를 O(nlogn)시간 내에 해결하는 방법알고리즘/자료구조 2015. 8. 27. 11:13
LIS는 수열 중에서 가장 긴 수열의 길이를 찾는 방법이다. 동적 계획법 해결 방법은 이전에 찾았던 수열의 마지막 값들 중 현재의 위치의 값보다 작으면 그 마지막 값이 가지고 있는 수열의 길이에 1을 더하는 방식이다. 조건에 해당하는 수열 중에서 가장 긴 수열을 선택해야 한다. 기존의 방법은 긴 수열을 찾는데 O(N)의 시간이 걸려 모든 배열의 값을 탐색한 후에는 전체 알고리즘 복잡도는 O(N^2)가 되었다 하지만 길이 L 인 수열의 마지막 값들 중 최소 값을 저장하는 배열을 둔다고 생각해보자 C[L] C[]배열은 순 증가하는 그래프가 될 것이다. (간단히 설명하자면 C[N]은 C[N-1]의 영향을 받을 것이고 C[N-1]은 현재 길이에서 최소의 값을 가지기 때문에...귀납적으로 설명하면 그렇다. 직감적..
-
c++ priority_queue에서 comparator 선언해주는 방법알고리즘/자료구조 2015. 8. 26. 11:49
class Prove{ public : int pos, cost, time; Prove(int nposition, int ncost, int ntime){ pos = nposition; cost = ncost; time = ntime; } }; class mycomparison { public: bool operator() (const Prove& a, const Prove& b) const { return a.time > b.time; } }; priority_queue mypq; 위의 Prove class는 내가 문제를 풀기 위해 임의로 만든 것이기 떄문에 무시해도 된다.만약 int인 priorityqueue를 만들고 싶다면 priority_queue으로 선언하면 된다. 여기서 세가지 인자가 들어가는..