dev-waterparsley

🔸대칭키 암호

• =비밀키 암호, 단일키 암호, 관용 암호
• 암호화와 복호화에 하나의 같은 비밀키를 사용하는 암호 방식

C = Eₖ(P)
P = Dₖ(C) 

1. 블록 암호

• 평문을 고정된 크기의 블록으로 나누어 각 블록마다 암호화 과정을 수행하여 블록 단위로 암호문을 얻는 대칭키 암호 방식

🔸블록 암호 알고리즘의 구조

• 입력 블록과 키의 모든 비트는 출력 블록의 각 비트에 영향을 줌

• 암호화는 주로 단순한 함수를 반복적으로 적용함으로써 암호학적으로 강한 함수를 만듦
  • 라운드 함수: 반복되는 함수
  • 라운드 키: 라운드 함수에 작용하는 키
  • 키 스케줄: 키를 입력하여 라운드 키를 발생시키는 과정

🔸라운드 구성

①파이스텔(feistel) 구조

• 하나의 입력 블록을 분할하여 좌우 두 개의 블록으로 구분 후 짝수 번의 라운드를 진행
• 각 라운드의 출력 블록이 다음 라운드의 입력 블록이 됨
• i번째 라운드 처리 과정
  • f: 라운드 함수
  •  kᵢ: 라운드 키

• 라운드 함수와 관계없이 역변환(복호화) 가능 → 라운드를 거꾸로 계산
  • 단, 복호화 할 때는 왼쪽 출력 부분을 라운드 함수 파라미터로 해야 됨 = f(Lᵢ₋₁, kᵢ)
• 두 번의 수행으로 블록 간의 완전한 확산이 이루어짐(짝수 번의 라운드를 진행하는 이유)
• DES, SEED 등 많은 블록 암호에 사용됨

②SPN(Substitution Permutation Network) 구조

• 하나의 입력 블록을 여러 개의 소블록으로 나눈 후 라운드를 진행
• 각 라운드의 출력 불록이 다음 라운드의 입력 블록이 됨
• i번째 라운드 처리 과정
  • 각 소블록을 S-box로 입력하여 치환
  • S-box 출력을 P-box로 전치
• 라운드 함수가 역변환 가능해야 함
• 더 많은 병렬성을 제공
• AES, ARIA 등 최근의 블록 암호에서 사용됨

🔸블록 암호의 사용 모드

• 각 블록에 블록 암호를 어떤 방식으로 사용할 것이냐에 따라 구분
  1. 전자 코드 북(ECB) 모드: 블록 암호의 개념 정도로만 생각
  2. 암호 블록 연결(CBC) 모드: 현재 자주 이용되는 모드
  3. 암호 피드백(CFB) 모드
  4. 출력 피드백(OFB) 모드
  5. 카운터(CTR) 모드: 현재 자주 이용되는 모드

① 전자 코드 북(Electronic Code Book, ECB) 모드

• 입력 받은 평문을 각각의 블록으로 나눈 뒤, 각각의 키를 가지고 블록 암호를 돌려서 암호문을 생성
• 암·복호화 시 병렬처리 가능
• 암호문 블록의 오류가 다른 블록에 영향을 미치지 않음
• 동일한 평문 블록은 동일한 암호문 생성(패턴 분석 가능) → 요즘 잘 사용하지 않는 이유

② 암호 블록 연결(Cipher Block Chaning, CBC) 모드

• XOR 연산 추가, 다음 평문은 직전의 암호문과 XOR → 암호화 시 병렬처리 불가능(복호화할 때는 병렬처리 가능)
• 암호화 시 평문 블록 오류가 그 다음 모든 암호문에 영향 → 메시지 인증에 사용

③ 암호 피드백(Cipher FeedBack, CFB) 모드

• 암호화 시 특정 입력이 이후로 영향을 미침 → 메시지 인증에 사용
• 복호화 함수 필요 없음

④ 출력 피드백(Output FeedBack, OFB) 모드

• 암호문 블록의 오류는 한 블록에만 영향을 미침 → 영상이나 음성 같은 디지털 신호화된 아날로그 신호에 사용
• 복호화 함수 필요 없음

⑤ 카운터(CounTeR, CTR) 모드

• 암·복호화 시 병렬처리 가능
• 오류의 확산이 일어나지 않음
• 복호화 함수 필요 없음

2. 스트림 암호

• 평문과 같은 길이의 키 스트림을 생성하여 평문과 키를 비트 단위로 XOR하여 암호문을 얻는 대칭키 암호 방식

🔸키 스트림

• 임의의 길이의 평문이 주어져도 동일한 길이의 키 스트림 생성 가능
• 규칙성이 없어 예측이 불가능한 랜덤 수열이 가장 안전
• 의사 랜덤(pseudorandom) 수열 생성
  • 예측이 어려우면서도 자동화된 생성이 가능
  • Ex) LFSR

🔸선형 귀환 시프트 레지스터(Linear Feedback Shift Register, LFSR)

• 직전 m개의 비트값을 선형 결합하여 새로운 한 비트값을 생성

• 주기: 최대 2ᵐ-1 비트 길이
• LFSR 단독 사용은 쉽게 해독됨

✅ 대칭키 암호 알고리즘

① DES(Data Encryption Standard)

• 1977년 미국에서 데이터 암호 알고리즘의 표준으로 공표
• 블록 암호 알고리즘
  • 블록 크기: 64bits
  • 키 길이: 56bits
  • 파이스텔 구조: 16라운드, 라운드 키 길이 48bits
• 컴퓨터 속도 개선과 암호해독기술의 발전으로 2001년 AES에 표준 자리를 물려줌

②TDEA(Triple Data Encryption Algorithm)

• DES를 3회 반복(3DES)

• DES의 짧은 키 길이로 인한 안정성 문제 해결
• DES보다 3배 정도 느림

③AES(Advanced Encryption Standard)🔸

• DES를 대신하는 새로운 표준
• 2001년 미국 NIST에서 공표(공모를 통해 Rijndael을 AES로 선정)
• 블록 암호 알고리즘
  • 블록 크기: 128bits
  • 키 길이: 128bits, 192bits, 256bits 중 택일
  • SPN 구조

• AES 구성

• AES 암호화 과정
  • 라운드 1 ~ 라운드 Nᵣ-1
    • SubBytes: 비선형을 갖는 S-Box로 바이트 단위 치환
    • ShiftRows: 행 단위로 순환 시프트
    • MixColumns: 열 단위로 혼합
    • AddRoundKey: 라운드 키를 XOR
  • 라운드 Nᵣ (마지막 라운드)
    • SubBytes
    • ShiftRows
    • AddRoundKey

그 외의 대칭키 알고리즘

🔑 암호

-  두 사람이 안전하지 않은 채널을 통해 정보를 주고받더라도 제 2자는 이 정보의 내용을 알 수 없도록 하는 것

-  기밀성을 보장하기 위한 필수적인 기술

• 평문(plaintext): 원래의 메세지
• 암호문(ciphertext): 코드화된 메세지
• 암호화(encryption): 평문 → 암호문
• 복호화(decryption): 암호문 → 평문
• 키(key): 암호화와 복호화를 위한 가장 중요한 열쇠

🔸암호의 역사

- 초장기엔 주로 군사와 정치적인 목적으로 사용

-  컴퓨터와 통신이 결합됨에 따라 불법 사용자의 봉쇄 또는 데이터 위조 및 변조를 막는 수단으로 이용

-  최근엔 인터넷 뱅킹에 사용되는 공동인증서, 금융인증서, 보안 키패드, 메신저의 비밀 채팅 등에 여러 분야에서 이용

일반적인 암호의 요건(Kerchoff의 원리)
제 3자에게 암호 알고리즘을 알려주더라도 제 3자가 키를 모르면 암호를 풀 수 없다는 것을 가정

1. 고대암호

①전치법(permutation 혹은 transposition cipher)

• 평문에 있는 문자들의 순서를 바꿈으로써 암호화하는 기법

가장 단순한 방식: 두 문자씩 앞뒤로 섞는 방법	스파르타의 봉 암호

②치환법(substitution ciper)

• 평문의 문자들을 다른 문자로 치환함으로써 암호화하는 기법
• 치환 규칙에 따라 암호화 및 복호화

