음 아마 비둘기보단 똑똑할꺼야


1. 알고리즘 기본개념

1) 알고리즘 생성단계
    설계 > 표현/기술 > 정확성 검증 > 효율성 분석

2. 기본 자료구조

1) 알고리즘에서 자료구조는?

1-1) 자료구조
    - 컴퓨터 기억공간 내에 자료를 표현하고 조직화 하는 방법
    - 프로그램 = 자료구조 + 알고리즘
    - 자료구조에 대한 고려 없는 효율적인 알고리즘의 선택, 또는 알고리즘에 대한 고려 없는 효율적인 자료구조의 선택은 무의미

기본 자료구조 =

배열, 연결리스트 , 스택 , 큐 , 트리 , 그래프

선형 자료구조 : 배열 , 연결리스트 , 스택 , 큐
    ㄴ 데이터에 순서가 있다.
비선형 자료구조 : 트리, 그래프
    ㄴ 데이터에 순서가 없다.


2) 배열

정의: 같은 자료형을 갖는 여러 개의 데이터를 하나의 변수에 저장해놓고 각각의 원소에 접근할 때에는 인덱스 첨자를 사용해서 접근하는 자료구조

특징: 논리적인 순서와 물리적인 순서가 같다.

단점: 삽입과 삭제가 발생하게되면 순서를 유지하기 위해서 자리의 이동이 불가피하다.

장점: 배열은 인덱스를 가지고 해당 원소에 직접접근하는 특징을 가지고 있다. 배열은 데이터가 어디에 저장되어있든지 어디로든 접근의 시간이 동일하다.

3) 연결리스트

하나의 원소는 노드라고 한다. 데이터가 들어가는 곳을 필드라고 한다.
하나의 노드는 하나의 데이터필드와 하나의 링크필드로 표현된다.

특징: 논리적순서와 물리적인순서가 같지 않다. 링크필드의 의미는 다음 노드의 메모리 주소값을 저장하고 있다.

장점: 삽입과 삭제가 간단하다.

단점: 특정 데이터를 찾아갈때는 처음부터 찾아가야 한다는 단점이 있다.


2-1,3-1) 배열과 연결리스트의 종류

배열 : 1차원 2차원 다차원배열

연결리스트: 단일 연결, 단일 원형 연결, 이중 연결, 이중 원형 연결

주어진 문제에 따라 자료구조를 선택해야 함.

접근을 빨리 하고싶으면 배열을 쓰는게 좋고 데이터의 접근보다는 데이터의 삽입과 삭제가 많다면 연결리스트 사용이 효과적일 수 있다.


4) 스택

정의: LIFO (Last In First Out) 후입선출 입구와 출구가 하나밖에 없는 구조

top : 스택에 데이터가 어디까지 쌓여져 있는가를 알림.

push: 삽입하는 연산

pop: 삭제하는 연산

데이터가 삽입 삭제때마다 top이 가리키는 위치가 달라짐.

5) 큐

정의: FIFO (First In FIrst Out) 선입선출 입구와 출구가 정방향

front: 삭제와 관련

rear: 삽입과 관련

삽입이 이뤄질경우 rear가 가리키는 값이 바뀜.

삭제가 이뤄질경우 front가 가리키는 값이 바뀜.


6) 트리

정의: 하나 이상의 노드로 구성된 유한 집합 T

조건1: T의 원소 가운데 단 하나의 루트 노드가 존재
조건2: 루트 노드를 제외한 나머지 노드는 n개의 서로 분리된 부분집합 T1, T2, TN(서브트리) 으로 나누어진다

주요 용어:

차수

리프노드(단말노드)

부모,자식,형제 노드

조상(선조) 후손(자손)

레벨 높이 깊이

6-1) 이진트리

정의: 각 노드의 차수가 2이하인 순서 트리

특성:
    - 레발 i에서 최대 노드의 개수 = 2의 i승
    - 높이 h에서 이진 트리의 최대 노드의 개수 = 2의 h승 - 1
    - 단말 노드(자식이 없는 노드)의 수 n0 = 차수가 2인 노드의 수에 +1 하면 된다. 
        n0 = n2 + 1

