2021 정보처리기사 실기 - 2. 데이터 입출력 구현(4)

스토리지

스토리지의 개요

- 단일 디스크로 처리할 수 없는 대용량의 데이터를 저장하기 위해 서버와 저장장치를 연결하는 기술

 

DAS(Direct Attached Storage)

- 서버와 저장장치를 전용 케이블로 직접 연결하는 방식

- 서버에서 저장장치를 관리

- 저장장치를 직접 연결하므로 속도가 빠르고 설치 및 운영이 쉬움

- 다른 서버에서 스토리지에 접근하여 사용 불가

 

NAS(Network Attached Storage)

- 서버와 저장장치를 네트워크를 통해 연결하는 방식

- 별도의 파일 관리 기능이 있는 NAS Storage가 내장된 저장장치를 직접 관리

- DAS에 비해 확장성 및 유연성이 좋음

- 서버들이 자유롭게 스토리지에 접근하여 파일 공유

 

SAN(Storage Area Network)

- DAS의 빠른 처리와 NAS의 파일 공유 장점을 혼합한 방식

- 서버와 저장장치를 연결하는 전용 네트워크를 별도로 구성

- 파이버 채널(FC) 스위치를 이용하여 네트워크를 구성

    -> 파이버 채널 : 장치 간 데이터 전송 속도를 기가바이트로 높이기 위한 네트워크 기술

- 서버나 저장장치를 광케이블로 연결하므로 처리 속도가 빠름

- 서버들이 저장장치 및 파일을 자유롭게 공유

 

DAS, NAS, SAN 비교

 

 

 

논리 데이터 모델의 물리 데이터 모델 변환

테이블 

- 데이터를 저장하는 데이터베이스의 가장 기본적인 오브젝트

 

엔티티를 테이블로 변환

- 논리 데이터 모델에서 정의된 엔티티를 물리 데이터 모델의 테이블로 변환

 

 

- 테이블과 엔티티 명칭은 동일하게 하는 것을 권고

- 테이블은 소스코드 가독성을 위해 영문명을 사용

- 표준화된 용어 사용 지향

- 변환 규칙

 

 

슈퍼타입/서브타입을 테이블로 변환

- 슈퍼타입과 서브타입은 논리 데이터 모델에서 이용되는 형태이므로 물리 데이터 모델을 설계할 때는 테이블로 변환

- 슈퍼타입 기준 테이블 변환

    -> 서브타입을 슈퍼타입에 통합하여 하나의 테이블로 만듦

    -> 데이터의 액세스가 상대적 용이

    -> 뷰를 이용하여 각각의 서브타입만을 액세스 하거나 수정할 수 있음

    -> SQL 문장 구성이 단순

    -> 디스크 저장 공간이 증가

    -> 인덱스의 효율이 떨어짐

 

 

- 서브타입 기준 테이블 변환

    -> 슈퍼타입의 속성들을 각각의 서브타입에 추가하여 서브타입들을 개별적인 테이블로 만듦

    -> 각 서브타입 속성들의 선택 사양이 명확한 경우 유리

    -> 여러 개의 테이블로 통합하므로 테이블당 크기가 감소하여 전체 테이블 스캔 시 유리

    -> 수행 속도 감사

    -> 복잡한 처리를 하는 SQL의 통합이 어려움

 

 

- 개별타입 기준 테이블 변환

    -> 슈퍼타입과 서브타입들을 각각의 개별적인 테이블로 변환

    -> 슈퍼타입과 서브타입 테이블 사이에는 각각 1:1 관계가 형성

    -> 저장공간이 상대적으로 작음

 

 

속성을 칼럼으로 변환

- 논리 데이터 모델에서 정의한 속성을 물리 데이터 모델의 컬럼으로 변환

- 일반 속성 변환

     -> 엔티티의 속성을 테이블의 각각의 컬럼으로 변환

     -> 칼럼명은 SQL 예약어 사용을 피하고 가능한 한 짧게 지정

 

관계를 외래키로 변환

- 논리 데이터 모델에서 정의된 관계는 기본키와 이를 참조하는 기본키로 변환

자료구조

자료 구조의 정의

