저희 학교 알고리즘 과목에 첫 번째 과제로 피보나치킨이 등장했습니다. 입력 제한이 3억일 때, 피보나치 배열을 어느 제한까지 구해야 하는지, 배열 인덱싱과 stringToint의 형 변환 등 다양한 요소가 포함되어 있습니다. 단순 구현으로 풀이해도 되지만, 다양한 풀이법이 존재하고 피보나치수열과 제켄도르프 정리는 상당히 흥미로운 내용이기 때문에 소개해 드리려고 합니다. 코드는 모두 올리진 않겠습니다. 학교 과제 내용이기도 해서.. 1. DP를 이용한 풀이 방법 가장 일반적인 방법입니다. f(n)=f(n-1)+f(n-2) 라는 간단한 점화식을 활용해 피보나치 수를 구한 다음, n보다 작지만 가장 큰 피보나치 수를 빼며 그 인덱스를 치킨 합에 더해주고 n에 피보나치 수를 빼고 n을 0으로 만들면 종료합니다...
// d is the number of characters in the input alphabet #define d 29 //find txt in pattern int RCsearch(const string& pattern , const string& txt, int q = 100003) { int M = pattern.size(), N = txt.size(); int p = 0; // hash value for pattern int t = 0; // hash value for txt int h = 1; for (int i = 0; i < M - 1; i++) h = (h * d) % q; for (int i = 0; i < M; i++){ p = (d * p + pattern[i]) % q; t = (..
2차원 평면위의 두 점사이의 상대적인 위치를 정확히 표현하기위해 방향과 거리의 쌍을 벡터(vector)라고 합니다. 기하문제들을 프로그래밍하기위해 꼭 필요한 개념입니다. 일이러한 벡터의 기본적 덧셈,뺄셈,곱셈 등의 기하학적 문제들을 다룰수있는 구조체 입니다. const double PI = 2.0*acos(0.0); struct vector2 { double x, y; explicit vector2(double x_, double y_) :x(x_), y(y_) {} bool operator == (const vector2& rhs) const { return (x == rhs.x && y == rhs.y); } bool operator < (const vector2& rhs) const { return..
int ccw(pair a, pair b, pair c) { int op = a.first*b.second + b.first*c.second + c.first*a.second; op -= (a.second*b.first + b.second*c.first + c.second*a.first); if (op > 0)return 1; else if (op == 0)return 0; else return -1; } bool isIntersect(pair x, pair y) { pair a = x.first; pair b = x.second; pair c = y.first; pair d = y.second; int ab = ccw(a, b, c)*ccw(a, b, d); int cd = ccw(c, d, a)*cc..
const int MAX_N=100,MAX_V=MAX_N*2+2,INF=987654321; int N,M,S=MAX_V-2,E=MAX_V-1,capacity[MAX_V][MAX_V],flow[MAX_V][MAX_V]; vector adj[MAX_V]; int networkFlow(int source,int sink) { memset(flow,0,sizeof(flow)); int totalSum=0; while(true) { vector parent(MAX_V,-1); queue q; parent[source]=source; q.push(source); while(!q.empty()&&parent[sink]==-1) { int now=q.front();q.pop(); for(auto next:adj[now..
typedef long long ll; ll cache[MAX_N][MAX_N]; //use dp ll comb(int n,int r) { if(r==0||n==r)return 1; ll&ret=cache[n][r]; if(ret!=-1)return ret; return ret=comb(n-1,r-1)+comb(n-1,r); } //if n is small ll comb(int n,int r) { if(r==0||n==r)return 1; return comb(n-1,r-1)+comb(n-1,r); } nCr=(n-1)C(r-1)+(n-1)Cr 점화식을 이용한 간단한 재귀함수이다. 경우의 수의 특성상 수가 조금만 커져도 int범위를 간단히 넘어버리니 왠만한 경우에는 long long 을 선언해서 풀어주어..
void pick(int n,vector&picked,int toPick) { if(!toPick) { //do something with picked return ; } int smallest=picked.empty()?0:picked.back()+1; for(int next=smallest;next
