2장 데이터 입출력 구현

데이터 베이스 개요

1. 데이터베이스

공동으로 사용될 데이터를 중복을 배제하여 통합하고, 저장장치에 저장하여 항상 사용할 수 있도록 운영하는 운영 데이터

 

(1) 데이터의 독립성

- 논리적 독립성

: DB와 애플리케이션을 독립시킴으로써 데이터의 논리적 구조 변경이 애플리케이션에 영향을 미치지 않음

- 물리적 독립성

: 애플리케이션과 보조 기억장치를 물리적으로 독립시킴, 디스크를 추가/변경해도 애플리케이션은 영향을 받지 않음

2. DBMS

사용자의 요구에 따라 정보를 생성해주고 데이터베이스를 관리하는 소프트웨어

 

(1) 필수기능

- 정의 기능

: 데이터의 형과 구조에 대한 정의, 이용 방식, 제약 조건 등을 명시하는 기능

- 조작 기능

: 데이터 검색, 갱신, 삭제, 삽입 기능을 위해 인터페이스 제공

- 제어 기능

: 데이터의 무결성, 보안, 권한 검사, 병행 제어를 제공하는 기능

 

3. 스키마

데이터베이스의 구조와 제약조건에 대한 전반적인 명세

 

(1) 종류

- 외부 스키마

: 사용자나 프로그래머가 DB의 논리적 구조를 정의 한 것

- 개념 스키마

: 데이터 베이스의 전체적인 논리적 구조

- 내부 스키마

: 물리 저장장치 입장에서 본 데이터베이스 구조

---

데이터베이스 설계

1. 설계 순서

요구 조건 분석 -> 개념적 설계 -> 논리적 설계 -> 물리적 설계 -> 구현

 

(1) 요구 조건 분석

DB를 사용할 사람들로 부터 필요한 용도를 파악하는 것

 

(2) 개념적 설계

현실 세계에 대한 인식을 추상적으로 표현하는 것

 

(3) 논리적 설계

현실 세계에서 발생하는 자료를 논리적 자료 구조로 변환하는 작업

 

(4) 물리적 설계

논리적 구조로 표현된 데이터를 물리적 구조의 데이터로 변환하는 작업

 

(5) 구현

논리적, 물리적 설계로 도출된 DB 스키마를 파일로 생성하는 과정

 

---

데이터 모델의 개념

1. 데이터 모델

현실 세계의 데이터들을 단순화, 추상화하여 만든 개념적 모형

 

(1) 구성 요소

- 개체

  : 데이터베이스에 표현하려는 것으로 현실 세계의 개념이나 정보같은 대상체를 말함

- 속성

  : 데이터베이스를 구성하는 가장 작은 단위. 개체의 특성을 기술.

• 기본 속성
  • 업무 분석을 통해 정의한 속성
• 설계 속성
  • 원래 업무상 존재하지 않고 설계시에 도출된 속성
• 파생 속성
  • 다른 속성에 의해 영향이나 변형이 이루어져 도출된 속성
  • 되도록 적은 수를 정의할 것

- 관계

  : 개체간의 논리적 연결

• 관계의 형태
  • 일대일
  • 일대다
  • 다대다
• 관계의 종류
  • 종속 관계
    • 두 개체간의 주종 관계를 표현
  • 중복 관계
    • 두 개체 사이에 여러 관계가 표현된 경우
  • 배타 관계
    • 개체의 특성을 분할하는 관계
  • 재귀 관계
    • 자기 자신과 관계를 맺는 경우
    • 순환 관계 라고도 함

(2) 종류

- 개념적 데이터 모델

: 현실세계의 데이터를 추상적 개념으로 표현하는 과정 (E-R 모델)

 

- 논리적 데이터 모델

: 현실세계의 데이터를 컴퓨터가 이해할 수 있게끔 변환하는 과정.

단순히 데이터 모델이라고 하면 논리적 데이터 모델을 말하는 것.

 

- 물리적 데이터 모델

 

(3) 데이터 모델에 표시할 요소

- 구조

: 논리적으로 표현된 개체들간의 관계를 나타냄

- 연산

: DB를 조작하는 도구

- 제약조건

: 실제 데이터의 논리적인 제약 조건

 

---

E-R 모델

- 무질서한 현실세계의 데이터를 개념적 논리 데이터로 표현하기 위한 것

