리루

- 해시 테이블은 가장 효율적인 탐색 중 하나인 해싱을 제공한다.- 기본적으로 해시 테이블은 키(key)라는 특별한 인덱스로 자료에 접근하는 배열로 구성된다.- 해시 테이블의 주 개념은 모든 가능한 키들과 배열의 위치 사이에 해시 함수를 이용해서 매핑(mapping)을 만드는 것이다.- 해시 함수는 키를 전달 받아서 그 키의 해시 값(hash coding or hash value)을 리턴한다.- 키들의 형은 다양하지만 해시 값은 항상 정수이다. - 해시 값을 계산하는 것과 배열에서 특정 위치의 값을 얻는 것은 모두 상수 시간에 실행되므로 해싱의 매력은 상수 시간 탐색을 제공하는 점이다.- 해시 함수가 임의의 키에 대해 같은 해시값을 리턴하지 않는다면 이 때 생성되는 해시 테이블은 직접 참조된다라고 한다...

집합(Set)은 - 원소(Member)라는 구별되는 객체들이 연관되어 모인 것이다. - 서로 다른 연관된 원소들의 순서 없는 모임이다. 특징- 순서가 없다.- 원소들끼리 서로 다르다 응용1. 그래프 - 객체들 사이의 관계나 연결로 정의되는 문제(?)들을 모델링하는 데 전형적으로 사용되는 자료구조다. - 그래프를 표현하는 가장 일반적인 방법은 인접 리스트(adjacency list)를 사용하는 것이다. - 인접 리스트는 하나의 정점에 인접한 정점들을 갖는다. - 인접 리스트를 표현하는 한 방법은 인접한 정접들의 집합으로 표현하는 것이다. 2. 그래프 알고리즘 - 그래프로 모델링되는 문제들을 푸는 알고리즘이다. - 흔히 그래프 알고리즘은 정점들이나 에지들을 함께 모으는 데 집합을 사용한다. - 예를들어, 최..

재귀는 자신의 보다 작은 인스턴스들로 무엇인가를 정의할 수 있게 하는 강력한 원리이다. 재귀함수는 자신을 호출하는 함수이다. -->팩토리얼int fact(int n){ if(n 팩토리얼F(n,a) = a (if n=0, n=1, a는 기본 1) = F(n-1,na) (if n>1) int facttail(int n, int a){ if(n

Code SegmentData SegmentStack Heap[메모리 구조] 입력 매개변수리턴값임시기억장소상태정보저장출력 매개변수[활성 레코드의 메모리 구조] - 코드 영역에는 프로그램이 실행될 때 수행되는 기계어가 들어간다.- 정적 자료 영역에는 전역변수와 static local variable 같이 프로그램이 실행되는 동안 항상 존재하는 자료가 들어간다.- 힙은 malloc 함수를 통해 할당되는 메모리처럼 동적으로 할당되는 메모리 공간이다.- 스택에는 함수 호출 관련 정보가 들어간다.- 관례상 합 영역은 프로그램 메모리의 한쪼 끝에서 위로 커져가고, 스택은 반대로 끝에서 아래로 커져간다. - C 프로그램에서 함수가 호출될 때 호출과 관련된 정보를 보존하기 위해 스택에서 메모리 블록을 할당 받는다.- ..

함수의 매개변수로서의 포인터 포인터는 C에서 함수 호출의 가장 중요한 부분이다. 가장 중요한 것은 참조 호출(Call-by-reference)이라는 매개변수 전달을 지원하기 위해 포인터가 사용된다는 점이다. 참조호출에서 함수가 전달된 매개변수를 변경했을 때 그 변경은 함수가 리턴한 후에도 지속된다. 매개변수 변경이 함수 내에서만 지속되는 값 호출(Call-By-Value)과 비교해 보라. 또 자료의 변경과 관계없이 많은 양의 자료를 함수에 전달하거나 함수에서 전달받을 때 포인터가 효율적인 수단이 된다. 전체 자료 대신에 포인터만 전달되므로 이 방법은 효율적이다. 참조 호출 매개변수 전달 형식적으로 C는 값 호출만 제공된다. 값 호출 매개변수 전달에서는 함수가 실행될 때 전달된 매개변수의 내부 복사본이 만..

자료구조 1. 효율성 - 자료구조는 좀 더 효율적인 알고리즘이 될 수 있도록 자료를 구조화 시킨다. 자료를 탐색하기 위한 구조를 예로 들어보자. 단순하게 자료들을 배열에 넣고 원하는 자료를 찾을 떄까지 앞에서 차례대로 하나씩 비교하는 방법이 있따. 그러나 이 방법을 이용하면 모든 자료를 비교하는 일이 종종 발생하므로 비효율적이다. 이 경우에는 해시 테이블이나 이진 트리 같은 자료구조를 사용하면 훨씬 빠르게 탐색할 수 있다. 2. 추상화 - 자료 구조는 자료를 바다 쉽게 이해할 수 있는 방법을 제공한다. 즉 문제 해결을 위한 어느 정도의 추상화를 제공한다. 자료를 스택에 넣는 예를 보면, 스택에 자료를 넣고 빼는 연산의 자세한 구현 방법보다는 그 연산을 어떻게 이용할 것인지에 초점을 찾출 수 있다. 즉 자..