알고리즘
-
[알고리즘] Dynamic Programming (동적프로그래밍)SW/Algorithm 2018. 1. 5. 22:00
Dynamic Programming (동적계획법) 분할정복비법처럼 작은 문제들로 나누어 각각 해답을 찾고 원래 문제의 해답을 계산 하지만 중복이 발생하여 반복연산이 많아 수행시간이 길다. => 메모리제이션으로 해결(반복연산 제거) ex) 최적화 문제(최대,최소) : working backward기법 사용 (top-down 방법으로)-> 재귀식으로 정의 (중복계산발생)-> bottom-up 방식 -> 저장할 테이블을 생성 [앞 1~3번째 까지는 최적값을 계산하는 과정이고, 마지막은 최적해답을 계산하는 단계]factorial //많은 중복연산을 함. n=100int f(int n) //메모리제이션 - 미리저장{int i ,f[100];f[0]=1; //base casefor(i=1;i c(n) = c(n-1..
-
[알고리즘] 카타란 수SW/Algorithm 2018. 1. 5. 14:55
카탈란 수 코드링크 쌍을 이루는 것들을 나열하는 모든 경우의 수. 카탈란 수열 문제들 모든 괄호 짝 산 만들기 대각선 피해가기 다각형을삼각형으로 나누기 모든 괄호 짝 n쌍의 괄호가 잘 짜놓은 방법을 Cn. (A)B => A에 괄호가 k쌍 있다면 B에는 n-1-k쌍이 있다.(트리?) C1= C0C0 c2= C0C1+C1C0 c3= C0C2+C1C1+C0C2 ... Cn= Σ Ci*Cn-1-i (i는 0~n-1) Code void PrintBracket(bool *state,int size){ for(int i=1;i>n; bool state[2*100]; //n은 최대 100개, 괄호를 열것인지 닫을것인지 넣는다. Bracket(state,1,n,0); return 0;}
-
[Codeforces] Educational Codeforces Round 35/ B.Two CakesSW/Algorithm 2018. 1. 4. 22:58
Educational Codeforces Round 35/ B.Two Cakes 문제 링크 코드 링크 블로그 풀이풀이 케익 두개를 한개는 a조각으로 다른하나는 b조각으로 나눈다. n명의 사람이 오는데 접시에 자른케익을 놓는다. 한 접시에는 적어도 한조각이 있어야한다. 두가지 종류의 케익을 같은 접시에 놓을 수 없다. (문제에) 접시에 최소 캐익의 조각 개수가 최대가 되도록 한다. min(a/i,b/(n-i)) : 접시에 최소 캐익의 조각. max(ans,min()) : 최대가 되도록 int main(){ int n,a,b; cin>>n>>a>>b; int ans=0; for(int i=1;i
-
[Codeforces] Educational Codeforces Round 35/ A.NearestMinimumsSW/Algorithm 2018. 1. 4. 08:30
Educational Codeforces Round 35/ A.NearestMinimums 문제 링크 코드 링크 블로그 풀이풀이 영어가 약해서 무슨말인지 이해하기 힘들었다. 주어진 숫자 중 최소끼리 가장 가까 운 거리를 구하는 것 이다. 3 4 6 3 중 3 이 최소.. 3 에서 3은 3칸 이므로 답은 3 이다. int input[100004];int main(){ int n; cin>>n; long long min_n=1000000003; int distance=100000000; int ans=10000000; for(int i=1;i>input[i]; if(min_n>input[i]) { min_n=input[i]; distance=i; ans=100000000; } else if(min_n==in..
-
[알고리즘] TopologicalSoring (위상정렬)SW/Algorithm 2018. 1. 1. 20:30
위상정렬 (topological sorting) 방향 그래프에 존재하는 각 정점들의 선행 순서를 위해하지 않으면서 모든 정점을 나열하는 것. 진입 차수 0인 정점(들어오지않는)을 선택하고 선택된 정점과 여기에 부속된 모든 간선을 삭제한다. 반복해서 모든 정점이 선택,삭제되면 알고리즘을 종료. 이 과정에서 선택되는 정점의 순서를 위상순서(topological order)라 한다.example 진입 차수가 없는 0,1 선택가능. 후보: 0,1 (여기선 1 선택) (스택사용) 1에서 뻗는 간선들 삭제.(그러면 4에 들어오는 차수 0) 후보: 0,4 (4 선택) 4에서 뻗는 간선(4->5)삭제. (5는 들어오는 다른 간선이 있기 때문에 후보X) 후보: 0 (0 선택) 반복... 위상 순서: 1 4 0 2 3 5..
-
[알고리즘] Divide & Conquer (분할정복기법)SW/Algorithm 2018. 1. 1. 10:30
Divide & Conquer (분할정복기법) Recursion 기반 해결기법 분할정복기법의 문제해결 시나리오 분할(Divide) : 주어진 문제를 쪼갬 정복(Conquer) : 나누어진 작은 문제는 재귀로 해결. (재귀적으로 계속 분할해간다) 통합(Combine) : 나눴던 문제들로부터 구한 해답들을 서로 통합하여 원래 문제의 해답을 만든다. Top-Down 문제해결 방법 Top-Down : 작은 문제로 분할하여 해결하는 방법 Recursion으로 알고리즘 구현 Top-Down 을 더 작은 문제로 반복해서 분할 Divide & Conquer 분할정복기법 알고리즘의 정확성 증명 (수학적 귀납법 사용) 분할정복기법 알고리즘의 시간복잡도 계산Tromino 타일 채우기 문제 : 한 모퉁이가 없는 2X2로 타일..
-
[알고리즘]Recursion(재귀)SW/Algorithm 2017. 12. 31. 00:14
깃허브 바로가기(코드) Recursion -> 자신이 수행할 작업을 유사한 형태의 여러 조각으로 쪼갠 뒤 그 중 한 조각을 수행하고, 나머지를 자기 자신을 호줄해 실행하는 함수를 가리킨다.(완전탐색을 구현할 때 유용) base case : 함수의 값을 직접 계산할 수 있는 단순한 경우(적어도 한 개 이상의 base case가 있어야 함) recursive step : base case가 될 때까지 계속 환산해 나가면서 계산(스택 오버플로우 발생) type of recursion 단일 리컬젼 : 자기 자신을 부르는 곳이 하나 ex) 팩토리얼 바이너리 리컬젼 : 부르는 곳이 두개 ex) 피보나치 멀티 리컬젼 : 부르는 곳이 여러개 Function call stack 함수를 호출 할 때, 지금 실행중인 함수는..
-
[알고리즘] Begin AlgorithmSW/Algorithm 2017. 12. 30. 00:59
문제 해결 과정 문제를 읽고 이해하기 재정의와 추상화 계획 세우기 계획 검증 계획 수행 회고하기 (코드와 함께 자신의 경험을 기록 & 오답 원인 & 다른사람코드확인) 간결한 코드 작성하기 #define FOR(i,n) for(int i=0;i (n-1,r-1) + (n-1,r) 실수 크기 비교 현실적으로 오차를 생각하기 |a-b|/max(|a|,|b|)로 a,b 상대오차를 구하기 bool relativeEqual(double a,double b){ return fabs(a-b) =0; j--) if (a[j] > value) a[j+1] = a[j]; else break; a[j+1] = value; }} * Primitive operation T(n) : 4n^2+5n-8 (=, +, --) = O(n..