[정보처리기사] 데이터 입/출력 구현

Juni_woo·2025년 3월 20일
데이터 입출력 구현정보처리기사
0

정보처리기사

목록 보기
2/12
post-thumbnail

스키마

  • 데이터베이스의 구조와 제약조건에 관한 전반적인 명세를 기술한 것이다.
  • 외부 스키마
    • 사용자나 응용프로그래머가 각 개인의 입장에서 필요로 하는 데이터베이스의 논리적 구조를 정의한 것.
  • 개념 스키마
    • 데이터베이스의 전체적인 논리적 구조
    • 모든 응용 프로그램이나 사용자들이 필요로 하는 데이터를 종합한 조직 전체의 데이터베이스로, 하나만 존재함.
  • 내부 스키마
    • 물리적 저장장치의 입장에서 본 데이터베이스 구조
    • 실제로 저장될 레코드의 형식, 저장 데이터 항목의 표현 방법, 내부 레코드의 물리적 순서 등을 나타냄

데이터베이스 설계 순서

1. 요구조건 분석
- 요구 조건 명세서 작성
2. 개념적 설계
- 개념 스키마, 트랜잭션 모델링, E-R 모델
3. 논리적 설계
- 목표 DBMS에 맞는 논리 스키마 설계, 트랜잭션 인터페이스 설계
4. 물리적 설계
- 목표 DBMS에 맞는 물리적 구조의 데이터로 변환
5. 구현
- 목표 DBMS의 DDL(데이터 정의어)로 데이터베이스 생성, 트랜잭션 작성


개념적 설계

  • 개념적 설계(정보 모델링, 개념화)는 정보의 구조를 얻기 위하여 현실 세계의 무한성과 계속성을 이해하고, 다른 사람과 통신하기 위하여 현실 세계에 대한 인식을 추상적 개념으로 표현한 과정이다.
  • 개념적 설계에서는 개념 스키마 모델링과 트랜잭션 모델링을 병행 수행한다.
  • 개념적 설계에서는 요구 분석에서 나온 결과인 요구 조건 명세를 DBMS에 독립적인 E-R 다이어그램으로 작성한다.

논리적 설계

  • 논리적 설계는 현실 세계에서 발생하는 자료를 컴퓨터가 이해하고 처리할 수 있는 물리적 저장장치에 저장할 수 있도록 변환하기 위해 특정 DBMS가 지원하는 논리적 자료 구조로 변환시키는 과정이다.
  • 개념 세계의 데이터를 필드로 기술된 데이터 타입과 이 데이터 타입들 간의 관계로 표현되는 논리적 구조의 데이터로 모델화한다.
  • 개념적 설계각 개념 스키마를 평가 및 정제하고 DBMS에 따라 서로 다른 논리적 스키마를 설계하는 단계이다.

물리적 설계

  • 물리적 설계는 논리적 설계에서 논리적 구조로 표현된 데이터를 디스크 등의 물리적 저장장치에 저장할 수 있는 물리적 구조의 데이터로 변환하는 과정이다.
  • 물리적 설계에서는 다양한 데이터베이스 응용에 대해 처리 성능을 얻기 위해 데이터베이스 파일의 저장 구조 및 액세스 경로를 결정한다.
  • 저장 레코드의 형식, 순서, 접근 경로, 조회 집중 레코드 등의 정보를 사용하여 데이터가 컴퓨터에 저장되는 방법을 묘사한다.

데이터 모델

  • 데이터 모델은 현실 세계의 정보들을 컴퓨터에 표현하기 위해서 단순화, 추상화아여 체계적으로 표현한 개념적 모형이다.
  • 데이터 모델에 표시할 요소
요소내용
구조(Structure)논리적으로 표현된 개체 타입들 간의 관계로서 데이터 구조 및 정적 성질 표현
연산(Operation)데이터베이스에 저장된 실제 데이터를 처리하는 작업에 대한 명세로서 데이터베이스를 조작하는 기본 도구
제약 조건(Constraint)데이터베이스에 저장될 수 있는 실제 데이터의 논리적인 제약 조건

