tonirr

정렬의 개념 정렬이란 주어진 데이터를 값의 크기 순서에 따라 재배치 하는 것 정렬수행시점에 데이터가 어디에 저장되어 있는가? 내부정렬 모든 데이터를 주기억장치에 저장한 후 정렬하는 방식 비교 기반 알고리즘 버블정렬, 선택정렬, 삽입정렬, 셸정렬 O(n^2) 합병정렬, 퀵정렬, 힙정렬 O(nlogn) 데이터 분포 기반 알고리즘 계수 정렬, 기수 정렬 O(n) 외부 정렬 모든 데이터를 주기억장치에 저장할 수 없는 경우 모든 데이터를 보조기억장치에 저장한 채 그중 일부데이터씩 반복적으로 주기억장치에서 읽어들여서 정렬하는 방식 안정적 stable 정렬 동일한 값을 갖는 데이터가 여러개 있을 때 정렬 전의 상대적인 순서가 정렬 후에도 그대로 유지되는 정렬 방식 제자리 in-place 정렬 입력 데이터를 저장한 공..

포인터와 배열 char 포인터 포인터는 문자열 처리에 효과적 문자열 처리에 char형 포인터 사용 char *cp = "COMPUTER"; char 포인터의 기억공간 표현 char *cp = "COMPUTER"; cp는 문자열의 시작주소를 갖는다. 따라서 값을 참조할 떄와는 달리 포인터변수 cp에 주소를 치환하지 않는다. 포인터와 배열의 관계 포인터와 배열의 관계 포인터를 이용한 1차원 배열의 참조 char s[] = "SCIENCE"; char *cp; cp = s; -> 포인터 cp를 이용하여 배열 s의 내용을 참조 배열은 포인터의 일부분 모든 배열은 포인터로 표현 가능 cp+1 &s[1] *(cp+1) s[1] 포인터를 이용한 2차원 배열의 참조 int a[2][3]; int *pt; pt = a;..

