SW/Algorithm
-
[알고리즘] 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..