E-R 다이어그램

  • 사각형: 개체 타입
  • 마름모: 관계 타입
  • 타원: 속성
  • 이중 타원: 다중값 속성
  • 밑줄 타원: 기본키 속성
  • 복수 타원: 복합 속성
  • 관계: 1:1, 1:N, N:M 등의 개체 간 관계에 대한 대응수를 선 위에 기술함
  • 선, 링크: 개체 타입과 속성을 연결

관계형 데이터베이스의 릴레이션 구조

  • 릴레이션은 데이터들을 표의 형태로 표현한 것으로 구조를 나타내는 릴레이션 스키마와 실제 값들인 릴레이션 인스턴스로 구성된다.
  • 릴레이션 인스턴스: 데이터 개체를 구성하고 있는 속성들에 데이터 타입이 정의되어 구체적인 데이터 값을 가진 것을 의미함

튜플

  • 튜플은 릴레이션을 구성하는 각각의 행을 말한다.
  • 튜플은 속성의 모임으로 구성된다.
  • 파일 구조에서 레코드와 같은 의미이다.
  • 튜플의 수를 카디널리티 또는 기수, 대응수라고 한다.

속성

  • 속성은 데이터베이스를 구성하는 가장 작은 논리적 단위이다.
  • 파일 구조상의 데이터 항목 또는 데이터 필드에 해당된다.
  • 속성은 개체의 특성을 기술한다.
  • 속성의 수를 디그리 또는 차수라고 한다.

도메인

  • 도메인은 하나의 애트리뷰트가 취할 수 있는 같은 타입의 원자값들의 집합이다.
  • 도메인은 실제 애트리뷰트 값이 나타날 때 그 값의 합법 여부를 시스템이 검사하는 데에도 이용된다.

후보키

  • 후보키는 릴레이션을 구성하는 속성들 중에서 튜플을 유일하게 식별하기 위해 사용되는 속성들의 부분집합이다.
  • 기본키로 사용할 수 있는 속성들을 말한다.
  • 후보키는 유일성과 최소성을 모두 만족시켜야 한다.
  • 유일성: 하나의 키 값으로 하나의 튜플만을 유일하게 식별할 수 있어야 함.
  • 최소성: 키를 구성하는 속성 하나를 제거하면 유일하게 식별할 수 없도록 꼭 필요한 최소의 속성으로 구성되어야 함.

대체키

  • 대체키는 후보키가 둘 이상일 때 기본키를 제외한 나머지 후보키를 의미한다.
  • 대체키를 보조키라고도 한다.

슈퍼키

  • 슈퍼키는 한 릴레이션 내에 있는 속성들의 집합으로 구성된 키를 말한다.
  • 릴레이션을 구성하는 모든튜플 중 슈퍼키로 구성된 속서의 집합과 동일한 값은 나타나지 않는다.
  • 슈퍼키는 릴레이션을 구성하는 모든 튜플에 대해 유일성은 만족하지만, 최소성은 만족하지 못한다.

외래키

  • 외래키는 다른 릴레이션의 기본키를 참조하는 속성 또는 속성들의 집합을 의미한다.
  • 한 릴레이션에 속한 속성 A와 참조 릴레이션의 기본키인 B가 동일한 도메인 상에서 정의되었을 때의 속성 A를 외래키라고 한다.
  • 외래키로 지정되면 참조 릴레이션의 기본키에 없는 값은 입력할 수 없다.