- 피터첸에 의해 제안 됨

---

RDB 구조 / 관계형 데이터 모델

1. 관계형 데이터베이스

2차원적인 표를 이용해서 데이터 상호 관계를 정의하는 데이터베이스 구조

장점 : 간결하고 보기 편함, 변환 용이

단점 : 성능이 다소 떨어짐

 

(1) 종류

- 튜플

: 릴레이션을 구성하는 행을 말함.

튜플의 수 = 카디널리티, 기수

 

- 속성

: 데이터베이스를 구성하는 가장 작은 단위

속성의 수 = 디그리, 차수

 

- 도메인

: 하나의 속성이 가질 수 있는 같은 타입의 원자값의 집합

 

(2) 특징

- 릴레이션에 포함된 튜플들은 모두 상이

- 튜플 사이에는 순서가 없음

- 속성 값은 원자값만 저장

2. 관계형 데이터 모델

2차원적인 표를 이용해서 데이터 상호 관계를 정의하는 데이터베이스 구조

 

3. 제약조건

(1) 키

- 후보키

속성들 중에서 튜플을 유일하게 식별하는 속성들의 부분집합. 유일성과 최소성을 모두 만족해야 함

- 기본키

후보키에서 특별히 선정된 주 키

- 대체키

여러 개의 후보키 중에서 기본키를 제외한 나머지 후보키 집합

- 슈퍼키

속성들의 집합으로 구성된 키

- 외래키

다른 릴레이션의 키본키를 참조하는 속성 또는 속성 집합

 

(2) 무결성

데이터베이스에 저장된 값과 실제 데이터 값이 일치하는 정확성

 

• 종류
  • 개체 무결성 : 테이블을 구성하는 기본키는 null 값이 들어가거나 중복될 수 없음
  • 참조 무결성 : 외래키와 참조하는 테이블의 기본키가 일치해야 함
  • 도메인 무결성 : 한 속성 내에 지정된 도메인 외의 값은 들어갈 수 없음
  • 사용자 정의 무결성 : 사용자가 정의한 제약조건에 만족해야 함
  • NULL 무결성 : 릴레이션의 특정 속성값이 null이 되지 않도록 하는 것
  • 고유 무결성 : 릴레이션의 특정 속성값이 중복이 되지 않도록 하는 것
  • 키 무결성 : 하나의 릴레이션에는 적어도 하나의 키가 존재해야 하는 것
  • 관계 무결성 : 릴레이션의 어느 튜플을 삽입할 때 다른 릴레이션의 튜플 사이에 관계에 대한 적절성 여부 판단
• 데이터 무결성 강화
  • 애플리케이션 : 무결성 검사 코드 추가
  • 데이터베이스 트리거
  • 제약 조건

---

관계대수 / 관계해석

1. 관계대수

원하는 정보를 어떻게 얻는가를 기술하는 절차적 언어

 

(1) 순수 관계 연산자

- Select (시그마)

: 선택 조건을 만족하는 튜플의 부분집합 구하기 

- Projection (파이)

: 릴레이션에서 속성 리스트에 제시된 속성 값만을 추출하여 새로운 릴레이션을 만듦

- Join (리본모양)

: 공통 속성으로 두 릴레이션을 합쳐 새로운 릴레이션을 만듦. 일반 집합 연산자의 교차곱과 동일한 기능.

- Division (나누기)

: 한 쪽이 가진 속성을 제외한 속성만을 구하는 연산

(2) 일반 집합 연산자 

- 합집합

: 두 릴레이션에 존재하는 튜플의 합집합. 중복 제외.

- 교집합

- 차집합

- 교차곱(카디션 프로덕트)

: 두 릴레이션의 튜플들의 순서쌍을 구함

2. 관계해석

관계데이터의 연산을 표현하는 방법. 계산 수식 사용. 비절차적 특성.

 

---

이상 / 함수적 종속

1. 이상

테이블에서 일부 속성들의 종속으로 인해 중복 데이터가 발생하고, 이 중복으로 인해 데이터에 이상이 생기는 것이다.

(1) 삽입 이상

: 테이블에 데이터를 삽입할 때 원하지 않는 값들로 인해 삽입할 수 없는 것

(2) 삭제 이상