시저 암호 평문의 각 문자를 알파벳 순서상 세 문자 뒤에 위치하는 문자로 치환

*key

시프트 암호 평문의 각 문자를 알파벳 순서상 k번째 뒤 문자로 치환(0 ≤ k ≤ 25)

*key

비즈네르 암호 시프트 암호를 개선한 새로운 치환법으로 키는 여러 개의 정숫값을 사용

2. 근대암호

• 20세기 들어 암호에 대한 연구가 활발하게 진행됨
  • 통신기술의 발전, 기계식 계산기에 대한 연구
  • 두 차례의 세계대전을 통해 암호설계와 해독에 대한 필요성 증가
• 1949년 섀넌(shannon)
  • 일회성 암호체계(one-time pad)가 안전함을 증명
  • 암호체계 설계의 두 가지 기본원칙 제시
    1. 혼돈(confusion): 평문과 암호문 사이의 상관관계를 숨김
    2. 확산(diffusion): 평문의 통계적 성격을 암호문 전반에 확산시켜 숨김

3. 현대암호

①표준 암호 알고리즘의 등장

• 컴퓨터가 점차 발전하면서 데이터 보호에 대한 필요성 증가
• 1997년 미국 NBS(현 NIST)에서 표준 암호 알고리즘 공표
  • DES(Data Encrytion Standard): 대칭키 암호 알고리즘 → 2001년 새로운 표준 암호 알고리즘인 AES가 공표될 때까지 널리 이용됨

②공개키 암호 알고리즘의 등장

• 1976년 디피(Diffie)와 헬먼(Hellman)이 공개키 암호의 개념을 제시
  • 공개키 암호: 암호화와 복호화에 서로 다른 키를 사용
• 1978년 리베스트(Rivest), 샤미르(Shamir), 애들먼(Adleman)이 RSA 공개키 암호 알고리즘 개발
  • RSA: 소인수분해 문제에 기반을 둔 대표적인 공개키 암호 알고리즘

✅대칭키 암호

• 암호화와 복호화에 같은 키 하나를 사용하는 암호 방식
• 장점: 암호화와 복호화 속도가 빠름
• 단점: 키 분배 문제 존재
• 대표적인 알고리즘: DES, AES, IDEA 등

블록 암호 평문을 고정된 크기의 블록으로 나누어 각 블록마다 암호화 과정을 수행하여 블록 단위로 암호문을 얻는 대칭키 암호 방식	스트림 암호 평문과 같은 길이의 키 스트림을 생성하여 평문과 키를 비트 단위로 XOR하여 암호문을 얻는 대칭키 암호 방식

✅공개키 암호

• 암호화와 복호화에 두 개의 서로 다른 키를 사용하는 암호방식
  1. 공개키: 누구나 공개키를 이용하여 암호화 가능
  2. 개인키: 오직 자신만 개인키를 이용하여 복호화 가능
• 장점: 키 관리 쉬움, 키 분배 문제 해결 
• 단점: 대칭키 암호에 비해 속도가 느림
• 대표적인 알고리즘: RSA, ECC, EIGamal 등

🔸정보보호

• 정보를 여러 가지 위협으로부터 보호하기 위한 정책 및 기법
• 정보의 상태: 저장, 전달
• 위협의 종류: 허락되지 않는 접근/수정/훼손/유출 등

🔸컴퓨터보안

• 정보보호의 한 영역
• 컴퓨팅 환경이 관여된 모든 상황에 대한 정보보호
• 컴퓨팅 환경에 저장되거나 처리되는 정보를 다양한 위협으로부터 보호하기 위한 정책 및 기법

✅정보보호의 핵심 목표

1. 기밀성(Confidentiality)

• 허락되지 않는 자가 정보의 내용을 알 수 없도록 하는 것
  • 허락되지 않은 자가 정보에 접근을 아예 못하도록 함
  • 정보에 접근하더라도 무의미한 내용만 보이도록 함
• Ex) 자동화기기(ATM)의 비밀번호

2. 무결성(Integrity)

• 허락되지 않은 자가 정보를 임의로 수정할 수 없도록 하는 것
• 만약 허락되지 않은 자에 의한 수정이 발생했다면 이를 확인할 수 있는 것
• Ex) 자동화기기(ATM)의 계좌번호와 입출금정보

3. 가용성(Availability)

• 허락된 자가 정보에 접근하고자 할 때 이것이 방해받지 않도록 하는 것
• 즉, 정보에 대한 접근권한이 있는 자는 필요할 때 언제든지 정보를 사용할 수 있어야 함
• 정해진 시간 내에 정보를 볼 수 있음을 보장
• Ex) 자동화기기(ATM)의 서버, 네트워크, 사물(ATM기기)

🔸그 외 목표

- 부인방지(non-repudiation)

• 정보에 관여한 자가 이를 부인하지 못하도록 하는 것
  • 발신 부인방지: 정보를 보낸 사람이 나중에 정보를 보냈더는 것을 부인하지 못하도록 함
  • 수신 부인방지: 정보를 받은 사람이 나중에 이를 부인하지 못하도록 함

- 인증(authentication)

• 어떤 실체가 정말 주장하는 실체가 맞는지 확인할 수 있고 신뢰할 수 있는 것
  • 실체: 정보 자체, 정보를 이용하는 사용자 등

- 접근제어(access contral) 

• 정보에 대한 허락된 접근만 허용하고 그 외의 접근은 허용하지 않는 것
• 즉, 접근권한이 있는 자와 없는 자를 구분하여 제어
• 접근권한은 정보에 따라, 사용자에 따라 다양하게 부여될 수 있음

✅컴퓨터 보안의 역사

1. 컴퓨터의 등장

• 앨런 튜링(Alan Turing): 컴퓨터의 이론적인 개념을 정립. 제 2차 세계대전 당시 암호분석가로 활동하며 에니그마 암호문을 해독할 수 있는 일반적인 방법을 고안
• 1950년대와 1960년대
  • 메인프레임 형태의 컴퓨터들이 개발되어 기관이나 학교 등에서 이용
  • MIT의 TMRC(Tech Model Railroad Club)학생들이 해커(hacker)라는 용어를 처음 사용
    • 해커: 컴퓨터의 세세한 부분까지 적극적으로 탐구하고 활용성을 확대하기 위해 연구하는 것을 즐기는 사람
    • 크래커(cracker): 컴퓨터 보안에 위해를 가하는 악의적인 사람

2. 인터넷의 모체 등장

• ARPANET(Advanced Research Project Agency Network)
  • 1960년대 후반, 미국 국방부에서는 각 지역에 위치한 기관들의 컴퓨터를 연결하는 네트워크를 개발
  • 1970년대를 거치며 상당히 복합한 형태로 발전
  • 1980년대 인터넷 등장

3. 개인용 컴퓨터의 등장

• 1970년대
  • 애플 컴퓨터에서 개인용 컴퓨터(PC) 판매 시작
  • 연구자 뿐만 아니라 일반인도 컴퓨터를 접할 수 있게 됨
• 1980년대
  • IBM에서 저가 PC판매를 시작하며 컴퓨터가 대중화
  • TCP/IP가 개발되며 누구나 PC와 인터넷으로 다양한 정보를 접할 수 있는 환경이 만들어짐
  • 악의적인 사람들도 역시 컴퓨터와 인터넷을 사용하게 되어 컴퓨터 보안의 필요성 증가

4. 다양한 위협 발생

• 1980년대
  • 모리스 웜(Morris worm): 인터넷으로 연결된 수천 대의 UNIX 컴퓨터를 감염
  • 이를 계기로 침해대응센터인 CERT 만들어짐
• 1990년대
  • 시티뱅크 시스템에 침입하여 자금 탈취
  • 여러 회사 시스템에 침입하여 각종 정보 탈취
  • 정부 시스템에 침입하여 걸프전 정보 탈취
• 2000년대
  • 야후, CNN, 아마존 등 접속자가 많은 몇 개의 사이트에 분산 서비스 거부(DDoS) 공격 발생
  • 서비스 중단을 목적으로 표적 서버, 서비스 또는 네트워크에 인터넷 트래픽을 대량으로 보내려고 시도하는 악의적인 사이버 공격의 형태
• 2010년대 중반부터 랜섬웨어 유행
  • 컴퓨터에 저장되어 있는 문서나 그림 파일 등을 암호화하여 사용자가 사용할 수 없게 만든 뒤, 암호를 풀기 위해서는 비트코인 등을 솜금하도록 유도함