무결성

  • 무결성은 데이터베이스에 저장된 데이터값과 그것이 표현하는 현실세계의 실제값이 일치하는 정확성을 의미한다.
  • 개체 무결성: 기본 테이블의 기본키를 구성하는 어떤 속성도 Null 값이나 중복값을 가질 수 없다는 규정
  • 참조 무결성: 외래키 값은 Null이거나 참조 릴레이션의 기본키 값과 동일해야 함. 즉 릴레이션은 참조 할 수 없는 외래키 값을 가질 수 없다는 규정

관계대수

  • 관계대수는 관계형 데이터베이스에서 원하는 정보와 그 정보를 검색하기 위해서 어떻게 유도하는가를 기술하는 절차적인 언어이다.
  • 관계대수는 릴레이션을 처리하기 위해 연산자와 연산규칙을 제공하며, 피연산자와 연산 결과가 모두 릴레이션인다.
  • 관계대수는 질의에 대한 해를 구하기 위해 수행해야할 연산의 순서를 명시한다.

순수 관계 연산자

  • Select
    • 릴레이션에 존재하는 튜플 증에서 선택 조건을 만족하는 튜플의 부분집합을 구하여 새로운 릴레이션을 만드는 연산이다.
    • 릴레이션의 행에 해당하는 튜플을 구하는 것이므로 수평 연산이라고도 한다.
    • 기호: σ
  • Project
    • 주어진 릴레이션에서 속성 리스트에 제시된 속성 값만을 추출하여 새로운 릴레이션을 만드는 연산이다.
    • 릴레이션의 열에 해당하는 속성을 추출하는 것이므로 수직 연산자라고도 한다.
      -기호: π
  • Join
    • 공통 속성을 중심으로 두 개의 릴레이션을 하나로 합쳐서 새로운 릴레이션을 만드는 연산히다.
    • Join의 결과는 Cartesian Product(교차곱)을 수행한 다음 Select를 수행한 것과 같다.
    • 기호: ⨝
  • Division
    • X ⊃ Y인 두 개의 릴레이션 R과 S가 있을 때, R의 속성이 S의 속성값을 모두 가진 튜플에서 S가 가진 속성을 제외한 속성만을 구하는 연산이다.
    • 기호: ÷

일반 집합 연산자

  • 합집합(UNION)
    • 두 릴레이션에 존재하는 튜플의 합집합을 구하되, 결과로 생성된 릴레이션에서 중복되는 튜플은 제가되는 연산이다.
    • 합집합의 카디널리티는 두 릴레이션 카디널리티의 합보다 크지 않다.
    • 기호: ⋃
  • 교집합(INTERSECTION)
    • 두 릴레이션에 존재하는 튜플의 교집합을 구하는 연산이다.
    • 교집합의 카디널리티는 두 릴레이션 중 카디널리티가 적은 릴레이션의 카디널리티보다 크지 않다.
    • 기호: ⋂
  • 차집합(DIFFERENCE)
    • 두 릴레이션에 존재하는 튜플의 차집합을 구하는 연산이다.
    • 차집합의 카디널리티는 릴레이션 R의 카디널리티보다 크지 않다.
    • 기호: —
  • 교차곱(CARTESIAN PRODUCT)
    • 두 릴레이션에 있는 튜플들의 순서쌍을 구하는 연산이다.
    • 교차곱의 디그리는 두 릴레이션의 디그리를 더한 것과 같고, 카디널리티는 두 릴레이션의 카디널리티를 곱한 것과 같다.
    • 기호: ×

관계해석

  • 관계해석은 관계 데이터의 연산을 표현하는 방법이다.
  • 관계 데이터 모델의 제안자은 코드가 수학의 Predicate Calculus에 기반을 두고 관계 데이터베이스를 위해 제안했다.
  • 관계해석은 원하는 정보가 무엇이라는 것만 정의하는 비절차적 특성을 지닌다.
  • 원하는 정보를 정의할 때는 계산 수식을 사용한다.