: 의도와 상관 없이 관련 없는 튜플들도 연쇄 삭제가 되는 이상현상

(3) 갱신 이상

: 갱신 시 일부 튜플만 변경되어 정보의 불일치성이 발생하는 현상

 

2. 함수적 종속

특정 속성 집합이 다른 속성 집합을 결정할 때 사용하는 표현 (X -> Y)

---

정규화

테이블 속성들이 서로 종속적인 관계를 갖는 특성을 이용하여 테이블을 무손실 분해하는 것.

 

(1) 제 1 정규화

: 모든 속성의 도메인이 원자값으로 구성되어 있는 경우

 

(2) 제 2 정규화

: 기본키가 아닌 모든 속성이 기본키에 의해 완전 함수적 종속을 만족하는 경우 (부분 함수적 종속 제거)

 

(3) 제 3 정규화

: 이행적 함수적 종속 제거

 

(4) 보이스코드 정규화 (BCNF)

: 모든 결정자가 후보키인 경우 (결정자이면서 후보키가 아닌 것 제거)

 

(5) 제 4 정규화

: 다치(다중) 종속 제거

 

(6) 제 5 정규화

: 조인 종속성 이용

---

반정규화

정규화된 데이터 모델을 의도적으로 통합, 중복, 분리하여 정규화 원칙을 위배하는 것

장점 : 성능 향상, 관리 효율 증가

단점 : 데이터의 일관성 유지가 어려움

 

(1) 테이블 통합
- 두 테이블의 조인 연산이 많은 경우 하나의 테이블로 통합하는 것

- 1:1 관계 테이블 통합, 1:n 관계 테이블 통합, 슈퍼타입/서브타입 테이블 통합

 

(2) 테이블 분할

- 테이블을 수평 또는 수직으로 분할하는 것

- 수평 분할 : 레코드 기준으로 분할. 레코드 별 사용 빈도 차이가 큰 경우

- 수직 분할 : 속성 기준으로 분할. 자주 조회되는 속성인 경우, 갱신 위주의 속성인 경우, 속성이 너무 많은 경우. 

 

(3) 중복 테이블 추가

- 테이블을 중복하여 유지하는 것

- 다른 서버에 있는 테이블을 이용해야 하는 경우, 여러 테이블에서 데이터를 추출해야 하는 경우.

- 집계 테이블 추가

- 진행 테이블 추가

- 특정 부분만 포함하는 테이블 추가

 

(4) 중복 속성 추가

- 조인해서 데이터를 처리 할 때 자주 조회하는 속성을 하나 더 추가하는 것

- 데이터의 무결성 유지가 어려움

---

시스템 카탈로그

다양한 객체에 관한 정보를 포함하는 시스템 데이터베이스

카탈로그는 데이터 사전에 저장됨

 

(1) 메타 데이터

: 시스템 카탈로그에 저장된 정보

 

(2) 데이터 디렉터리

: 데이터 사전에 수록된 데이터에 접근하는 데 필요한 정보를 관리/유지하는 시스템

 

---

트랜잭션 분석 / CRUD 분석

1. 트랜잭션

하나의 논리적 기능을 수행하기 위한 작업 단위.

한 번에 수행되어야 하는 일련의 연산들.

 

(1) 특성

- Atomicity (원자성)

: 트랜잭션 연산은 모두 commit 되던지, 모두 rollback되어야 함

- Consistency (일관성)

: 트랜잭션 실행을 성공하면 그 결과 값은 일관성 있는 상태로 변화

- Isolation (독립성)

: 각 트랜잭션은 서로에게 영향을 주지 않음

- Durability (영속성)

: 성공적으로 완료된 트랜잭션은 영구적으로 반영되어야 함

 

 

2. CRUD 분석

프로세스 - 테이블 간에 CRUD 테이블을 만들어서 트랜잭션을 분석하는 것.

C, R, U, D 중 어느 것도 적히지 않은 행이나 열, C나 R이 없는 열을 확인하여 누락된 테이블/프로세스를 찾음.

 

3. 트랜잭션 분석

CRUD 매트릭스를 기반으로 테이블에 발생하는 트랜잭션 양을 분석, 테이블에 저장되는 데이터 양을 유추하여 용량 산정 및 구조의 최적화를 목적으로 함.

