프로그래밍 잡동사니

보호되어 있는 글입니다.

알고리즘이란? 알고리즘(Algorithm) = 문제를 해결하기 위한 단계적인 절차 * 해결 방법은 다양하지만 가장 효율적인 방법을 찾는 것에 의의가 있다 알고리즘의 특성 정확성: 주어진 입력에 대해 올바른 해를 주어야 한다 수행성: 각 단계는 컴퓨터에서 수행 가능해야 한다 유한성: 일정한 시간 내에 종료되어야 한다 효율성: 효율적일수록 그 가치가 높아진다 유클리드(Euclid)의 최대공약수 알고리즘 = 최초의 알고리즘 알고리즘의 표현 방법 알고리즘은 프로그래밍 언어나 의사 코드(pseudo code)로 표현할 수 있다 최대값 알고리즘을 표현하는 다양한 방식.. 알고리즘의 분류 문제 해결 방식에 따른 분류 분할 정복(Divide-and-Conquer) 알고리즘 그리디(Greedy) 알고리즘 동적 계획(Dy..

장애와 회복 장애란 시스템이 정해진 명세대로 작동하지 않는 상태이며, 장애의 원인으로는 ‘하드웨어 결함 / 소프트웨어의 논리오류 / 사람의 실수’ 등이 있다 트랜잭션 장애: 논리적 오류 입력 데이터의 불량 시스탬 장애: 하드웨어의 오동작 미디어 장애: 디스크 헤드 붕괴 또는 고장 회복(Recovery)이란 DB를 장애 발생 이전의 일관된 상태로 복원시키는 것으로, 일관된 상태(consistent state)란 오류가 없고 DB 내용에 모순이 없는 상태이다. 회복의 기본 원리는 데이터를 중복(redundancy)으로 기록하는 것이며, 다른 저장장치에 그대로 복제는 덤프(dump) 방식이나 데이터 파일의 변경된 부분만 별도의 파일에 기록하는 로그(log, journal) 방식을 사용할 수 있다 회복을 위한 ..

그래프 그래프란 연결되어 있는 객체 간의 관계를 표현하는 자료구조이다 그래프 G는 (V, E)로 표현되며 ‘정점(vertices) or 노드’ / ‘간선(edge) or 링크’ 간의 관계를 의미한다 그래프의 경로: 정점 간 거쳐가는 경로 ex) B -> A -> C -> D 그래프의 길이: 경로 사이의 간선 개수 ex) 3 그래프의 표현 그래프의 탐색 그래프의 탐색은 시작 정점부터 차례대로 모든 정점들을 한 번씩 방문하는 방법으로, 깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS)이 있다 신장 트리 신장 트리란 그래프 내의 모든 정점을 포함하는 트리로 사이클을 포함하면 안된다 위상 정렬 위상 정렬이란 방향 그래프에 대해 정점들의 선행 순서를 위반하지 않으면서 모든 정점을 나열하는 것 가중치 그래프 간선..

질의어 처리 SQL(고급 질의어)가 scanner를 거치면서 token(의미)이 생성되고 내부 형태 질의문으로 변환된다 내부 형태 질의문(= tree -> 관계 대수)이 질의어 최적기를 거쳐 plan으로 선택된다 plan이 질의문 실행 코드, DB 처리를 거쳐서 결과적으로 질의어 결과를 도출한다 질의어 최적화 중간 과정의 질의어 최적화란? 더 성능이 빠른 (효율적) 실행을 위해 디스크 I/O횟수, 중간 결과의 크기, 응답시간을 감소시킨다 ‘질의문 내부표현 -> 효율적 내부형태로 변환 -> 후보 프로시저 선정 -> 평가 및 결정’ 질의문 트리의 단말 노드에는 피연산자인 릴레이션이, 내부 노드에는 관계대수 연산자가 들어간다 질의문 트리는 상향식으로 실행되며, 마지막으로 루트 노드가 실행되며 질의문 결과를 출..

탐색 트리 탐색 트리란 탐색을 위한 트리 기반의 자료구조이다 삭제 연산의 3가지 경우 삭제하려는 노드가 단말(가장 마지막) 노드인 경우 삭제하려는 노드가 왼쪽이나 오른쪽 중 하나의 서브트리를 가지는 경우 (자식이 하나) 삭제하려는 노드가 2개의 서브트리를 모두 가지고 있는 경우 (자식이 둘) 이진탐색트리를 활용해 맵 클래스를 구현해보자 균형이진탐색(AVL)트리 AVL 트리는 모든 노드에서 왼쪽 서브트리와 오른쪽 서브트리의 높이 차가 1을 넘지 않는 이진탐색트리 * 평균, 최선, 최악의 경우 모두 시간 복잡도 O(logn)을 보장 탐색 연산은 기존 방식과 동일하지만 삽입/삭제 연산의 경우 균형 상태가 깨진다면 불균형 상태의 조상 노드(균형 인수 +-2)의 서브 트리들이 다시 재균형 (회전) + Red-Bl..

보호되어 있는 글입니다.

트리(Tree) 계층적인 자료의 표현에 적합한 자료 구조 ex) 조직도, 가계도 지금까지 배운 선형 자료 구조들과 다르게 비선형 자료 구조 노드의 ‘부모/자식/형제’ 관계와 ‘조상(부모 이상)/자손’ 관계가 정의된다 계층에 따라 위부터 레벨이 나눠지며 트리의 높이는 최고 레벨 값이다 더 이상 자식이 없는 노드는 단말 노드이며 그렇지 않은 노드는 비단말 노드이다 자식 노드의 수가 해당 노드의 차수이며 트리의 차수는 노드 차수들 중 최대 차수이다 이러한 노드 구조들을 통틀어 포레스트(forest)라고 한다 이진 트리 서브트리는 공집합일 수 있으며 이진 트리는 순환적으로 정의된다 트리의 각 레벨에 노드가 꽉 차있다면 포화 이진 트리이다 * 단, 완전 이진트리의 경우 마지막 레벨 h에서는 노드가 좌측부터 순서대..

B-트리 데이터가 입력되는 순서대로 쌓이는 순차 방법은 레코드들의 논리적 순서가 저장 순서와 동일 ~ 물리적 순서대로 레코드에 접근하며 파일 복사, 순차적 일괄 처리에 응용 인덱스의 종류) 기본키에 대한 인덱스라면 기본 인덱스, 아니라면 보조 인데스 레코드가 키 값 순으로 정렬되었다면 집중 인덱스, 아니라면 비집중 인데스 모든 키에 대해서 인덱스 엔트리가 있다면 밀집 인덱스, 아니라면 희소 인데스 * 인덱스 엔트리: 레코드 키 값 + 포인터 디스크에 인덱스를 만들 때, 데이터를 저장하는 탐색 트리 m-원 탐색 트리 중 모든 자식 노드가 균형을 유지하는 경우 B-트리라고 한다 B-트리의 조건) 공백이거나 높이가 1이상인 m-원 탐색 트리 루트와 리프를 제외한 내부 노트는 최소 m/2, 최대 m개의 서브트리..

보호되어 있는 글입니다.