01. 기본 개념

🔸데이터

• 관찰이나 측정을 통해 현실 세계에서 단순히 수집된 사실/값
• 적절한 처리를 거쳐야만 정보로서 가치를 가짐

🔸정보처리 시스템

• 데이터를 수집, 조직, 저장하고 정보를 생성, 분배하는 시스템
• 실세계의 방대한 데이터를 효과적으로 저장/운영하기 위한 기술이 필요 → "데이터베이스"

✅ 파일 처리 시스템 (데이터베이스 등장 전 사용)

• 정보 표현에서 1차원적인 저장 시스템
• 각 응용 프로그램이 특정한 응용을 위해 필요한 파일을 독립적으로 소유하고 관리

🔸파일 처리 시스템의 문제점

1. 데이터 종속성(data dependency)
   • 응용 프로그램과 데이터 사이의 1:1 상호 의존 관계
   • 파일 구성 요소, 접근 방식 등이 변경되면 해당 응용 프로그램도 함께 변경
2. 데이터 중복성(data redundancy)
   • 한 시스템에 동일 데이터가 여러 개 존재
   • 일관성, 보안성, 경제성, 무결성 확보 및 유지 곤란

→ 데이터 공용 불가➡️ "데이터베이스" 기술 등장

✅ 데이터베이스

• 한 조식의 여러 응용 시스템이 공유해서 사용하기 위한 통합, 저장, 운영 데이터의 집합

shared, 여러 응용 프로그램이 공동으로 소유하고 사용
integrated, 중복된 데이터를 배제하여 각 데이터의 일관성 유지
- 중복의 완전 배제가 아닌 "최소한의 제한적으로 통제한 범위 내에서의 중복"은 허용
stored, 컴퓨터가 접근 가능한 저장매체에 저장
operational, 어떤 조직의 목적과 유용성 측면에서 반드시 유지해야 할 데이터
- 단순한 입출력 데이터 및 처리 과정에서의 일시적인 데이터는 제외

🔸데이터베이스 특징

• 실시간 접근성
  • DB에 수시로 접근하는 사용자의 요구를 즉시 처리하여 응답을 제공
• 계속적인 변화
  • 삽입/삭제/갱신 등의 연산을 통해 새로운 데이터로 내용을 지속적으로 변화시킴 → 현실 세계의 상태를 정확히 반영한 데이터를 유지
• 동시 공유
  • 서로 다른 목적을 가진 여러 사용자가 동시에 원하는 데이터에 접근
• 내용에 의한 참조
  • 데이터가 저장된 위치/주소가 아닌 내용/값에 따라 데이터를 참조

🔸파일 처리 방식에 대해 향상된 특징

• 데이터베이스 시스템의 자기 기술성
  • DB 시스템은 DB 자체뿐만 아니라 DB에 대한 정의/설명까지 포함(DB에 속하는 각 파일의 구조, 각 항목의 타입과 저장 형식, 데이터의 제약 조건 등이 시스템 카탈로그에 저장)
• 프로그램-데이터 독립성
  • 데이터 파일의 구조에 대한 정보가 응용 프로그램으로부터 분리되어 관리
• 데이터 추상화
  • 사용자에게 상세 정보보다 데이터에 대한 개념적 표현을 제공 → 보다 용이한 데이터 접근이 가능
• 다중 뷰 제공
  • 한 DB에 대한 여러 사용자의 서로 다른 관점의 데이터 요구에 따라 필요한 부분만을 선별적으로 추출해서 볼 수 있는 기능 제공
• 데이터 공유
  • 여러 사용자가 동시에 DB에 접근할 수 있는 기능 제공
• 다수 사용자의 트랜잭션 처리
  • 동시성 제어 기능을 통해 다수 사용자가 동일 데이터를 동시에 변경하는 경우에도 데이터의 일관성을 보장

🔸데이터베이스의 장점

• 데이터의 *일관성
• 데이터의 *무결성
• 데이터의 보안
• 백업과 회복
• 표준화
• 응용 프로그램 개발 시간 단축
• 융통성
• 최신 정보의 가용성
• 규모의 경제성

*일관성: 현실 세계의 어느 한 사실을 나타내는 두 개 이상의 데이터 간의 일치 여부
*무결성: DB에 들어있는 데이터 값과 그것이 표현하는 현실 세계의 실제 값이 일치하는 정확성

🔸데이터베이스의 단점

• 운영비의 증대
• 백업과 회복의 오버헤드
• 복잡한 자료 처리
• 시스템의 취약성

02. 데이터베이스 시스템

✅ 데이터베이스 시스템

• 데이터를 데이터베이스에 저장하고 관리해서 필요한 정보를 생성하는 컴퓨터 중심 시스템
• 구성요소
  • 데이터베이스
  • 데이터베이스 관리 시스템
  • 데이터 언어
  • 데이터베이스 사용자
  • 데이터베이스 관리자
  • 데이터베이스 기계

✅ 데이터베이스 시스템 구조

1. 외부 단계(뷰 단계)
   • 각 사용자가 바라보는 개인적인 수준의 DB에 관한 것
2. 개념 단계(논리적 단계)
   • 범기관적(조직) 입장에서 DB의 전체 구조를 추상화하는 단계
   • 물리적 저장구조의 세부 사항을 은폐하고, 어떤 데이터가 저장되었는지와 데이터 간에 존재하는 관계를 기술
3. 내부 단계(물리적 단계)
   • 저장장치 입장에서 데이터가 실제로 어떻게 저장되는가를 기술

🔸스키마(schema)

• DB 구조에 대한 정의와 제약 조건의 명세를 기술한 것
  • 3가지 관점 → 외부 스키마, 개념 스키마, 내부 스키마

1. 외부 스키마
   
   • =서브스키마: 전체 DB의 한 논리적 부분만을 표현
   • 개별 사용자(응용 프로그래머)가 관심을 두는 DB의 일부분만 기술
   • 개별 사용자마다 이에 대응하는 여러 개의 외부 스키마가 존재
   • 하나의 DB 시스템에는 여러 개의 외부 스키마가 존재
2. 개념 스키마
   • 모든 사용자/응용 프로그램이 필요로 하는 전체적이고 통합된 데이터베이스의 구조를 기술( )
   • 모든 데이터 개체들에 대한 정의, DB 접근 권한, 보안 정책, 무결성 규칙 등에 대한 명세를 포함
   • 모든 외부 스키마는 개념 스키마로부터 생성되고 지원됨
3. 내부 스키마
   
   • =저장 스키마: 개념 스키마에 대한 저장 구조를 정의
   • 물리적인 데이터 구조를 정의
   • 저장장치의 입장에서 데이터가 실제로 저장되는 방법을 기술
   • 저장 레코드 형식, 인덱스 유무, 저장 필드의 표현 방법, 저장 레코드의 물리적 순서 등을 기술
   • 물리적 레코드(페이지, 블록)와 저장장치의 특성(실린더, 트랙)은 고려하지 않음

🔸각 단계의 사상

- 각 스키마들을 매핑해주는

1. 외부/개념 사상 → 논리적 데이터 독립성
   • 특정 외부 스키마와 개념 스키마 사이의 대응 관계를 정의
   • 응용 프로그램에 영향을 주지 않고 DB의 논리적 구조의 변경이 가능
   • 하나의 논리적 구조로 많은 응용 프로그램이 요구하는 다양한 형태의 논리적 구조를 제공
2. 개념/내부 사상 → 물리적 데이터 독립성
   • 개념 스키마와 내부 스키마 사이의 대응 관계를 정의
   • 논리적 구조에 영향을 주지 않고 실제 데이터에 대한 저장 양식의 변경이 가능
   • 하나의 논리적 구조로 여러 가지 상이한 물리적 구조의 지원 가능

✅ 데이터베이스 관리 시스템(DBMS)

• 응용 프로그램이 데이터베이스를 공용할 수 있도록 관리해주는 소프트웨어 시스템
  • 사용자와 데이터베이스 사이에 위치하며 DB의 구성, 접근 방법, 관리 유지 등에 관한 모든 책임과 권한을 갖고 모든 기능을 통합적으로 수행하여 사용자의 요구에 맞는 정보를 생성해 주는 소프트웨어