과도하게 트랜잭션이 집중되는 테이블이 있다면 이를 여러 디스크에 분산 배치하여 병목현상을 줄일 수 있음.

 

---

인덱스

데이터 레코드를 빠르게 접근하기 위해 키, 값 포인터 쌍으로 이루어진 데이터 구조

 

(1) 종류

- 트리 기반 인덱스

: 인덱스를 저장하는 블록들이 트리 기반으로 이루어져 있는 것

- 비트맵 인덱스

: 컬럼 값을 0과1로 이루어진 값으로 변환하여 인덱스로 사용하는 것

- 함수 기반 인덱스

: 컬럼 값 대신 컬럼에 함수의 결과 값을 사용하는 것

- 비트맵 조인 인덱스

: 다수의 조인된 객체로 구성된 인덱스

- 도메인 인덱스

: 사용자가 지정한 값을 인덱스로 만드는 것

 

(2) 클러스터드 / 넌클러스터드

- 클러스터드 인덱스

: 인덱스 키의 순서에 따라 데이터가 정렬되어 저장되는 방식

- 넌클러스터드 인덱스

: 인덱스만 순서에 따라 정렬되고 데이터는 정렬되지 않는 방식

 

---

뷰/ 클러스터

1. 뷰

접근이 허용된 자료만을 제한적으로 보여주기 위해 하나 이상의 기본 테이블로부터 유도된 가상 테이블

 

(1) 장단점

- 장점 : 접근 제어를 통한 자동 보안, 논리적 데이터 독립성 등

- 단점 : 독립적인 인덱스를 가질 수 없음, 뷰의 정의를 변경할 수 없음, 구성된 내용에 대해 삽입/삭제/갱신에 제약이 생김

2. 클러스터

액세스 효율을 향상시키기 위해 동일한 성격의 데이터를 동일한 블록에 저장하는 물리적 방법

조회 속도는 향상시키지만 삽입/갱신/삭제 연산은 성능 저하

데이터 분포도가 높을수록(동일 데이터가 많을 수록) 유리

처리 범위가 넓은 경우는 단일 클러스터링, 조인 연산이 많을 때는 다중 클러스터링을 사용

---

파티션

대용량의 테이블이나 인덱스를 작은 논리적 단위로 나누는 것

 

(1) 장단점

- 장점 : 액세스 범위를 줄여 성능 향상, 분산 저장되므로 디스크 성능 향상, 백업 및 복구가 빠름, 데이터 가용성 향상

- 단점 : 세심한 관리 요구, 테이블간 조인 비용 증가, 용량이 작은 테이블에 파티셔닝을 하는 경우 성능이 오히려 저하됨

 

(2) 종류

- 범위 분할

: 지정한 열의 범위로 분할

- 해시 분할

: 해시 값이 같은 데이터 끼리 분할

- 조합 분할

: 범위분할 + 해시분할 (범위분할 후 해시분할)

 

---

분산 데이터베이스 설계

1. 데이터베이스 용량 설계

- 데이터가 저장될 공간 정의

- 데이터베이스 용량을 정확히 산정하여 디스크의 저장 공간을 효과적으로 사용하고 확장성 및 가용성을 높임

 

2. 분산 데이터베이스 설계

하나의 시스템처럼 동작하지만 물리적으로는 네트워크 상에서 분산되어 있는 데이터베이스

 

(1) 목표

- 위치 투명성

: 접근하려는 DB의 실제 위치를 알 필요가 없음

- 장애 투명성

: 장애가 났어도 트랜잭션을 정확하게 처리함

- 병행 투명성

: 다수의 트랜잭션이 동시에 실행되더라도 서로 영향을 미치거나 받지 않음

- 중복 투명성

: 동일한 데이터가 여러 곳에 중복되어 있더라도 하나의 데이터만 존재하는 것처럼 사용할 수 있음

 

(2) 설계 방법

- 테이블 위치 분산

: DB 테이블을 각기 다른 서버에 분산 배치

- 분할

: 데이터를 분할하여 분산

완전성, 재구성, 상호 중첩 배제를 지켜야함

수평 분할(행 단위), 수직 분할(열 단위)

- 할당

: 동일한 분할을 여러 개의 서버에 생성하는 분할 방법

중복 할당, 비중복 할당

---

 

데이터베이스 이중화 / 서버 클러스터링