종류:
    - 포화 이진트리 : 높이 h 까지 중간에 빈 자리 없이 꽉 차있는 트리
    - 전 이진트리: 각 노드의 차수 = 0 이거나 2. 전 노드의 차수가 1인 경우가 없는 트리
    - 완전 이진트리: 노드의 레벨의 마지막 레벨 전까지가 포화 이진트리이고 마지막 레벨의 노드들이 왼쪽에서부터 마지막까지 중간에 빠짐없이 채워져있는 트리
    - 균형 이진트리: 왼쪽 서브트리와 오른쪽 서브트리의 노드레벨 차이가 1 이내인 트리

구현:
      * 배열을 이용하는 방법

* 연결리스트를 이용하는 방법

7) 그래프

정의: 그래프 G=(V,E)
    V: 정점의 집합, E: 간선의 집합

간선이 방향성이 있느냐에 따라 무방향과 방향그래프로 나뉜다.

각 정점을 잇는 선이 간선이다.

간선들에 값을 줄 수 있다. 비용이라 칭함. 간선들에 비용이 있는 그래프를 가중그래프(가중치그래프)라 한다.

7-1) 무방향 그래프

간선의 표현: (1,2) = (2,1)

그래프 표현: V(G) = { 1,2,3,4,5 } , E(G) = { (1,2),(1,3),(2,4),(3,5) }

7-2) 방향 그래프

간선의 표현: <1,2>


주요 용어:

인접,부수, 부분그래프, 경로, 경로의 길이, 차수(방향그래프 > 진입 차수 , 진출 차수), 단순 경로, 사이클, 루프, 연결, 강력 연결

구현

1) 인접 행렬

2) 인접 리스트

2018/05/15 - [방송통신대학교/컴퓨터과학과 [3학년 1학기]] - [데이터베이스] 5강 정규화 기초

2018/03/21 - [방송통신대학교/컴퓨터과학과 [3학년 1학기]] - [데이터베이스] 4강 데이터베이스 언어

2018/03/19 - [방송통신대학교/컴퓨터과학과 [3학년 1학기]] - [데이터베이스] 3강 관계형 모델

2018/03/16 - [방송통신대학교/컴퓨터과학과 [3학년 1학기]] - [데이터베이스] 2강 데이터베이스 모델링

2018/03/16 - [방송통신대학교/컴퓨터과학과 [3학년 1학기]] - [데이터베이스] 1강 데이터베이스의 이해

1. 데이터베이스의 개념

사용: 은행 항공 대학 등등등등 많다

데이터베이스가 없으면 원하는 자료를 찾는데 소요되는 비용이 너무 크다. 

1) 파일처리시스템
    DB가 개발되기전에 데이터관리에 사용
    업무 별 작성되는 각각의 어플리케이션이 개별적으로 자신의 데이터를 케어하는 시스템

    1-1) 데이터 종속의 문제
        저장된 데이터가 특정 HW 또는 SW에서만 사용될수 있도록 제한되는 문제
        - 물리적 데이터 독립성
        - 논리적 데이터 독립성

    1-2) 데이터 중복의 문제
        동일한 사항에 대한 데이터를 복수 개 저장할 경우 일관성, 보안성, 경제성 측면에서 문제 발생
        - 일관성: 한가지 사실에 대해 한 개의 데이터 값을 유지
        - 보안성: 같은 데이터에 같은 수준의 보안 유지
        - 경제성: 데이터에 대해 최소한의 저장 공간 만을 점유

    1-3) 무결성 훼손의 문제
        실세계의 데이터는 어떤 현상에 대한 값을 유지하고 있을 뿐만 아니라 데이터가 가질 수 있는 기능범위를 포함
        - 현상에 대한 값의 예: '홍길동'의 수강과목
        - 가능 범위의 예: 1학기 최대 수강과목 18학점
        데이터 무결성
        - 데이터의 정확성 보장
        - 데이터의 값과 값에 대한 제약조건을 동시에 만족
        파일 시스템은 데이터 무결성을 보장하기 위한 기능을 제공하지 않음

    1-4) 동시접근의 문제
        동일 데이터에 다수 사용자의 접근 허용 시 일관성이 훼손