최단경로 가중방향 그래프에서 두 정점을 연결하는 경로 중에서 간선의 가중치의 합이 가장 작은 경로 플로이드 알고리즘 모든 정점 간의 최단 경로 동적 프로그래밍 방법 적용 O(|V|^3) 가중치의 합이 음수인 사이클이 없다고 가정 플로이드 Floyd 알고리즘 다익스트라 Dijkstra 알고리즘 모든 정점 간의 최단 경로 특정한 하나의 정점에서 다른 모든 정점으로의 최단 경로 (단일 출발점 최단 경로) 동적 프로그래밍 방법 적용 그리디 방법 적용 O(|V|^3) O(|V|^2) 가중치의 합이 음수인 사이클이 없다고 가정 음의 가중치를 갖는 간선이 없다고 가정 다익스트라 알고리즘 거리 d[v] 출발점에서 현재까지 선택된 정점 집합 S를 경유하여 정점 v에 이르는 최소 경로의 길이 출발점에서 시작하여 거리 d[..

인덱스의 필요 데이터 검색에서 발생하는 비효율적인 데이터 입출력 문제를 해결하기 위한 목적으로 시작 인덱스: DBMS에서 요청된 레코드에 빠르게 접근할 수 있도록 지원하는 데이터와 관련된 부가적인 구조 인덱싱: 인덱스를 구성하고 생성하는 작업 인덱스의 탐색키를 이용하여 해당 레코드가 저장된 블럭을 디스크 저장장치 또는 메모리에서 파악하여 해당 블럭을 빠르게 적재 탐색키 파일에서 레코드를 찾는데 사용되는 컬럼이나 컬럼의 집합 인덱스 기반의 검색 과정 인덱싱 되어 있는 컬럼을 메모리에 빠르게 올리고 디스크에서 찾음 인덱싱의 종류 인덱스의 종류 순서 인덱스: 특정 값에 대해 정렬된 순서 구조 순서 인덱스의 특징 탐색키로 정렬된 순차파일에 대해 레코드에 대한 빠른 접근이 가능하도록 구성한 인덱스 탐색키를 정렬하..

물리적 저장장치 물리적 저장장치의 구성 물리적 저장장치는 데이터 접근 속도, 용량을 기준으로 다양한 장치로 구성 레지스터 캐시 메인메모리 자기디스크, 플래시메모리 광학디스크, 자기 테이프 물리적 저장장치별 특징 휘발성 캐시: 고비용 저장장치로 빠른 접근 속도를 보장 메인 메모리: 실제 프로그램과 데이터 적재 공간 비휘발성 플래쉬 메모리: 메인 메모리와 유사하나 비휘발성 자기 디스크: 데이터베이스 전체를 안정적으로 저장 광학 디스크 드라이브: CD, DVD, Blue-ray 등 테이프 장치: 용량이 크고 저렴하나 순차 접근 방식으로 접근속도가 매우 느림 파일 데이터베이스의 구성 데이터베이스 -> 파일 -> 블럭 -> 레코드 데이터베이스 구성 요소 파일 데이터를 영구적으로 저장하기 위해 사용되는 가장 기초적..

함수적 종속성의 확장 함수적 종속성은 릴레이션의 효율성 여부에 중요한 판단기준 그러나 릴레이션의 인스턴스만으로 내재된 모든 함수적 종속서을 찾아내기 어려움 판별되지 않은 모든 함수적 종속성을 찾기 위해 추론 규칙을 사용하여 함수적 종속성을 확장 클로저(closure) 판별된 함수적 종속성 집합으로부터 유추할 수 있는 모든 함수적 종속성 집합 함수적 종속성 추론 규칙 암스트롱 공리(Armstring's axiom) 재귀성 규칙: X⊇Y이면, X→Y이다 부가성 규칙: X→Y이면, XZ→YZ이다 이행성 규칙: X→Y이고, Y→Z이면, X→Z이다. 분해 규칙: X→YZ이면, X→Y이다. 합집합 규칙: X→Y이고, X→Z이면, X→YZ이다. 의사 이행성 규칙: X→Y이고, WY→Z이면, WX→Z이다. 함수적 종속..

포인터변수의 선언 형식: 자료형 *포인터변수명; 사용 예: int *p; 기능: 변수 p는 포인터 변수로서 정수형의 자료를 갖는 변수의 주소를 갖는다. int *p p: 포인터 변수로 정수형 자료가 수록되어 있는 주소를 가지고 있음 *p: 해당 주소에 수록되어 있는 정수형 자료를 갖고 있음 포인터변수의 사용 예 int a, b; int *p; 변수 p를 포인터 변수로 선언 a=5000; p=&a; 포인터 변수 p에 변수 a의 주소 값을 대입 b=*p; 포인터 변수 p가 가리키는 주소의 내용을 변수 b에 저장(a의 값 5000이 b에 저장된다) 포인터변수의 참조 포인터변수의 참조 => &, * 연산자 사용 예 1) int *p, i=4; *p=i; 포인터변수 p가 기억공간 내 몇 번지를 가르키는지 알 수 ..

해를 구하는 일련의 선택 단계마다 전후 단계의 선택과는 무관하게 해당 단계에서 가장 최선이라고 여겨지는 국부적인 최적해를 선택함으로써 전체적인 최적해를 구함 greedy -> 탐욕적 방법, 탐욕 알고리즘, 그리디 알고리즘 동적 프로그래밍 방법 그리디 알고리즘 최적화 문제 해결에 주로 사용 최적성의 원리가 적용된 방법 소문제의 여러 최적해로부터 다음 크기의 문제에 대한 최적해가 결정 -> 항상 전체적인 최적해를 구함 소문제(각 단계)에 대해서 하나의 최적해만을 고려 -> 전체적인 최적해를 구하지 못할 수도 있음 그리디 알고리즘 방법의 원리 그리디 알고리즘의 한계 예를들어 가장 멋진바지, 가장 멋진 넥타이, 가장 멋진 자켓을 입는다고 할 때 그런 옷을 입은 멋쟁이씨는 과연 세상에서 가장 멋쟁이라고 할 수 있..