1. 데이터베이스 이중화

시스템 오류로 인한 DB 서비스 중단이나 손상 발생 시 이를 복구하기 위해 동일한 DB를 복제하여 관리하는 것

사용자가 행하는 작업은 DB 이중화 시스템에 연결된 다른 DB에도 동일하게 적용됨

여러 개의 DB에서 분산 처리 하므로 DB 부하를 줄일 수 있음

 

(1) 분류

- Eager

: 트랜잭션 수행 중 데이터 변경이 발생하면 이중화된 DB에 즉시 반영

- Lazy

: 트랜잭션이 종료되면 변경 사실을 새로운 트랜잭션에 작성하여 각 DB에 전달되는 방법

 

(2) 구성 방법

- 활동-대기 방법

: 한 개의 DB 서버가 정상적으로 운영될 때는 다른 DB는 대기 상태로 존재. 정상적으로 운영하던 DB에 장애가 발생하면 대기 상태로 있던 DB가 활성화 됨

- 활동-활동 방법

: 이중화 되어있는 모든 DB가 서로 다른 서비스를 제공하는 활성 상태로 존재. 그 중 어느 하나가 잘못되면 다른 쪽에서 해당 서비스를 제공하는 방식

 

2. 클러스터링

두 대 이상의 서버를 한 대처럼 운영하는 기술

서버 이중화 및 공유 스토리지를 사용하여 서버의 고가용성 제공

 

(1) 종류

- 고가용성 클러스터링

: 한 서버에 장애가 발생하면 다른 서버에서 처리하는 것

- 병렬 처리 클러스터링

: 작업 처리를 분산으로 진행하여 처리율을 높이는 것

 

(2) RTO / RPO

- RTO (Recovery Time Objective, 목표 복구 시간)

: 얼마나 빨리 복구되나. 복구되어 가동될 때까지의 소요시간

- RPO (Recovery Point Objective, 목표 복구 시점)

: 얼마나 많이 복구되나. 데이터를 복구할 수 있는 기준점

---

데이터베이스 보안

권한이 없는 사용자가 접근하는 것을 금지하기 위해 사용되는 기술

 

1. 암호화

수신자만 열람할 수 있도록 송신자가 평문을 암호화 하는 것

- 공개키 암호 방식

- 개인키 암호 방식

2. 접근 통제

(1) 접근 통제 기술 (권한 부여)

- DAC (Discretionary Access Control, 임의 접근 통제)

: 사용자의 신원에 따라 접근 권한 부여

- MAC (Mandatory Access Control, 강제 접근 통제)

: 주체와 객체의 등급을 비교하여 접근 권한 부여 (DB객체에는 보안 등급을 사용자에게는 인가 등급을 매겨 일치하거나 인가 등급이 높아야만 접근 가능하게 통제하는 것)

- RBAC (Role Based Access Control, 역할기반 접근 통제)

: 사용자의 역할에 따라 접근 권한 부여

 

(2) 접근 통제 정책 (접근 통제)

- 신분 기반 정책

: 신분에 근거하여 객체의 접근을 제한

- 규칙 기반 정책

: 주체가 갖는 권한에 근거하여 객체의 접근을 제한

- 역할 기반 정책

: 주체의 역할에 근거하여 접근을 제한

 

(3) 접근 통제 매커니즘 (접근 통제 구현)

접근 통제 정책을 구현하는 기술적인 방법

접근통제 목록, 능력 리스트, 보안 등급, 패스워드, 암호화 등이 있음

 

(4) 접근 통제 보안 모델 (보안 정책 구현)

- 기밀성 모델

: 군사목적으로 개발. 기밀성이 최우선.

- 무결성 모델

: 불법적인 정보 변경 방지

- 접근통제 모델

: 접근통제 매커니즘을 보안 모델로 발전시킨 것

 

(5) 접근 통제 조건 (접근 통제 정책에 추가할 수 있는 조건)

- 값 종속 통제

: 객체에 저장된 값에 따라 접근 통제를 다르게 허용해야 하는 경우

- 다중 사용자 통제

: 지정된 객체에 다수의 사용자가 동시에 접근 요청을 하는 경우

- 컨텍스트 기반 통제

: 특정 시간, 네트워크 주소 등에 근거하여 접근을 제어하는 방법

 

(6) 감사 추적

