CS

[자료구조] 연결 리스트(Linked List) 1. 정의 포인터를 사용하여 여러 개의 노드를 연결하는 자료 구조 배열의 단점(데이터 추가, 삭제시 shift 비용 발생)을 해결 각각의 노드들은 다음 노드를 가리키는 포인터, 자신의 값을 가지고 있는 데이터를 가리키는 포인터 2개로 구성 마지막 노드의 다음 노드는 없으므로 null을 가리키게 된다. head라는 포인터는 첫번째 노드의 주소를 가지고 있다. 힙에서는 연결 리스트의 head만 알고 있기 때문에 head.next를 이용하여 연결리스트를 탐색한다. 1.1 배열과 비교 배열 논리적 저장 순서와 물리적 저장 순서가 일치 찾고자 하는 원소의 인덱스를 알고 있으면 O(1)으로 원소에 접근 가능 → Random Access 가능 삭제와 삽입시 빈 공간이 ..

[자료구조] 스택과 큐 1. 정의 1. 스택 Stack : 쌓는다는 의미 → 차곡차곡 쌓는 자료구조 LIFO : Last In First Out 구조 top에 있는 자료가 가장 최신의 자료 한쪽에서 자료의 삽입과 삭제가 반복 됨 1.2 큐 Queue : 줄서서 기다린다는 의미 → 먼저 들어오는게 먼저 나가는 자료 구조 FIFO : First In First Out 구조 큐의 양끝에서 자료 추가와 삭제가 이루어짐 2. 구현 2.1 스택 class Stack { static class Node { private T data; private Node next; public Node(T data) { this.data = data; } } private Node top; //데이터 제거 public T pop(..

Chapter14 트랜잭션 이 글은 기초가 든든한 데이터 베이스를 참조하여 작성했습니다. 1. 트랜잭션 개념 데이터에이스 내에서 하나의 논리적 기능을 수행하기 위해 행해지는 한꺼번에 사용되는 하나 이상의 쿼리를 모아 놓은 쪼갤 수 없는 작업의 논리적인 단위 2. 트랜잭션의 ACID 특성 Atomicity(원자성) Consistency(일관성) Isolation(고립성 또는 격리성) Durability(지속성 또는 영속성) 2.1 원자성(Atomicity) 분해가 불가능한 최소의 단위인 원자처럼 동작 All or Nothing 작업 수행이 시작되면 트랜잭션 내의 모든 연산들은 반드시 전체가 완전이 수행되어야 함(All) 어느 하나라도 수행이 실패하면 어떠한 연산도 수행되지 않는 상태로 돌아감(Nothing..

Chapter12 정규화 이 글은 기초가 든든한 데이터 베이스를 참조하여 작성했습니다. 이상 현상(anomaly) 테이블을 수정할 때 데이터의 일관성이 깨지는 현상 데이터를 삽입할 때 불필요한 NULL이 삽입되거나, 삭제시 연쇄 삭제 현상이 발생하는 것 1.1 삽입 이상 데이터 삽입 시 특정 열에 해당하는 값이 없어서 필요하지 않은 NULL을 강제로 입력해야 하는 현상 1.2 삭제 이상 데이터 삭제 시 유용한 다른 데이터까지 함께 삭제되는 현상 → 연쇄 삭제 1.3 수정 이상 중복 데이터 중에서 일부만 수정되어 데이터의 불일치 문제가 발생하는 현상 2. 정규화(normalization) 이상 현상이 발생하는 테이블의 설계를 수정하여 정상으로 만드는 과정 → 정규화가 된 테이블이 특정한 제약 조건을 만족하..

Chapter11 ER모델(Entity-Relationship Model) 이 글은 기초가 든든한 데이터 베이스를 참조하여 작성했습니다. ER 모델의 개념 개념적 데이터 모델로써, 개체 집합, 속성 집합, 그리고 개체 집합 간의 관계 집합을 표현한 것이다. 1.1 집합과 원소 집합 : 어떤 주어진 조건에 의하여 그 대상을 분명히 알 수 있는 것들의 모임 원소 : 원소를 구성하는 대상 하나 하나를 그 집합의 원소라고 함 1.2 ER 모델 개체와 그들 간의 관계를 이용하여 현실세계를 개념적 구조로 표현하는 방법 개체와 개체 간의 관계를 ERD(ER Diagram)으로 표현 직사각형, 타원, 마름모 세 개의 도형으로 직관적인 그림으로 표현 2. ER 모델의 구성요소 2.1 개체 독립적으로 존재하며, 서로 구별..

Chapter4 관계 대수 이 글은 기초가 든든한 데이터 베이스를 참조하여 작성했습니다. 1. 관계 대수 릴레이션을 처리하는 연산의 집합 2. 일반 집합 연산자 2.1 합집합 연산자 두 개의 릴레이션을 합하여 하나의 릴레이션을 반환 2.2 교집합 연산자 두 릴레이션 모두에 속한 투플들을 반환 2.3 차집합 연산자 R - S : R릴레이션에는 속하지만 S릴레이션에 속하지 않는 투플들로 결과 릴레이션 구성 2.4 카티션 프로덕트 연산자 릴레이션 R과 릴레이션 S의 카티션 프로덕트는 릴레이션 R에 속한 투플들과 릴레이션 S에 속한 투플들의 모든 연결 가능한 조합으로 구성되는 릴레이션 3. 순서 관계 연산자 3.1 순수 관계 연산자 3.1.1 셀렉션 연산자 하나의 릴레이션에서 주어진 조건을 만족하는 투플들을 선..

Chapter3 관계 데이터 모델과 제약조건 이 글은 기초가 든든한 데이터 베이스를 참조하여 작성했습니다. 1. 관계 데이터 모델 1.1 릴레이션 개념 관계 데이터 모델에서 정보를 저장하는 구조 행과 열로 구성된 2차원 형태의 테이블 구조 1.2 릴레이션 관련 용어 속성 : 릴레이션의 열 투플 : 릴레이션의 행 도메인 : 하나의 속성의 가질 수 있는 값들의 집합 NULL : 특정 속성에 대한 값을 알 수 없어서 입력하지 못하는 경우 1.3 릴레이션 스키마와 인스턴스 릴레이션 스키마 : 한 개의 릴레이션의 논리적인 구조를 정의한 것으로 릴레이션의 이름과 릴레이션에 포함된 속성들의 집합 기본키는 밑줄로 표현 속성의 개수를 그 릴레이션의 차수(degree)라고 함 릴레이션 인스턴스 : 어느 한 시점의 릴레이션..

Chapter2 데이터 모델 이 글은 기초가 든든한 데이터 베이스를 참조하여 작성했습니다. 1. 데이터모델 1.1 개념 데이터베이스의 구조를 단순화, 추상화하여 체계적으로 표현하는데 사용하는 도구로써 그래픽적으로 구현한다. 1.2 구성요소 데이터구조 : 데이터베이스에서 표현될 대상과 그들 간의 관계에 대한 명세, 주로 정적인 특징 연산 : 데이터 구조에 따라 실제 값들을 처리하는 작업에 대한 명세, 데이터 조작 기법, 동적인 특징 제약조건 : 무결한 데이터 저장을 위한 데이터 조작 한계에 대한 규정 1.3 종류 개념적 모델 데이터베이스의 논리적 구조를 명시 사용자가 인식하는 것과 유사하게 표현 ex) ER(Entity - Relationship) 모델 논리적 모델 개념적 구조를 컴퓨터가 이해할 수 있는 ..