• 목적
  • 응용 프로그램이 데이터에 종속되지 않는 데이터의 독립성 제공

🔸개념적인 수준의 작업 과정(in 관계형 데이터베이스 관리 시스템)

• 사용자는 SQL과 같은 언어를 이용하여 데이터 접근을 요구
• DBMS가 요구를 받아 분석
• 외부스키마, 대응하는 외부와 개념 스키마 접속, 개념 스키마, 개념과 내부 스키마 접속 그리고 기억장소 구조 정의순으로 차례대로 검토
• 저장된 데이터베이스에 필수적인 연산을 수행

필수 기능

• 정의(definition)
  • 물리적으로 구현된 하나의 DB 구조로부터 여러 사용자들의 다양한 요구에 부응할 수 있도록 가장 적합한 DB 구조를 정의하는 기능
• 조작(manipulation)
  • 사용자와 DB 사이의 상호작용을 위한 수단 → 사용자가 연산 도구를 통해 DB에 체계적으로 접근하고 조작할 수 있는 기능
• 제어(control) 
  • 공용 목적으로 관리되는 DB의 내용을 정확하고 안전하게 유지시키는 기능 → 데이터 무결성 유지, 보안 유지 및 권한 검사, 동시성 처리 등

✅ 데이터 언어

• DBMS와의 통신 수단
  • 기능/목적에 따라 → 데이터 정의어, 데이터 제어어, 데이터 조작어

▪️ 데이터 정의어(DDL, Data Definition Language)

• DB의 구조, 데이터 형식, 처리 방식 등을 정의하는 언어
  • 개념 스키마를 정의하기 위해서 주로 사용
  • 데이터베이스 설계자 또는 관리자가 주로 사용
• 3단계의 데이테베이스 시스템 구조가 명확하게 구분되는 경우
  • 뷰 정의어: 외부 스키마를 정의하기 위한 언어
  • 기억장소 정의어: 내부 스키마를 정의하기 위한 언어

▪️ 데이터 제어어(DCL, Data Control Language)

• 데이터 공유와 정확하고 안전한 사용을 위해 데이터 제어를 정의하고 기술하는 언어
  
  • 데이터베이스 관리자가 사용해서 데이터 보안, 무결성, 데이터 회복, 동시성 제어 등과 관련된 명령어들을 통해서 데이터를 관리

▪️ 데이터 조작어(DML, Data Manipulation Language)

• DB에 대한 검색, 수정, 삽입, 삭제 등의 조작을 위한 언어
• 절차적 데이터 조작어
  
  • 필요한 데이터를 어떻게(how)구하는 지를 명시해야 하는 조작어
  • 응용 프로그램 속에 삽입되어 사용 → 한 번에 하나의 레코드를 검색하여 처리
  • "one-record-at-a-time 데이터 조작어", "저수준 데이터 조작어"
• 비절차적 데이터 조작어
  • 어떻게 구하는지는 명시하지 않고, 어떤(what) 데이터가 필요한지만을 명시
  • "선언적 언어", "고수준 데이터 조작어"
  • 질의어(SQL), 데이터 부속어

✅ 데이터베이스 사용자

- 데이터베이스에 접근하는 사람의 총칭

• 일반 사용자: 터미널에서 SQL과 같은 질의어로 DB의 정보에 단순히 접근하는 사람
• 응용 프로그래머: 일반 호스트 언어와 데이터 부속어를 통해 DB에 접근하는 사람
• 데이터베이스 관리자: 데이터베이스 시스템 별도의 한 구성요소로 취급

✅데이터베이스 관리자(DBA, DataBase Administrator)

• DDL과 DCL를 통해 DB를 정의하고 제어할 목적으로 접근하여 관리하는 사람
• 데이터를 여러 사람이 공용할 수 있도록 관리하고 제어하는 사람
• DB에 대한 접근 권한 설정, 제작과 갱신, 보전과 관리, 성능 변경 요구에 대한 응답 등의 의무를 가짐
• 조직의 모든 전산 업무, DBMS, 관련 H/W와 S/W 등에 대한 상당한 지식이 필요

✅ 데이터베이스 기계

- "데이터베이스 컴퓨터"

• DB 관리 기능을 효율적으로 수행할 수 있도록 특화되어 설계된 하드웨어/소프트웨어
• 후위 처리기, 지능형 저장장치, 내용에 의한 참조 메모리, 병렬 처리, 데이터베이스 연산기 등을 포함

03. 데이터 모델링 & 개체-관계 모델

✅ 데이터 모델링

• 현실 세계의 데이터를 데이터 모델 상의 데이터베이스 구조로 변환하는 과정
• 실세계의 일부분을 DB 시스템이 지원하는 데이터 모델의 형태로 DB를 표현하는 과정

▪️ 데이터 모델

• 데이터 타입, 데이터의 연산, 데이터의 의미 및 일관성 제약 조건 등의 DB 구조를 명시하기 위한 개념의 집합
• 지원하는 개념의 타입에 따라 → 개념적 모델, 논리적 모델, 물리적 모델

🔸개념적 모델

• 현실 세계에서 주요 데이터를 추출하여 개념 세계의 데이터로 변환하는 과정에서의 모델
  • 사용자가 데이터를 인식하는 방법과 밀접한 개념 제공
• 대표적 모델: 개체-관계 모델(E-R 모델)

🔸E-R(Entity-Relationship)모델

• 개체 타입과 이들 간의 관계 타입을 이용해서 실세계를 사람이 이해할 수 있도록 개념적으로 표현하는 방법
  • 그래프에 기반을 둔 모델 → "개체-관계 다이어그램(ERD)"

✅ 개체

• 데이터로 표현하려는 실세계의 유무형의 모든 것
  • 컴퓨터 파일구조에서 하나의 레코드에 대응
• 하나 이상의 속성으로 구성
  • 속성
    • 데이터의 가장 작은 논리적 단위
    • 각 개체의 특성이나 상태를 설명
    • 컴퓨터 파일 구조에서 필드에 대응
  • 종류: 단일값 속성, 다중값 속성, 단순 속성, 복합 속성, 유도 속성 등

✅ 관계

• 개체 집합 사이의 대응성(사상)을 의미
• 개체 집합 간의 관계 정보를 표현하는 수단
  • 미리 어떤 관계를 정의해 놓고 주어진 값을 정의된 관계에 따라 해석하면 유용한 의미 표현이 가능

🔸개체 간의 관계

▪️ 두 개체 집합 X와 Y 관계에서

• "개체 Y가 개체 X에 종속되어 있다"
  • 개체 X가 존재하는 경우에만 개체 Y가 존재할 수 있고, 개체 X가 삭제되면 Y도 함께 삭제되는 경우
  • 개체 X = 오너 개체, 개체 Y = 약한 개체
• "전체 참여한다/필수적으로 참여한다"
  • 개체 X의 모든 인스턴스가 관계에 반드시 참여하는 경우 
  • ↔ "부분 참여한다, 선책적으로 참여한다"

✅E-R다이어그램

🔸논리적 모델(구현 모델)

• 개념 세계의 데이터를 데이터베이스에 저장할 구조로 표현하는 과정에서의 모델
  • 개념적 모델과 물리적 모델의 중간에 위치한 모델
  • 데이터 구성에 대한 세부적인 사항은 숨기고 사용자가 이해할 수 있는 정도의 데이터 저장에 대한 개념 제공
• 종류: 계층형 모델, 네트워크형 모델, 관계형 모델, 객체지향형 모델, 객체 관계형 모델

계층형 모델	네트워크형 모델(망형 모델)	관계형 모델
▪️ 트리 형태로 표현 ▪️ 두 개체 사이의 관계 → 1:n 관계 = 부모-자식 관계	▪️ 그래프 형태로 표현 ▪️ 링크로 표현된 데이커 간의 관계 → 오너-멤버 관계	14강 참고
객체지향형 모델	객체 관계형 모델
▪️ 데이터와 절차를 일체화된 단위로 다루는 객체 지향의 개념을 잘 모아서 정의해 높은 집합 - 실세계에서 존재하는 개념적 객체를 중심으로 모델링 하는 방식	▪️ 관계형 모델과 객체지향형 모델의 장점을 결합한 가장 진보된 형태 - 관계형 시스템에서 새로운 객체 저장 능력을 추가한 형태