애플리케이션이 DB에 접속하여 행한 모든 작업을 기록하는 기능

---

스토리지

대용량 데이터를 저장하기 위해 서버와 저장장치를 연결하는 기술

 

(1) DAS (Direct Attached Storage)

- 전용 케이블로 직접 연결하는 방식

(2) NAS (Network Attached Storage)

- 네트워크를 통해 연결하는 방식

(3) SAN (Storage Area Network)

- DAS + NAS

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

---

자료구조

기억장치에 저장하는 방법과 자료간의 관계 및 처리 방법 등을 연구하는 것 (공간 효율성, 시간 효율성 분석)

1. 배열

크기와 타입이 동일한 자료들이 순서대로 나열된 집합

2. 연속 리스트

메모리에 값이 연속하여 저장되는 자료구조

3. 연결 리스트

자료들을 무작위 공간에 저장하되, 자료 항목의 순서에 따라 노드와 포인터를 이용하여 서로 연결시킨 자료 구조

4. 스택

리스트 한 쪽 으로만 삽입, 삭제를 하는 자료구조 (후입선출)

5. 큐

리스트 한 쪽에서는 삽입만, 반대 쪽에서는 삭제만 이루어지는 자료구조 (선입선출)

6. 그래프

정점(Vertex)과 간선(Edge)의 두 집합으로 이루어지는 자료구조

사이클이 없는 그래프는 트리

 

- 방향 그래프

최대 간선 수 : n(n-1)

- 무방향 그래프

최대 간선 수 : n(n-1)/2

 

7. 트리

정점과 간선으로 이루어진 두 집합으로 이루어져 있지만 사이클이 발생하지 않는 자료구조이다.

 

- 근 노드(Root Node)

- Degree(차수)

: 자식의 개수 (트리의 차수 = 최다 자식을 가진 노드의 자식 개수)

- Level (레벨)

: Root Node의 레벨을 1로 정했을 때 자식노드는 부모 노드 레벨의 + 1

 

8. 이진트리

차수가 2 이하인 노드들로 구성된 트리

 

- 이진트리로 만드는 수식 표기법

• Postfix -> Infix
  • 인접한 피연산자 두 개와 오른쪽 연산자를 괄호로 묶기
  • 연산자를 피연산자들의 가운데로 이동시키기
• Prefix -> Infix
  • 인접한 피연산자 두 개와 왼쪽 연산자를 괄호로 묶기
  • 연산자를 피연산자들의 가운데로 이동시키기

---

정렬

1. 삽입 정렬 (Insertion Sort)

이미 정렬된 원소들 중 새로운 원소를 순서에 맞게 삽입시켜 정렬하는 방식

해당 원소가 삽입되면 뒤쪽에 존재하는 원소들은 한 칸씩 밀리게 됨

2. 선택 정렬 (Selection Sort)

n번을 반복하여 최소값을 갖는 원소를 순서대로 정렬시키는 방식

찾게된 최소값 원소와 최소값이 위치되어야 할 곳에 존재하는 원소를 바꾸는 방식으로 정렬됨

3. 버블 정렬 (Bubble Sort)

인접한 두 원소를 비교하여 크기에 따라 위치를 바꾸는 방식

4. 쉘 정렬 (Shell Sort)

매개변수 값으로 서브파일을 구성하고 각 서브 파일을 삽입정렬 방식으로 순서 배열하는 과정을 반복하는 정렬 방식

Donald Shell이 고안한 방법으로 Shell Sort라는 이름이 붙음

평균 : O(n1.5), 최악 : O(n2)

5. 퀵 정렬 (Quick Sort)

키를 기준으로 작은 값은 왼쪽, 큰 값은 오른쪽 서브 파일에 분해 시키는 정렬 방식

평균 : O(nlogn), 최악 : O(n2)

6. 힙 정렬 (Heap Sort)

완전 이진트리를 이용한 정렬 방식.

평균, 최악 모두 O(nlogn)

7. 2-Way 합병 정렬 (Merge Sort)

이미 정렬되어 있는 두 개의 서브 파일을 합병하여 한 개의 파일로 만드는 정렬 방식

평균, 최악 모두 O(nlogn)

8. 기수 정렬

큐를 이용하여 자릿수별로 정렬하는 방식

평균, 최악 모두 O(dn)