이상

  • 이상(Anomaly)이란 데이터베이스 내에 데이터들이 불필요하게 중복되어 릴레이션 조작 시 예기치 않게 발생하는 곤란한 현상을 의미한다.
  • 삽입 이상(Insertion Anomaly): 테이블에 데이터를 삽입할 떄 의도와는 상관없이 원하지 않은 값들로 인해 삽입할 수 없게 되는 현상.
  • 삭제 이상(Deletion Anomaly): 테이블에서 튜플을 삭제할 때 의도와는 상관없는 값들도 함께 삭제되는, 즉 연쇄 삭제가 발생하는 현상.
  • 갱신 이상(Update Anomaly): 테이블에서 튜플에 있는 속성 값을 갱신할 때 일부 튜플의 정보만 갱신되어 정보에 불일치성이 생기는 현상.

함수적 종속

  • 함수적 종속(Functional Dependency)
    • 어떤 테이블 R에서 X와 Y를 각각 R의 속성 집합의 부분 집합이라 하자. 속성 X의 값 각각에 대해 시간에 관계없이 항상 속성 Y의 값이 오직 하나만 여관되어 있을 때 Y는 X에 함수적 종속 또는 X가 Y를 함수적으로 결정한다고 하고, X -> Y로 표기한다.
  • 완전 함수적 종속(Full Functional Dependency)
    • 어떤 테이블 R에서 속성 Y가 다른 속성 집합 X 전체에 대해 함수적 종속이면서 속성 집합 X의 어떠한 진 부분 집합 Z에도 함수적 종속이 아닐 때 속성 Y는 속성 집합 X에 완전 함수적 종속이라고 한다.
  • 부분 함수적 종속(Partial Functional Dependency)
    • 어떤 테이블 R에서 속성 Y가 다른 속성 집합 X 전체에 대해 함수적 종속이면서 속성 집합 X의 임의의 진 부분 집합에 대해 함수적 종속일 때, 속성 Y는 속성 집합 X에 부분 함수적 종속이라고 한다.
  • 이행적 함수적 종속(Transitive Functional Dependency)
    • X -> Y이고 Y -> Z일 때 X -> Z를 만족하는 관계를 의미한다.

정규화

  • 정규화는 테이블의 속성들이 상호 종속적인 관계를 갖는 특성을 이용하여 테이블을 무손실 분해하는 과정이다.

정규화 과정 정리

  1. 비정규 릴레이션
  2. 1NF(제 1정규형): 도메인이 원자값
  3. 2NF(제 2정규형): 부분적 함수 종속 제거
  4. 3NF(제 3정규형): 이행적 함수 종속 제거
  5. BCNF: 결정자이면서 후보키가 아닌 것 제거
  6. 4NF(제 4정규형): 다치 종속 제거
  7. 5NF(제 5정규형): 조인 종속성 이용

반정규화

  • 반정규화는 시스템의 성능을 향상하고 개발 및 운영의 편의성 등을 높이기 위해 정규화된 데이터 모델을 의도적으로 통합, 중복, 분리하여 정규화 원칙을 위배하는 행위이다.
  • 반정규화를 수행하면 시스템의 성능이 향상되고 관리 효율성은 증가하지만 데이터의 일관성 및 정합성이 저하될 수 있다.
  • 과도한 반졍구화는 오히려 성능을 저하시킬 수 있다.

시스템 카탈로그

  • 시스템 카탈로그는 시스템 그 자체에 관련이 있는 다양한 객체에 관한 정보를 포함하는 시스템 데이터베이스이다.
  • 시스템 카탈로그 내의 각 테이블은 사용자를 포함하여 DBMS에서 지원하는 모든 데이터 객체에 대한 정의나 명세에 관한 정보를 유지 관리하는 시스템 테이블이다.
  • 카탈로그들이 생성되면 데이터 사전에 저장되기 때문에 좁은 의미로는 카탈로그를 데이터 사전이라고도 한다.

트랜잭션의 특성