🔸물리적 모델

• 저장장치 입장에서 데이터가 어떻게 저장되어 있는지에 대한 세부적인 사항을 기술하는 개념 제공
  • 레코드 형식, 레코드 순서, 접근 경로 등의 정보 제공

01. 정렬 알고리즘: 퀵 정렬, 합병 정렬

✅ 퀵 정렬

• 특정 데이터를 기준으로 입력 배열을 두 부분 배열로 분할하고, 각 부분 배열에 대해서 독립적으로 퀵 정렬을 순환적으로 적용하는 방식
• 평균적으로 가장 좋은 성능의 비교 기반 알고리즘: O(nlogn)

▪️ 피벗(pivot, 분할원소)

• 두 개의 부분 배열로 분할할 때 기준이 되는 데이터
• 보통 주어진 배열의 첫번째 원소로 지정

▪️ 피벗이 제자리를 잡도록 하여 정렬하는 방식

🔸분할(partition) 과정

🔸특징

• 분할 정복 방법을 적용한 알고리즘
  • 분할: 정렬한 n개 데이터를 피벗 중심으로 두개의 부분 배열로 분할
  • 정복: 두 부분 배열에 대해 퀵 정렬을 각각 순환적으로 적용하여 두 부분배열을 정렬
  • 결합: 필요 없음

🔸성능

• 분할 과정의 수행 시간 = O(n)
• 최선 수행시간 = O(nlogn)
  • 피벗을 중심으로 항상 동일한 크기의 두 개의 부분 배열로 분할 되는 경우

• 최악 수행시간 = O(n^2)  ←피벗 선택의 임의성만 보장되면 평균 수행 시간을 보일 가능성이 높음!
  • 피벗만 제자리를 잡고 나머지 모든 데이터가 하나의 부분 배열로 분할되는 경우
  • 피벗이 배열에 항상 최대값 또는 최소값이 되는 경우
  • 입력 데이터가 이미 정렬되어 있고, 피벗을 맨 왼쪽 원소로 지정한 경우 

✅ 합병 정렬

• 동일한 크기의 두 개의 부분 배열로 분할하고(쪼개지지 않을 때까) 각 부분 배열을 순환적으로 정렬한 후, 정렬된 두 부분의 배열을 다시 합병하여 하나의 정렬된 배열을 만드는 방식

▪️ 전체 수행 과정

▪️ 합병(merge) 과정

🔸특징

• 분할 정복 방법을 적용한 알고리즘
  • 분할: 정렬한 n개 데이터를 n/2개의 데이터를 갖는 두 부분배열로 분할
  • 정복: 두 부분배열에 대해 합병 정렬을 각각 순환적으로 적용하여 정렬
  • 결합: 정렬된 두 부분 배열을 합병하여 하나의 정렬된 배열을 만듦
• 최선, 최악, 평균 수행 시간 = O(nlogn)

02. 순차 탐색, 이진 탐색

▪️ 탐색

• 주어진 데이터 집합에서 원하는 값을 가진 데이터를 찾는 작업
  • 순차 탐색(sequential search) = O(n)
  • 이진 탐색(binary search) = O(logn)
  • 이진 탐색 트리(binary search tree) = O(logn) O(n)

✅ 순차 탐색

• 리스트 형태로 주어진 데이터를 처음부터 하나씩 차례대로 비교하여 원하는 값을 가진 데이터를 찾는 방법

▪️ 성능 = O(n)

• 탐색 실패의 경우 → n번 비교
• 탐색 성공의 경우 → 최소 1번, 최대 n번, 평균(n+1)/2번 비교

▪️ 특징

• 모든 리스트(배열, 연결리스트)에 적용 가능
• 데이터가 키값과 관련해서 아무런 순서 없이 단순하게 연속적으로 저장된 경우에 적합 → 데이터가 정렬되지 않은 경우에 적합

✅ 이진 탐색

• 정렬된 입력 배열에 대해서 주어진 데이터를 절반씩 줄여가면서 원하는 데이터를 찾는 방법
  • 분할 정복 방법을 적용한 알고리즘

▪️ 탐색 방법

• 입력 배열의 가운데 값(A[(a시작인덱스+b끝인덱스)/2])과 탐색키를 비교
  • 탐색키 = 배열의 가운데 값 → 탐색 성공(배열의 인덱스 (a+b)/2 반환)
  • 탐색키 < 배열의 가운데 값 → 이진 탐색(배열의 전반부)
  • 탐색키 > 배열의 가운데 값 → 이진 탐색(배열의 후반부)

▪️ 수행 과정

▪️성능 = O(logn)

• 한 번 탐색할 때마다 탐색 대상이 되는 데이터 개수 1/2씩 감소

▪️ 특징

• 데이터가 이미 정렬된 경우에만 적용 가능
  • 삽입/삭제 연산 시 정렬 상태를 유지하기 위해 데이터의 이동 발생 → 삽입/삭제가 빈번한 응용 분야에는 부적합

03. 이진 탐색 트리

🔸이진 트리

• 각 노드의 왼쪽 서브트리에 있는 모든 키값은 그 노드의 키값보다 작다
• 각 노드의 오른쪽 서브트리에 있는 모든 키값은 그 노드의 키값보다 크다

▪️ 탐색 연산

• 루트 노드에서부터 키값의 비교를 통해 왼쪽/오른쪽 서브트리를 따라 이동하면서 원하는 데이터를 찾음

▪️ 삽입 연산

• 삽입할 데이터를 탐색한 후, 탐색이 실패한 위치에 새로운 노드를 자식 노드로 추가
  • 탐색이 성공한 경우(값이 있는 경우) → 삽입 없이 종료

▪️ 삭제 연산

📌 후속자(successor, 계승자) 노드

- 삭제되는 노드의 자식 노드 개수에 따라 구분해서 처리

1. 자식 노드가 없는 경우(리프 노드의 경우)
   • 남은 노드의 위치 조절이 불필요
2. 자식 노드가 하나인 경우
   • 자식 노드를 삭제되는 노드의 위치로 올리면서 서브트리 전체도 따라 올린다
3. 자식노드가 두 개인 경우
   • 후속자 노드를 삭제되는 노드의 위치로 올린다
   • 후속자 노드의 자식 노드 개수에 따라 다시 삭제 연산을 처리한다

삭제 연산 예시

▪️성능  = O(logn) / O(n)

• 키값의 비교 횟수에 비례 → 트리의 높이가 h라면 O(h)

01. m원 탐색 트리

🔸이진 탐색 트리(BS 트리; binary search tree)

• 트리에서 특정 데이터를 검색하고, 노드의 삽입/삭제 연산이 자주 발생하는 응용 문제에 가장 효과적인 이진 트리
• 왼쪽과 오른쪽이라는 방향성을 가지며 다루기가 매우 편리함
• 부모 노드를 중심으로[부모 보다 큰 데이터 노드]와 [부모 보다 작은 데이터 노드]로 구분됨
  • =왼쪽 서브 트리와 오른쪽 서브 트리의 중간 값은 이들의 부모 노
• 일반적으로 노드의 개수가 많아지면 트리의 높이가 커지게 됨
• BS 트리가 2원(2-way) 탐색 트리임

✅ m원 탐색 트리

• 트리의 노드가 m개 이하의 가지를 가질 수 있는 탐색 트리 => 같은 수의 노드를 갖는 이진트리보다 낮은 높이의 m원 트리
  • m원: 탐색 트리가 가질 수 있는 자식 노드들의 개수
• 이진 탐색 트리의 확장된 형태
• 탐색 트리의 제한을 따르되 2개 이상(m개 이하)자식을 가질 수 있음

✅ m원 탐색 트리의 제한 조건

▪️ m원 탐색 트리 - 3원 탐색 트리

• 3원 탐색 트리는 최대 3개의 자식 노드를 가질 수 있음 == (정렬된) 키 값은 최대 2개
• 키 값들과 서브트리들의 값의 관계 확인 (어떤 것은 작고, 어떤 것은 크고, 어떤 것은 사잇값인지를 확인)
  • 만약 키값이 60, 62이면 첫번째 자식 노드의 값은 60보다 작아야 하고, 두번째 자식 노드는 60과 62 사이의 값이어야 하고, 세번째 자식 노드는 62보다 큰 값이어야 함

