본문 바로가기

C38

동적 표를 이용하자. 동적표란 우리가 계산하면서 나온 결과값을들 저장해두는 표를 말한다. 이러한 행위를 왜 하는가? 관계기반 설계를 설명할 때, 탐색기반을 함께 설명했었다. 그때 탐색기반의 단점을 해소 하기 위해 '배제'를 한다고 했었는데 동적 표를 이용하여 비슷한 개념의 행위로 똑같은 효과를 낼 수 있다. 무슨 뜻이냐면, 이미 계산한 결과를 저장해두고, 중복되는 일이 있을때 그값을 꺼내 오기만 하면 된다. 이로써 중복된 연산을 피할 수 있고, 결론적으로 더 빠르고 효율적인 프로그램이 되는 것이다. 또한, 이전 값을 이용해서 다음 값들을 채워 나갈 수 있다. 이전 값이 반드시 필요한데 이건 관계 기반 설계에서 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.
어셈블리, 메모리 구조, 함수 생성 및 파기 과정 메모리 구조 어셈블리어mov : Source에서 Destination으로 데이터를 복사한다.add : Destination에 Source의 값을 더해서 Destination에 저장한다.sub : Destination에 Source의 값을 빼서 Destination에 저장한다.push : 스택에 값을 넣는다. ESP의 값이 4만큼 줄어들고 이 위치에 새로운 값이 채워진다.pop : ESP 레지스터가 가리키고 있는 위치의 스택 공간에서 4byte 만큼을 Destination 피연산자에 복사하고 ESP 레지스터의 값에 4를 더한다. 레지스터eax : 산술, 논리연산을 수행한 값이 저장되며 함수의 리턴값이 저장됨.eip : 다음에 실행하여야 할 명령어가 존재하는 메모리 주소가 저장됨.ebp : 스택의 시작지점 .. 2016. 6. 14.
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.

티스토리툴바