특성의미
Atomicity(원자성)트랜잭션의 연산은 데이터베이스에 모두 반영되도록 완료되든지 아니면 전혀 반영되지 않도록 복구되어야 함
Consistency(일관성)트랜잭션이 그 실행을 성공적으로 완료하면 언제나 일관성 있는 데이터베이스 상태로 변환함
Isolation(독립성, 격리성, 순차성)둘 이상의 트랜잭션이 동시에 병행 실행되는 경우 어느 하나의 트갠잭션 실행중에 다른 트랜잭션의 연산이 끼어들 수 없음
Durability(영속성, 지속성)성공적으로 완료된 트랜잭션의 결과는 시스템이 고장나더라도 영구적으로 반영되어야 함

CRUD 분석

  • CRUD 분석은 프로세스와 테이블 간에 CRUD 매트릭스를 만들어서 트랜잭션을 분석하는 것이다.
  • CRUD 분석을 통해 많은 트랜잭션이 몰리는 테이블을 파악할 수 있으므로 디스크 구성 시 유용한 자료로 활용할 수 있다.
  • CRUD 매트릭스의 각 셀에는 Create, Read, Update, Delete의 앞 글자가 들어간다.

인덱스

  • 인덱스는 데이터 레코드를 빠르게 접근하기 위해 <키 값, 포인터> 쌍으로 구성되는 데이터 구조이다.
  • 인덱스는 레코드가 저장된 물리적 구조에 접근하는 방법을 제공한다.
  • 인덱스를 통해서 파일의 레코드에 빠르게 액세스 할 수 있다.

뷰

  • 뷰는 사용자에게 접근이 허용된 자료만을 제한적으로 보여주기 위해 하나 이상의 기본 테이블로부터 유도된, 이름을 가지는 가상 테이블이다.
  • 뷰가 정의된 기본 테이블이나 뷰를 삭제하면 그 테이블이나 뷰를 기초로 정의된 다른 뷰도 자동으로 삭제된다.
  • 뷰를 정의할 때는 CREATE문, 제거할 때는 DROP문을 사용한다.

파티션의 종류

종류특징
범위 분할(Range Partitioning)지정한 열의 값을 기준으로 분할함
ex)일별, 월별, 분기별 등
해시 분할(Hash Partitioning)- 해시 함수를 적용한 결과 값에 따라 데이터를 분할함
- 특정 파티션에 데이터가 집중되는 범위 분할의 단점을 보완한 것으로, 데이터를 고르게 분산할 때 유용함
- 특정 데이터가 어디에 있는지 판단할 수 없음
- 고객번호, 주민번호 등과 같이 데이터가 고른 컬럼에 효과적임
조합 분할(Composite Pratitioning)- 범위 분할로 분할한 다음 해시 함수를 적용하여 다시 분할하는 방식
- 범위 분할한 파티션이 너무 커서 관리가 어려울 때 유용함

분산 데이터베이스의 목표

  • 위치 투명성(Location Transparency): 액세스하려는 데이터베이스의 실제 위치를 알 필요 없이 단지 데이터베이스의 논리적인 명칭만으로 액세스할 수 있음
  • 중복 투명성(Replication Transparency): 동일 데이터가 여러 곳에 중복되어 있더라도 사용자는 마치 하나의 데이터만 조재하는 것처럼 사용하고, 시스템은 자동으로 여러 자료에 대한 작업을 수행함
  • 병행 투명성(Concurrency Transparency): 분산 데이터베이스와 관련된 다수의 트랜잭션들이 동시에 실현되더라도 그 트랜잭션의 결과는 영향을 받지 않음.
  • 장애 투명성(Failure Transparency): 트랜잭션, DBMS, 네트워크, 컴퓨터 장애에도 불구하고 트랜잭션을 정확하게 처리함