- 프로그램에서 사용하기 위한 자료를 기억장치의 공간 내에 저장하는 방법과 자료 간의 관계, 처리 방법 등을 저장공간의 효율성 및 실행 간의 신속성을 높이기 위한 연구 분석하는 것

 

자료 구조의 분류

- 배열

    -> 동일한 자료형의 데이터들이 같은 크기로 나열되어 순서를 갖고 있는 집합

    -> 첨자를 이용하여 데이터에 접근

    -> 첨자의 개수에 따라 n차원 배열이라 부름

- 선형 리스트

    -> 일정한 순서에 의해 나열된 자료 구조

    -> 연속 리스트

        * 배열을 이용한 선형 리스트

        * 중간에 데이터를 삽입하기 위해 연속된 빈 공간이 있어야 하며 삽입, 삭제 시 자료의 이동 필요

    -> 연결 리스트

        * 자료 항목의 순서에 따라 노드의 포인터 부분을 이용하여 서로 연결시킨 자료 구조  

        * 연결을 위한 포인터를 찾는 시간이 필요해 접근 속도가 느림

        * 노드의 삽입 삭제 작업이 용이

        * 노드 부분 때문에 연속 리스트에 비해 기억 공간의 효율이 좋지 않음 

노드

- 스택

    -> 리스트의 한쪽으로 자료의 삽입, 삭제가 이루어짐

    -> LIFO(Last In First Out)의 구조를 가지고 있음

    -> 오버플로우(overflow) : 기억 공간이 모두 차있는 상태에서 데이터를 삽입하면 일어나는 현상

    -> 언더플로우(underflow) : 기억 공간이 비어있는 상태에서 데이터를 삭제하면 일어나는 현상 

    -> Top : 스택에 가장 마지막으로 삽입된 자료의 위치

    -> Bottom : 스택의 가장 바닥

스택

- 큐

    -> 리스트의 한쪽에서는 삽입 다른 한쪽에서는 삭제가 이루어짐

    -> FIFO(First In First Out)의 구조를 가지고 있음

    -> F(Front) : 먼저 삽입된 자료의 기억 공간을 가르키는 포인터

    -> R(Rear) : 마지막에 삽입된 자료의 기억 공간을 가르키는 포인터

- 트리

    -> 노드와 가지를 이용하여 사이클이 없이 구성한 그래프의 특수 형태

    -> 디그리 : 노드에서 뻗어나온 가지의 개수

    -> 단말노드 / 잎 노드 : 자식이 없는 노드

    -> 트리의 디그리 : 노드들의 디그리 중 가장 많은 수

정렬

버블 정렬

- 인접한 두 요소를 비교하면서 오름차순/내림차순에 따라 값을 뒤로 보냄

- 오름차순 : 큰 값을 뒤로 보냄

- 내림차순 : 작은 값을 뒤로 보냄

- 마지막까지 비교했다면 맨 뒤를 제외하고 다시 반복하는 방식으로 정렬될때까지 반복

- 버블정렬의 시간복잡도 : 4개를 기준으로 3번, 2번, 1번 진행이 됨

 

선택 정렬

- 정렬할 결과를 담을 공간을 따로 마련해놓고 정렬 대상에서 처음부터 끝까지 조회해서 가장 작은(큰) 값을 정렬 결과 공간에 옮기는 정렬법

- 위 방법은 메모리 공간을 따로 요구한다는 단점이 있어 아래와 같이 개선

- 처음부터 끝까지 조회해서 가장 작은 값을 가장 앞으로 이동(교환)

- 가장 앞은 이미 만족했으니 그 뒤부터 가장 끝까지 조회하는 방식으로 반복

- 선택 정렬의 시간복잡도 : 4개를 기준으로 3번, 2번, 1번 진행이 됨

    -> 최악의 경우 최상의 경우 이동의 연산은 동일하게 수행되고 바깥쪽 for문에 있기에 비교 연산보다 적기때문에 비교 연산보다 중요도가 떨어짐

 

삽입 정렬

- 정렬이 된 영역과 정렬이 안된 영역을 나눔