🔸m원 탐색 트리 노드의 구조

🔸m원 탐색 트리의 탐색 연산

🔸m원 탐색 트리의 탐색

• 일반적으로 노드의 가지 개수가 많을수록(서브트리가 많을 수록), 최대 탐색 길이는 짧아짐(트리의 깊이가 얕으므로 더 빨리 찾을 수 있음)
• 예를 들어, 키가 255개인 경우 4원 트리로 구성하면 최대 경로 길이가 4가 됨

02. B 트리

✅ B 트리

• m원 탐색 트리는 서브트리의 균형에 대해서는 특별히 제한하지 않았음
• 각 노드가 자식을 많이 갖게 하여 트리의 높이를 줄이고 전체적으로 균형을 유지한다면 탐색 성능을 더욱 향상할 수 있음
• m원 탐색트리를 개선한 B트리는 인덱스 구조를 구현하는데 가장 일반적으로 사용함
• 차수  m인 B 트리의 탐색 경로 길이는 같은 개수의 키를 가지는 이상적인 m원 탐색 트리보다 길 수 있지만 키값을 삽입/삭제할 때 B트리를 유지하는 것이 더 쉬움

✅ B 트리의 조건

• 루트와 잎노드를 제외한 트리의 각 노드는 최소 [ m/2 ]개의 서브트리를 갖는다
  • 루트와 잎노드를 제외한 트리의 각 노드는 언제나 하나의 키값 혹은 두 개의 자식 노드를 가져야 함
• 트리의 루트는 최소한 2개의 서브트리를 갖는다
• 트리의 모든 잎노드는 같은 레벨에 있다

* [ ] 가우스 함수: 소수점을 포함하는 수를 그것보다 1큰 정수로 바꿈
예) [3/2] = [1.5] = 2

🔸B 트리에 키를 삽입하는 알고리즘

🔸B 트리의 노드 삽입

🔸B 트리에서 키를 삭제하는 알고리즘 - 잎노드에서 삭제

삭제할 키값을 포함한 노드를 찾는다

• 잎노드에서 삭제하는 경우
  1. 노드에서 키값을 삭제한다.
  2. 필요하면 재배열한다.

🔸B 트리에서 키를 삭제하는 알고리즘 - 내부노드에서 삭제

내부노드의 키값은 하위 노드에 대한 기준값(중간값)이기 때문에 삭제 시, 대체할 수 있는 적절한 값을 찾아야 한다.
보통 왼쪽 서브트리의 가장 큰 키값 또는 오른쪽 서브트리의 가장 작은 키값으로 대체할 수 있다. 이들은 모두 잎노드에 위치한다.

• 새로운 기준값(삭제된 자리에 올 키값)을 선택하여 해당 (잎)노드에서 삭제하고 그 값을 현재 키값을 삭제한 자리로 옮긴다. 즉 대체한 것이다.
• 기준값으로 대체하기 위해 키를 삭제한 잎노드가 정해진 개수의 키값을 갖지 않으면 트리를 재배열 한다.

▪️ 40 삭제(내부노드에서 삭제)

• 40을 삭제하면 중간값을 오른쪽 서브트리의 가장 앞에 있는 값을 올려줌
  • 키값이 부족한 노드의 오른쪽 형제가 존재하고 키 개수가 여유있다면 오른쪽 키값의 가장 앞에 있는 것을 부모 노드로 한다는 규정

03. B*, B+ 트리

✅ B* 트리의 정의

• 노드의 약 2/3 이상이 채워지는 B 트리 → 높이가 더 줄어듬(B트리는 1/2)
• 노드가 꽉 차면 분리하지 않고, 키와 포인터를 재배치하여 다른 형제 노드로 옮김
• 삽입/삭제 시 발생하는 노드 분리를 줄이려고 고안됨

✅ B* 트리의 조건

차수가 m인 B* 트리는 다음 조건을 만족하는 B트리이다

① 공집합이거나 높이가 1 이상인 m원 탐색 트리이다
② 루트 노드는 2개 이상 2 ⌊ (2m-2)/3 ⌋ + 1개 이하의 자식노드를 갖는다
③ 내부노드는 최소한 ⌈ (2m-1)/3 ⌉개의 자식노드를 갖는다
④ 모든 잎노드는 동일한 레벨에 놓인다
⑤ 포인터가 k개인 잎이 아닌 노드는 k-1개의 키를 갖는다(루트노드 포함)

✅ B+ 트리의 정의

• 탐색 트리로 구성하면 매우 빠르게 탐색할 수 있지만, 전체 데이터를 차례로 처리하기는 불편함
  • => 데이터 전체를 이진 탐색 트리로 구성해놓으면 검색은 빠르지만! 전체 데이터를 다 찾아서 제일 큰 값부터 차례로 출력할 때는 굉장히 복잡
  • 매번 왼쪽인지 오른쪽인지 비교해가면서 다음 노드를 찾아가면서 처리해야 함
  • 스택을 써서 프로그래밍 하기 때문에 pop(), push() 연산이 추가되면 속도가 굉장히 느려짐
• B+ 트리는 인덱스된 순차 파일을 구성하는데 사용됨
• B 트리와 같이 각 노드의 키가 적어도 1/2이 채워져야 하는 점은 같음
• 잎노드를 순차적으로 연결하는 포인터 집합이 있다는 점에서 다름
  • 잎노드의 마지막 포인터를 다음 키값을 갖는 노드를 가리킴
  • 순차 처리를 할 때는 이 포인터를 이용해서(키값을 비교하지 않고) 차례로 다음 데이터에 접근해서 처리
• 모든 키값이 잎 노드에 있고 그 키값에 대응하는 실제 데이터(파일 내용)에 대한 주소를 잎노드만이 가지고 있음
  • 직접 탐색은 잎노드에 도달해야 종료
  • 중간노드는 잎노드를 찾아가기 위한 징검다리 역할

01. 이진 탐색 트리

✅ 이진 탐색 트리(binary search tree)

• 특정 데이터를 검색하고, 노드를 삽입/삭제하는 응용 문제에 가장 효과적인 이진 트리
• 탐색에 최적화된 이진 트리
• 키: 이진 트리 노드의 데이터(노드를 특정할 수 있는 값)

노드 Vᵢ의 키를 Kᵢ라 할 때 각 노드 Vᵢ가 다음을 만족하는 이진트리를 이진 탐색 트리(BS 트리)라고 함

1. Vᵢ의 왼쪽 서브트리에 있는 모든 노드의 키값은 Vᵢ의 키값보다 작다
2. Vᵢ의 오른쪽 서브트리에 있는 모든 노드의 키값은 Vᵢ의 키값보다 크다

같은 순서 데이터에 대해서 BS 트리를 다양하게 만들 수 있음

✅ BS 트리 순회

🔸BS 트리를 위한 노드 정의

🔸BS 트리의 중위 순회

🔸BS 트리의 노드 탐색

 BS 트리에서 키값이 K인 노드를 찾는 과정

① 트리가 비어있다면 탐색 실패, 비어있지 않다면 k와 현재 루트 노드의 키값 kᵢ를 비교한다.

② k = kᵢ 일 경우 탐색 성공, 이때 찾은 정점은 vᵢ 이다.

③ k < kᵢ 이면 vᵢ의 왼쪽 서브 트리를 탐색한다. 즉, vᵢ = vᵢ ,left로 바꾸고 ①로 간다.

④ k > kᵢ 이면 vᵢ의 오른쪽 서브 트리를 탐색한다. 즉, vᵢ = vᵢ ,right로 바꾸고 ①로 간다. 

🔸BS 트리의 노드 삽입 연산

BS 트리의 노드 삽입 연산

① 트리가 비어있다면 키 k를 가지는 노드를 삽입한다. 그렇지 않으면 k와 현재 루트 노드의 키 kᵢ를 비교한다.

② k = kᵢ 일 경우 멈춘다.

③ k < kᵢ 이면 vᵢ의 왼쪽 서브 트리에 삽입해야 하므로 vᵢ = vᵢ → left로 바꾸고 ①로 간다.

④ k > kᵢ 이면 vᵢ의 오른쪽 서브 트리에 삽입해야 하므로 vᵢ = vᵢ → right로 바꾸고 ①로 간다.

예)

🔸BS 트리의 노드 삭제