RTO/RPO

  • RTO(Recovery Time Objective, 목표 복구 시간): 비상사태 또는 업무 중단 시점으로부터 복구되어 가동될 때까지의 소요 시간을 의미함.
    ex) 장애 발생 후 6시간 내 복구 가능
  • RPO(Recovery Point Objective, 목표 복구 시점): 비상사태 또는 업무 중단 시점으로부터 데이터를 복구할 수 있는 기준점을 의미함.
    ex) 장애 발생 전인 지난 주 금요일에 백업시켜 둔 복원 시점으로 복구 가능

임의 접근통제

  • 임의 접근통제(DAC; Discretionary Access Control)는 데이터에 접근하는 사용자의 신원에 따라 접근 권한을 부여하는 방식이다.
  • 데이터 소유자가 접근통제 권한을 지정하고 제어한다.
  • 객체를 생성한 사용자가 생성된 객체에 대한 모든 권한을 부여받고, 부여된 권하늘 다른 사용자에게 허가할 수도 있다.

강제 접근통제

  • 강제 접근통제(MAC; Mandatory Access Control)는 주체와 객체의 등급을 비교하여 접근 권할을 부여하는 방식이다.
  • 시스템이 접근통제 권한을 지정한다.
  • 데이터베이스 객체별로 보안 등급을 부여할 수 있다.
  • 사용자별로 인가 등급을 부여할 수 있다.

역할기반 접근통제

  • 역할기반 접근통제(RBAC; Role Based Access Control)는 사용자의 역할에 따라 접근 권한을 부여하는 방식이다.
  • 중앙관리자가 접근통제 권한을 지정한다.
  • 임의 접근통제와 강제 접근통제의 단점을 보완하였다.
  • 다중 프로그래밍 환경에 최적화된 방식이다.

DAS

  • DAS(Direct Attached Storage)는 서버와 저장장치를 전용 케이블로 직접 연결하는 방식이다.
  • 일반 가정에서 컴퓨터에 외장하드를 연결하는 것이 여기에 해당된다.
  • 직접 연결 방식이므로 다른 서버에서 접근할 수 없고 파일을 공유할 수 없다.

SAN

  • SAN(Strage Area Network)은 DAS의 빠른 처리와 NAS의 파일 공유 장점을 혼합한 방식으로, 서버와 저장장치를 연결하는 전용 네트워크를 별도로 구성하는 방식이다.
  • 파이버 채널(Fibre Channel, 광 채널) 스위치를 이용하여 네트워크를 구성한다.
  • 파이버 채널 스위치는 서버와 저장장치를 광케이블로 연결하므로 처리 속도가 빠르다.
  • 서버들이 저장장치 및 파일을 공유할 수 있다.

자료 구조의 분류

  • 선형구조: 배열, 선형 리스트(연속 리스트, 연결 리스트), 스택, 큐, 데크
  • 비선형 구조: 트리, 그래프

스택

  • 스택은 리스트의 한쪽 끝으로만 자료의 삽입, 삭제 작업이 이루어지는 자료구조이다.
  • 후입선출(LIFO; Last In First Out) 방식으로 자료를 처리한다.
  • 저장할 기억 공간이 없는 상태에서 테이터가 삽입되면 오버플로(Overflow)가 발생한다.
  • 삭제할 데이터가 없는 상태에서 데이터를 삭제하면 언더플로(Underflow)가 발생한다.

방향/무방향 그래프의 최대 간선 수

  • 방향 그래프의 최대 간선 수: n(n-1)
  • 무방향 그래프에서 최대 간선 수: n(n-1)/2
    n은 정점의 개수이다.

트리 관련 용어

  • 노드(Node): 트리의 기본 요소로서 자료 항목과 다른 항목에 대한 가지를 합친 것.
  • 근 노드(Root Node): 트리의 맨 위에 있는 노드.
  • 단말 노느(Terminal Node) = 잎 노드(Leaf Node): 자식이 하나도 없는 노드, 즉 Degree가 0인 노드
  • Level: 근 노드의 Level을 1로 가정한 후 어떤 Level이 L이면 자식 노드는 L + 1
  • 깊이: Tree에서 노드가 가질 수 있는 최대의 레벨
  • 숲: 여러 개의 트리가 모여 있는 것
  • 트리의 디그리: 노드들의 디그리 중에서 가장 많은 수

