C/알고리즘5 동적 표를 이용하자. 동적표란 우리가 계산하면서 나온 결과값을들 저장해두는 표를 말한다. 이러한 행위를 왜 하는가? 관계기반 설계를 설명할 때, 탐색기반을 함께 설명했었다. 그때 탐색기반의 단점을 해소 하기 위해 '배제'를 한다고 했었는데 동적 표를 이용하여 비슷한 개념의 행위로 똑같은 효과를 낼 수 있다. 무슨 뜻이냐면, 이미 계산한 결과를 저장해두고, 중복되는 일이 있을때 그값을 꺼내 오기만 하면 된다. 이로써 중복된 연산을 피할 수 있고, 결론적으로 더 빠르고 효율적인 프로그램이 되는 것이다. 또한, 이전 값을 이용해서 다음 값들을 채워 나갈 수 있다. 이전 값이 반드시 필요한데 이건 관계 기반 설계에서 f(1)을 미리 구한 것과 같다. ex) 피보나치 수열 1) 동적 표를 사용하지 않은 방식 1234567int f(i.. 2016. 12. 18. 관계기반 알고리즘의 설계 알고리즘 설계법은 크게 두 가지가 있다. 1. 관계기반 설계 각 값들 사이의 관계를 이용하여 해를 구하는 방법 함수로 표현할 수 있어야 하며, 점화식같은 형태를 이용하여 표현 할 수 있어야 한다. 2. 탐색기반 설계 컴퓨터의 빠른 연산으로, 모든 집탑을 탐색하는 방법. 크기에 비래하여 시간이 길어질 수도 있다. 때문에 배제를 한다. ex) 1 ~ n 까지의 합 1) f(1) = 1;f(n) = f(n-1)+n; (n>=2) [출처] 알고리즘 심화 - 관계기반 알고리즘의 설계|작성자 bestmaker 1234567int f(int n){ if (n == 1) return 1; else return f(n - 1) + n;}cs 위와 같이 표현할 수 있겠다. 2) f(k) 를 n/2 로 가정 f(1) = 1.. 2016. 12. 18. Lower bound Upper bound Lower bound 선형구조의 부분탐색인 이진탐색은 찾고자 하는 값이 없으면 실패한다. 하지만, Lower bound는 찾고자 하는 값보다 이상인 값이 처음 나타나는 위치이다, Lower bound는 같은 원소가 여러개 있어도 상관 없다. 위치를 찾기위해, 이진탐색에서 조금만 바꾸면 된다. 1234567891011121314151617181920212223242526272829303132333435#include int find(int arr[], int f, int s, int e); int main(void){ int i; int f; int n; int arr[10000] = {}; int check = 0; scanf("%d", &n); for (i = 0; i 0) { m = (s + e) /.. 2016. 5. 10. 인접 행렬 그래프, 깊이 우선탐색 (DFS), 너비 우선탐색(BFS) 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394959697989910010110210310410510610710810911011111211311411511611711811912012112212312412512612712812913013113213313413513613713813914014114214314414514614714814915015115215315415515615715815916016116216316416516616716816.. 2016. 5. 10. 이전 1 2 다음