• 자식을 하나만 갖는 노드를 삭제하는 경우, [삭제한 노드를 가리키던 포인터]가 [그 노드의 null이 아닌 서브트리의 루트]를 가리키게 할당함
• 리프 노드의 경우 추가적인 작업 없이 바로 삭제 

• 두 개의 자식 노드를 가지는 노드는 삭제 시, 항상 특정 방향의 자식 노드를 올리는 방법으로 구현(항상 오른쪽(왼쪽) 자식 노드를 삭제 위치로 이동)
  • 특정 방향은 PM이 프로젝트 전에 미리 결정해둔대로 따름
• 구조를 가장 최소로 변화시키는 노드를 선택해서 삭제!

• 이진 트리 탐색을 사용하다 보니 탄생한 여러 트리들
  • splay 트리: 데이터 또는 키값을 찾을 때 예전에 찾았던 값을 또 찾는 경우가 생각보다 빈번하다는 입장에서 탐색 속도를 높이기 위해 만듬
  • BB 트리와 AVL 트리: 트리의 균형을 맞춤으로써 탐색의 속도를 높이려고 만듬

🔸이진 탐색 트리의 단점

• BS 트리의 성능은 트리의 구조와 특정 노드에 접근할 확률에 영향을 받음
• 트리의 성능이 구조에 영향을 받기 때문에 어떤 노드의 탐색/삽입/삭제를 위한 접근정보를 예측할 수 없는 상황에서는 최적의 BS 트리구조를 결정하기 어려움
• 휴리스틱 알고리즘(=경험적 알고리즘)을 사용하여 구축한 BS 트리의 성능이 최적에 가까움

🔸좋은 성능의 BS 트리를 구축하는 방법(휴리스틱)

1. 자주 탐색하는 키를 가진 노드를 트리의 루트에 가깝게 놓는다.
2. 트리가 균형(balance)이 되도록 유지한다. 즉, 각 노드에 대해 왼쪽과 오른쪽 서브트리가 가능한 같은 수의 노드를 갖게 한다.

02. Splay 트리

✅ Splay 트리

• 자주 탐색하는 키를 가진 노드를 루트에 가깝게 위치하도록 구성한 BS 트리
• Splay 연산: 최근에 접근한 노드 x를 (곧 사용할 것으로 예상하여) 루트에 위치시켜 트리를 재구성하는 연산
• Splay 트리: 가장 퇴근에 사용한 노드 x가 트리의 루트에 올 때까지 Splay 연산을 반복 적용하여 생성된 이진 트리

🔸Splay 트리의 연산

• 노드 x: 최근에 접근한 노드 
  노드 p: x의 부모 노드
• 노드 g: x의 조부모(부모의 부모) 노드

왼쪽 트리에 대해 7이 루트가 되도록 Splay연산을 적용

03. AVL 트리

✅ 변형 BS 트리 → AVL 트리

➡️ 노드의 삽입과 삭제가 일어날 때, 노드의 키값과 서브트리 키값 사이의 관계를 유지하면서 균형을 유지시키는 것이 쉽지 않음

🔸AVL 트리의 개념

• 제한 조건을 완화하여 트리가 (완전한) 균형이 아닌 것을 허용함
• 무너진 균형의 정도는 작아야 하고, 평균 탐색 길이도 완전 균형 트리의 탐색 길이와 크게 차이가 나지 않아야 함
• 거의 완전한 균형 트리의 한 형태로 높이가 균형 잡힌 높이 균형 트리(height balanced tree)
• 직접 탐색 성능이 매우 좋음

🔸AVL 트리의 조건

• 노드 vᵢ의 왼쪽 서브트리 높이와 오른쪽 서브트리 높이가 최대 1만큼 차이가 남

04. BB 트리

✅ BB(bound-balanced)트리

• 거의 완전히(대략) 균형 잡힌 트리의 다른 종류로 무게가 균형 잡힌 트리
• 각 노드의 양쪽 서브트리 무게가 균형을 유지하는 트리

✅ 균형 트리

• AVL 또는 BB 트리에 대하여 각각 무게 또는 크기(높이) 제한 조건을 만족시키는데 드는 비용은 트리를 완전히 균형 잡히게 유지하는 비용이나 노력보다 훨씬 작음
• 십입이나 삭제 후에 트리를 완전히 균형합지게 유지하기 위해서는 O(n)의 노드를 옮겨야 하는 반면에 AVL 또는 BB트리는 O(log₂n)개의 노드를 옮기면 되는 것으로 알려져있음

➡️ 완벽한 균형이 아닌 적당히 허용된 균형(AVL, BB)이 여러모로 더 좋음

01. 선택 트리

✅ 합병 정렬

• 차례로 정렬된 k개의 데이터 리스트를 완전한 순서를 유지하는 하나의 데이터 리스트로 만드는 과정
• 일반적으로 데이터 리스트가 k개인 경우 k-1번 비교를 통해 데이터 리스트에서 가장 큰/작은 값을 결정함
  • 데이터가 많을 수록 엄청난 비교 횟수(오버헤드) => 선택 트리를 이용하여 비교 횟수를 줄일 수 있음

✅ 승자 트리

• 비교 횟수가 많은 합병 정렬 대신 선택 트리를 이용하여 구현
• 부모 노드가 두 자식 노드보다 작은 값을 갖는 완전 이진 트리
• 작은 값이 승자가 되어 올라가는 토너먼트 경기와 유사
• 트리의 각 노드는 두 자식 노드 값의 승자를 자신의 값으로 함
• 결과적으로 루트의 값이 트리에서 가장 작은 값이 됨

=> 11 삭제 후, 24 추가하여 삭제되어 빈 부분을 비교하여 승자 트리 재구성

• 첫번째 단계에서의 비교 횟수를 줄이지는 못했지만, 두번째 비교 단계부터는 비교 횟수가 감소됨
• 재구성 과정에서 빈 리스트가 생기면 큰 값을 넣어즘

✅ 패자 트리

• 승자 트리보다 구현하기 쉬운 자료구조를 구상하다가 탄생(효율은 비슷)
• 각 노드가 두 자식 노드보다 더 작은 값을 갖는 완전 이진 트리라는 점은 승자 트리와 같지만! 패자 트리는 루트 노드 위에 최상위 0번 노드를 가짐
• 최상위 0번 노드에는 최종 승자를 저장함
• 트리의 각 내부 노드에는 승자가 아닌 패자를 저장(즉, 패자를 부모 노드에 저장하고 승자는 부모의 부모 노드로 올라가서 다시 경쟁)
• 루트에는 마지막 패자를 저장하고 최종 승자는 0번 노드에 저장

• 2레벨의 14는 4레벨의 14와 11을 비교해서 패자인 14를 넣은 것(2레벨 17은 4레벨의 12와 17을 비교)
• 1레벨의 12의 경우 2레벨의 내부 노드 값(패자)이 아닌 승자 값을 비교해서 패자인 12를 넣어줌(승자인 11은 0번 노드로)

• 재구성할 때는 자식과 자식간의 비교가 아니라 부모와 자식간의 비교!!

02. 숲

✅ 숲

• n(n>=0)개 이상의 분리된 트리 집합
• 트리에서 루트(혹은 다른 노드)를 제거하면 숲을 쉽게 얻을 수 있음 ↔ 숲을 연결하면 트리를 만들 수 있음

🔸숲의 이진트리 변환

🔸일반트리 → 이진트리(참고)

🔸숲 → 이진트리

• 숲을 하나의 통합된 자료구조에 넣어서 관리할 수 있음

03. 이진 트리 개수

🔸노드 개수에 따른 가능한 이진 트리

=> 순회 방법이 정해진 상태에서 출력되는 값들의 순서가 정해지면 이진트리는 제한된 개수만큼만 만들어짐

Q. 노드가 3개인 이진 트리에서 전위 순회 방문 순서가 1,2,3 이고 중위 순회 방문 순서가 1,3,2라면 위의 5개의 트리 중 어느 것일까?

A. 두번째 트리

▪️ 첫번째 트리 중위 순회 방문

▪️ 두번째 트리 중위 순회 방문

=> 어떤 이진 트리에 대한 [전위 순회와 중위 순회 방문 순서]가 주어지면 트리 구조는 유일하게(1개) 특정할 수 있음

01. 우선순위 큐