Preorder 운행법

  • Preorder 운행법은 이진 트리를 Root -> Left -> Right순으로 운행하며 노드들을 찾아가는 방법이다.

Inorder 운행법

  • Inorder 운행법은 이진 트리를 Left -> Root -> Right순으로 운행하며 노드들을 찾아가는 방법이다.

Postorder 운행법

  • Postorder 운행법은 이진 트리를 Left -> Right -> Root순으로 운행하며 노드들을 찾아가는 방법이다.

Postfix로 표기된 수식을 Infix로 바꾸기

  • Postfix는 Infix 표기법에서 연산자를 해당 피연산자 두 개의 뒤로 이동한 것이므로 연산자를 다시 해당 피연산자 두 개의 가운데로 옮기면 된다.
  • ABC-/DEF++ -> A/(B-C)+D(E+F)
    1. 먼저 인접한 피연산자 두 개와 오른쪽의 연산자를 괄호로 묶는다.
      ((A(BC-)/)(D(EF+)*)+)
    2. 연산자를 해당 피연산자의 가운데로 이동시킨다.
      ((A/(B-C))+(D*(E+F)))
    3. 필요 없는 괄호를 제거한다.
      A/(B-C)+D*(E+F)

삽입 정렬

  • 삽입 정렬(Insertion Sort)은 가장 간단한 정렬 방식으로, 이미 순서화된 파일에 새로운 하나의 레코드를 순서에 맞게 삽입시켜 정렬하는 방식이다.

  • 평균과 최악 모두 수행 시간 복잡도는 O(n²)이다.
    ex) 8, 5, 6, 2, 4를 삽입 정렬로 정렬하시오.

    초기 상태:85624
    1회전:58624
    2회전:56824
    3회전:25684
    4회전:24568

선택 정렬

  • 선택 정렬(Selection Sort)은 n개의 레코드 중에서 최소값을 찾아 첫 번째 레코드 위치에 놓고, 나머지 (n-1)개 중에서 다시 최소값을 찾아 두 번째 레코드 위치에 놓는 방식을 반복하여 정렬하는 방식이다.

  • 평균과 최악 모두 수행 시간 복잡도는 O(n²)이다.
    ex) 8, 5, 6, 2, 4를 선택 정렬로 정렬하시오.

    초기 상태:85624
    1회전:25684
    2회전:24685
    3회전:24586
    4회전:24568

버블 정렬

  • 버블 정렬(Bubble Sort)은 주어진 파일에서 인접한 두 개의 레코드 키 값을 비교하여 그 크기에 따라 레코드 위치를 서로 교환하는 정렬 방식이다.

  • 평균과 최악 모두 수행 시간 복잡도는 O(n²)이다.
    ex) 8, 5, 6, 2, 4를 버블 정렬로 정렬하시오.

    초기 상태:85624
    1회전:56248
    2회전:52468
    3회전:24568
    4회전:24568

퀵 정렬

  • 퀵 정렬(Quick Sort)은 키를 기준으로 작은 값은 외쪽, 큰 값은 오른쪽 서브 파일에 분해시키는 과정을 반복하는 정렬 방식이다.
  • 레코드의 많은 자료 이동을 없애고 하나의 파일을 부분적으로 나누어 가면서 정렬한다.
  • 평균 수행 시간 복잡도는 O(nlog₂n)이고, 최악의 수행 시간 복잡도는 O(n²)이다.
profile
Juni_woo
개발 공부!
이전 포스트

[정보처리기사] 요구사항 확인

다음 포스트

[정보처리기사] 통합구현

0개의 댓글