- 순차적으로 정렬이 안된 영역에서 정렬이 된 영역으로 넘겨주고 넘겨줄때 이미 정렬이 되어있는 영역과 비교하여 저장

- 정렬이 안된 영역에서 정렬이 된 영역으로 넘길 때 정렬 위치에 데이터를 옮기면 데이터는 한칸씩 뒤로 옮겨야 함

- 옮길 위치를 찾고 해당 위치부터 뒤로 한칸씩 옮기는 연산이 필요한데 구분을 지어 구현하기보다 하나로 묶는게 편의성을 높일 수 있음

- 정렬된 영역의 뒤부터 하나씩 비교하면서 아니라면 뒤로 한칸 옮기고 맞다면 그 위치에 삽입하는 방식으로 구현

- 삽입 정렬의 시간복잡도 : 버블과 삽입과 마찬가지

 

힙 정렬

- 힙의 특성을 이용해서 데이터를 힙에 넣고 그대로 꺼내서 정렬을 시키는 방법

- 힙에 데이터를 넣을 때 우선순위를 기반으로 데이터를 넣기 때문에 그대로 이용하면 됨

- 힙 정렬의 시간 복잡도

    -> 데이터 저장, 삭제의 시간 복잡도

    -> 데이터 n개를 넣고 빼는데 걸리는 시간 복잡도

    -> n앞의 상수는 생략하므로 결국

 

병합 정렬

- Divide and Conquer(분할 정복) 알고리즘을 기반으로 하는 정렬

- 데이터를 한번에 정렬하지 않고 분할하여 정렬하고 다시 합치는 방법

- 데이터를 정렬하기 쉬운 단계까지 분할하는 것이 효율적

    -> 데이터가 1개가 될 때까지 분할

- 다시 합칠 때 정렬을 위한 연산을 수행

- 1단계 : fIdx가 mid를 넘거나 rIdx가 right의 값을 넘을때까지 진행

- 2단계 : 남아있는 영역의 데이터를 옮김

- 병합 정렬의 시간 복잡도

     -> 병합 정렬은 분할의 과정보다는 병합의 과정의 연산이 더 중요

     -> 데이터가 8개일 경우 3단계를 거쳐 병합을 완료함

     -> 하나의 단계에서 최대 병합하고자 하는 데이터만큼 비교 연산을 진행

     -> 데이터를 sortArr로 이동시키고 다시 arr로 이동

퀵 정렬

- 1단계(초기화)

- 퀵정렬을 위해서는 left / right / low / high / pivot이 필요

    -> left, right : 데이터의 시작과 끝

    -> pivot : 중심점, 기준

    -> low, high : pivot을 제외한 다음 위치

- 2단계(low와 high의 이동)

    -> low : 피벗보다 정렬의 우선순위가 낮은 데이터를 만날 때까지 이동

    -> high : 피벗보다 정렬의 우선순위가 높은 데이터를 만날 때까지 이동

    -> low와 high 이동은 별개

- 3단계(low와 high의 교환)

    -> 2단계의 low와 high위치의 데이터를 교환

    -> low와 high가 역전할 때 까지 계속 이동

- 4단계(pivot의 이동)

    -> 3단계를 실행함으로써 high 다음의 데이터들은 pivot보다 우선순위가 낮음을 확인했음

        * high가 내려오면서 우선순위가 높은것들은 자리를 바꿨음

    -> high의 데이터와 pivot의 데이터를 교환

    -> 그럼으로써 pivot의 데이터는 자리를 잡고 pivot의 데이터를 기준으로 좌우측은 섞일 필요가 없어짐

    -> 이제 pivot의 데이터(high 위치)를 기준으로 좌우측으로 나누어서 위의 단계를 반복

        * left가 right보다 커질때 까지 반복 => 더이상 쪼갤 영역이 없음

 

- 퀵 정렬의 시간 복잡도

    -> 최선의 경우 : 피벗이 제대로 선택된 경우

        * 데이터가 8개일 경우 3번에 거쳐서 나눠지면서 정렬이 진행

        * low와 high가 이동될때마다 pivot과 비교

    -> 최악의 경우 : 피벗이 제대로 선택되지 못한 경우

실기 정리

2021 정보처리기사 실기 정리