▪️ 큐: 먼저 들어간 데이터가 먼저 삭제되는 자료구조, 먼저 줄을 선 사람이 먼저 서비스를 받는 구조

▪️(힢을 이용한) 우선순위 큐: 대기 리스트에서 항상 우선순위가 높은 사람이 먼저 서비스를 받는 구조

🔸우선순위 큐의 배열 구현

• 데이터 삽입(Add_q()): 삽입 시, 우선순위를 고려하지 않고 순서대로 삽입

• 데이터 삭제(Delete_q()): 삭제 시, 우선순위 고려하여 삭제
  • Delete_q()에 의해 큐의 front 포인터에 있던 1이 삭제되면서 나머지 데이터 중에서 가장 작은 값인 2가 다음 삭제 위치(front가 가리키는 위치)로 이동됨

▪️ 우선순위 큐의 작동 방식

1. 삭제 명령이 실행되면 저장된 데이터 중에서 우선 순위가 가장 높은/낮은 데이터가 삭제됨
   • 10000건의 데이터가 있다고 가정했을 때 우선 순위대로 삭제 연산을 실행할 경우 9999번의 비교 필요 => 오버헤드 발생
   • 이를 해결하기 위해 자료구조 힢을 만듬 == 우선순위 큐를 구현하기 위해 힢을 고안
2. 나머지 데이터들은 어떤 순서로 저장되는 문제되지 않음

02. 힢

✅힢

• 피라미드 모양으로 쌓아 올린 더미이고 항상 맨 위에 있는 것을 먼저 꺼내는 구조
• 힢 추상 자료형
  • 힢 객체의 정의: 부모-자식 노드사이에서 부분적으로 정렬된 완전 이진트리로 부모노드는 자식노드보다 우선순위가 높음
  • 연산
    1. insert(element)::=힢에 데이터 삽입
    2. remove()::=힢(루트)에서 데이터 삭제
    3. peek()::=힢(루트)에서 데이터 읽어오기
    4. isEmpty()::=힢이 비었는지 확인
    5. size()::=힢에 저장한 데이터 개수 확인

🔸힢의 종류

① 최소 힢: 루트가 전체 노드 중에서 최소값을 가짐

• 트리의 모든 노드가 자식 노드보다 작은 값을 가짐(루트가 가장 작은 값을 갖고 부모는 자식보다 작은 값을 가짐)
• 트리의 레벨에 따라 데이터가 순서를 갖지는 않음
• 탐색 트리처럼 왼쪽 노드와 오른쪽 노드 사이에 크기 제한도 없음(=형제 노드 사이에서 크기 제한 없음)

② 최대 힢: 루트가 전체 노드 중에 최대값을 가짐

• 트리의 모든 노드가 자식 노드보다 큰 값을 가짐(루트가 가장 큰 값을 갖고 부모는 자식보다 큰 값을 가지면 됨)
• 트리의 레벨에 따라 데이터가 순서를 갖지는 않음
• 탐색 트리처럼 왼쪽 노드와 오른족 노드 사이에 크기 제한도 없음

🔸힢이 아닌 경우

03. 힢 노드의 삭제 및 삽입

🔸힢 구현을 위한 자료구조

• 배열을 이용한 힢의 구현: 완전 이진트리이기 때문에 배열로 구현해도 기억장소 낭비가 없음
  • 연결 리스트보다 실행 속도 면에서 효율적임
  • 기억장소 측면에서도 장점을 가짐 → 포인터 부분에 대한 영역을 따로 관리하지 않으니까

🔸힢의 노드 삭제

== 우선순위 큐에서 front가 가리키는 데이터를 삭제 == 힢에서는 루트 노드

🔸힢의 노드 삽입

• 데이터 삽입 후 확인해야할 것
  • 완전 이진 트리가 맞는가? YES
  • 부모와 자식 간의 관계가 다른 노들과 같은가? NO => 데이터 교환

01. 스레드 트리의 정의

이진 트리의 노드를 순회할 때, 방문하지 않고 지나쳐 온 노드들은 스택에 저장하여 관리해야 하는 번거로움이 발생함
*이진 트리의 노드 순회: 전위 순회, 중위 순회, 후위 순회

=> 이러한 방법을 사용하지 않고 놀고 있는 링크들을 사용하여 순회를 빠르게 하는 스레드 트리 탄생

✅ 스레드 트리

• '스레드'라는 포인터를 추가하여 트리 순회를 편리하게 한 것
• 스레드: 순회 방법에 따른 방문 순서를 유지하는 포인터

🔸세 가지 순회에 대한 스레드 트리

• 전위 순회(PLR)

• 중위 순회(LPR)

• 후위 순회(LRP)

02. 스레드 트리의 구현

🔸스레드의 구현 방법 - 포인터 필드의 추가

• 스레드를 저장하는 포인터를 추가하는 것

• 왼쪽 스레드 포인터, 왼쪽 자식 포인터, 데이터, 오른쪽 자식 포인터, 오른쪽 스레드 포인터 필드로 노드 구조를 정의함
  
  • 왼쪽 스레드: 해당 노드의 선행 노드를 가리킴
  • 오른쪽 스레드: 정해진 순회 순서에 따른 해당 노드의 후행노드를 가리킴
• 스택을 운영하지 않고도 쉽게 트리에 속한 모든 노드를 순회할 수 있지만 스레드를 위해 추가 기억장소를 사용한다는 부담이 생김

▪️ 포인터 필드의 추가

▪️ 추가된 포인터 필드를 이용한 중위 순회 연산과정

① 순회할 트리에서 가장 먼저 접근해야하는 노드를 가리키는 포인터 firstin을 매개변수로 하는 함수의 이름을 inorder()로 지정

② 노드를 가리킬 수 있는 TNode 타입의 포인터 p를 생성하고 firstin에 담긴 노드를 가리키도록 함

③ 포인터 p가 가리키는 데이터(info)를 출력하고 p를 p의 오른쪽 스레드 값으로 바꾸어(p→right_thread) 중위 순회에 따른 다음 노드를 가리키도록 수정함

④ 이 과정을 p가 null이 될 때까지 반복함

스레드를 이용한 전위 순회

• 자기 자식을 가리키는 것과 스레드가 동일한 경우가 많기 때문에 전위 순회를 할 거면 굳이 스레드를 추가해서 사용할 필요가 없음을 깨달음

🔸스레드의 구현 방법 - 노드의 빈 포인터 필드를 활용

• 기존 이진 트리의 노드 구조를 그대로 사용하면서 노드에 있는 사용하지 않는 포인터를 활용하는 방법
• 추가 기억장소를 사용하지 않아도 되는 장점이 있음!

• 잎 노드의 빈 포인터 필드의 활용
  • 이진 트리의 포인터 갯수(노드의 개수를 n개라 가정): 왼쪽 서브트리를 가리키는 포인터 n개+오른쪽 서브트리를 가리키는 n개 = 2n개의 포인터
  • 루트 노드를 제외한 전체 노드의 진입 차수 1 = 루트 노드를 제외한 전체 노드 즉, 누군가로부터 가리켜져야 할 노드의 개수: n-1
  • null이 아닌 포인터 개수: n-1
  • null 포인터 개수: 2n - (n-1) = n+1 그래서 이 null 포인터를 스레드로 활용
• 각 노드에 대해 포인터가 스레드로 사용 중인지, 서브트리에 대한 포인터인지를 구분하기 위해 태그 필드가 필요함(삽입/삭제 연산에서 반드시 필요)

▪️스레드를 이용한 전위 순회

• 전위 순회: 각 노드의 왼쪽 포인터 필드를 스레드로 사용하는 제한을 가정함
• 어떤 노드의 왼쪽 포인터가 실제 왼쪽 자식을 가리키면 그대로 두고, null이면 전위 순회로 순회할 대 다음으로 순회되는 노드를 가리키도록 지정

▪️ 스레드를 이용한 중위 순회

• 어떤 노드 X에 대해 오른쪽 포인터가 null이면 이 포인터를 X 노드의 후행 노드를 가리키도록 하고, 왼쪽 포인터가 null이면 X 노드의 선행 노드를 가리키게 함

▪️ 스레드를 이용한 후위 순회

• 자식 노드를 가리키는 것과 스레드가 불일치할 경우 프로그램적인 처리가 추가 필요