KMS_studio programming KMS_studio programming

확장유클라디안 알고리즘으과 메모이제이션을 사용하는 문제입니다. 모든 팩토리얼에 대해 normal modular와 inverse modular를 계산한 뒤, 입력값에 따라 처리합니다. 시간복잡도는 N의 최대값을 N, 제수를 M이라 할 때 O(NlogM)입니다. #include #include #define MOD_N 1000000007 #define MAX_N 4000000 typedef long long lint; int mem[MAX_N+1] = { 0, }; int inv[MAX_N+1] = { 0, }; int EEA(int i, int m){ int Q, Q1, Q2; int S, S1, S2; int T, T1, T2; int M; Q1=i; Q2=m; S1=T2=1; S2=T1=0; for(;..

KMP 알고리즘 문제입니다. #include #include #define MAX_N 1000002 char T[MAX_N] = { 0, }; char P[MAX_N] = { 0, }; int pi[MAX_N] = { 0, }; int res[MAX_N]; int main(void){ int lenT, lenP; int cur, loc, cnt; fgets(T, MAX_N, stdin); fgets(P, MAX_N, stdin); lenT=strlen(T); lenP=strlen(P); lenT--; lenP--; T[lenT]=P[lenP]=0; pi[0] = -1; for(int i=1;i

조금 새로운 이진탐색 문제입니다. 직관적으로는 스택을 사용해서 풀 수 있지만 그렇게 풀면 시간복잡도가 N^2이 되버리므로 나락을 가버립니다. 스택에 들어가는 값이 항상 정렬되있다는 사실을 활용, 이진탐색으로 시간복잡도를 NlogN까지 올릴 수 있습니다. #include int stk[500000] = { 0, }; int srcs(int val, int sze){ int lft=0, rht=sze-1, mid; for(mid=(lft+rht)/2;lft

DP문제입니다. 공간복잡도 O(W^2), 시간복잡도 O(W^2)으로 해결가능합니다. 또한 각 사건마다 할당된 경찰관을 묻고 있기 때문에 간단한 자취 남기기 기법을 응용합니다. DP의 구성은 아래와 같습니다. 회색 영역은 초기화 때 계산됩니다. 빗금 영역에 있는 값 중 최소의 값을 문제의 답으로 결정합니다. 한 번에 계산되는 양은 아래와 같습니다. 코드는 아래와 같습니다. #include #include #define SZE 1000 int dp[SZE+1][SZE+1]; int idx[SZE+1][2]; int giv[SZE+1] = { 0, }; typedef struct _p{ int row; int col; }point; point loc[SZE+1]; int get_dst(point p1, poi..

오늘은 코드로 상대를 유혹하는 방법을 알아보겠습니다.모든 코드는 ANSI문법을 준수합니다.01. 분기없이 Max, min 구하기#define MIN(x, y) ((y) ^ (((x) ^ (y)) & -((x) 02. N을 32로 나눈 나머지N & 0x1F03. log N값 구하기const int tab64[64] = { 63, 0, 58, 1, 59, 47, 53, 2, 60, 39, 48, 27, 54, 33, 42, 3, 61, 51, 37, 40, 49, 18, 28, 20, 55, 30, 34, 11, 43, 14, 22, 4, 62, 57, 46, 52, 38, 26, 32, 41, 50, 36, 17, 19, 29, 10, 13, 21, 56, 45, 25, 31, 35, 16, 9..

Plane sweep algorithm은 서로 겹치는 직사각형들이 주어질때, 직사각형이 총 차지하는 면적을 구하는 문제에 주로 사용됩니다. 아래 기술하는 알고리즘이 완벽한 plane sweep algorithm은 아니자만, 특별한 상황이 아닌 이상 plane sweep algorithm을 사용하는데는 지장이 없을 겁니다. 정확한 plane sweep algorithm은 아래 pdf를 참고해주시면 감사하겠습니다.아래 직사각형이 겹쳐졌을때 총 넓이를 구한다 가정해봅시다. 먼저 직사각형의 가로선들을 포함하는, x축에 평행한 직선들을 추출해냅니다. 직사각형의 가로선들로 Y[]배열을 만듭니다.배열을 만들어낸 후에는, 오름차순으로 정렬하고, 중복된 값들을 제거하여 Y[]배열을 완성합니다.Y[0]Y[1]Y[2]Y[3..

오늘은 난수에 대한 자료들을 다루어보겠습니다NIST에서 권장하는 난수 생성의 기준이라고 할까요? 그정도 느낌의 자료입니다.영어로 된 자료는 많지만, 한국어로 된 자료는 없어서 내가 볼겸, 정보공유를 할 겸 해서 포스트를 하게 되었습니다일단 pdf를 먼저 올려드리도록 하겠습니다이 pdf는 어떻게 수가 난수인지를 판별하는가에 대한 13가지의 기준을 설명하고 있습니다. 모든 기준을 만족해야 random number라 할 수 있구요, 각종 통계학에서 사용되는 것으로 보이는 함수들을 수식에 다량 사용하고 있습니다. 개인적으로는 뒤로 갈수록 수식이 더 복잡해지는 것 같았습니다. NIST에서는 이 random 판별 방식의 소스또한 공개하고 있습니다.(아래 사이트를 클릭하시면 자료를 가져온 사이트로 가실 수 있습니다)..

C언어 파이값을 비롯해, 자연상수, 자연상수 로그값, 자연소그부터 루트 파이와 2 분의 파이 등 다양한 상수값?들을 알아내는 방법을 알아봅시다.개인적으로 알면 별거 아닌데, 꼭 필요할때 기억이 안 나서 검색을 해봐야 했으므로 그냥 여기다 씁니다. 코드#include #define _USE_MATH_DEFINES#include // Now we can use MATH_PIint main(void) { return 0;} 사용가능한 매크로들 (발췌 : mathcorecrt_math_defines.h Copyright (c) Microsoft Corporation. All rights reserved.)// 이 매크로를 사용하기 위해서 _USE_MATH_DEFINES를 including 하기 전에 defin..