2. 특징

DB 관련 용어
    데이터: 어떠한 사실에 대한 정량적, 정성적 특징을 나타낼 수 있는 값과 값에 대한 설명
    데이터베이스: 특정 기관의 애플리케이션 시스템에서 사용되는 데이터의 집합
    DBMS: 데이터베이스에 저장된 데이터의 구성, 저장, 관리, 사용을 위한 소프트웨어 패키지
    데이터베이스 시스템: 정보를 데이터베이스에 저장, 관리하여 사용장게 요구된 형태의 정보로 제공하는 컴퓨터 기반 시스템

데이터베이스 사용의 의미
    이전의 파일처리시스템에서의 데이터사용과 데이터관리를 DBMS를 통해 이원화 시킨것.

특성)

DB 시스템의 자기 기술성
 - 설명(메타데이터)을 포함
프로그램과 데이터의 격리 및 추상화
 - 사용제에게 개념적인 표현을 제공하여 접근성을 향상
다중 뷰 제공
 - 각 사용자가 관심을 갖은 데이터베이스의 일부만을 표현할 수 있는 기능 제공
다수 사용자 트랜잭션 처리
 - 동시성 제어 기능

값, 데이터, 메타데이터의 차이)

12
값: 숫자 12의 순수한 의미
데이터: 숫자 12와 어떤것을 의미 하는지에 대한 설명 (오늘일자 낮 최고기온)
메타데이터: 숫자 12의 설명 (오늘일자 낮 최고기온)

DBMS의 구조)
    개념적 > 논리적 > 물리적

3. 모델

개념)
    사용 가능한 데이터만을 선별하여 구조화된 DB에 저장 사용할 방법이 필요
    데이터모델: 관계형, ER, 객체지향적 모델 등

1) ER(entity-relationship model) 모델
    실세계 인식에 기초하여 실세계의 객체(object)를 나타내는 개체(entity)들과 개체들간의 관계(relationship)로 구성

2) 관계형(relational model) 모델
    릴레이션이라고 하는 표 형태의 구조를 사용하여 데이터를 저장, 관리하는 모델

관계형 모델로 가기전에 ER 모델을 사용한 후 관계형으로 진행된다.

4. 구성요소

1) DB 언어

1-1) 개념: DBMS는 사용자가 DB를 쉽게 사용하고 다룰 수 있도록 언어 형태의 인터페이스를 제공
                역할에 따라 종류의 언어로 구분 데이터정의언어(DDL) , 데이터조작언어(DML)
            현대 DB언어는 자연어와 유사한 형태의 SQL로 표준화

1-2) 데이터정의언어 DDL (Data Definition Language)
        DB 스키마를 정의하기 위한 언어

1-3) 데이터조작언어 DML(Data Manipulation Language)
        구조화된 데이터에 사용자가 접근 및 조작할 수 있도록 지원하는 언어(검색,삽입,삭제,수정)

5. 시스템 아키텍처

1) 개념

1-1) 중앙집중식 방식
        - 단일 서버가 다수의 클라이언트 장치를 대신하여 작동
        - 중앙 컴퓨터의 과부하로 전체적인 성능 저하

1-2) 분산시스템 방식
        - 클라이언트 장치의 성능 향상으로 자체적인 처리 능력 보유
        - 클라이언트-서버 데이터베이스 시스템

* 클라이언트 - 서버 구조
2 tier: 사용자, 애플리케이션, 데이터베이스
3 tier: 사용자, 애플리케이션 클라이언트, 애플리케이션 서버, 데이터베이스 

© 2015 Jundol in 음 아마 비둘기보단 똑똑할꺼야
Designed by DH / Powered by Tistory
141 / 31 / 88,151