dev-waterparsley

• 이전 행 데이터 리턴
LAG(컬럼명 [,offset] [,default]) OVER([PARTITION BY 그룹컬럼명] ORDER BY 정렬컬럼명)

• 다음 행 데이터 리턴
LEAD(컬럼명 [,offset] [,default]) OVER([PARTITION BY 그룹컬럼명] ORDER BY 정렬컬럼명)

-offset: 값을 가져올 행의 위치(기본 값: 1)
-default: 값이 없을 경우 출력할 기본 값(생략 시, null)

✅ 예시

SELECT yyyy
      ,pin
      ,start_date
      ,end_date   
      ,LAG(end_date) OVER(ORDER BY yyyy, pin, start_date) AS r_end_date --(실제)이전 근무 종료일
      ,LEAD(start_date) OVER(ORDER BY yyyy, pin, start_date) AS r_next_start_date --(실제)다음 근무 시작일
FROM employees 
AND yyyy = ‘2022’

✅ 응용

--연속적으로 근무한 직원들의 pin 번호 조회
SELECT z.pin
FROM (
       SELECT y.*
             ,DENSE_RANK() OVER(ORDER BY y.pin) AS grp
       FROM (
              SELECT x.yyyy
                    ,x.pin
                    ,x.start_date
                    ,x.end_date
                    ,(CASE WHEN x.c_past_end_date = LAG(x.end_date) OVER(ORDER BY x.yyyy, x.pin, x.start_date) 
                           THEN 1 ELSE 0 END) AS chk1 --(예측)이전 근무 종료일과 (실제)이전 근무 종료일의 값 비교
                    ,(CASE WHEN x.c_next_start_date = LEAD(x.start_date) OVER(ORDER BY x.yyyy, x.pin, x.start_date)
                           THEN 1 ELSE 0 END) AS chk2 --(예측)다음 근무일과 (실제)다음 근무 시작일 값 비교
              FROM (
                     SELECT yyyy
                           ,pin
                           ,start_date --근무 시작일
                           ,end_date --근무 종료일
                           ,to_char(to_date(start_date, ‘YYYYMMDD’) - 1) As c_past_end_date --(예측)이전 근무 종료일
                           ,to_char(to_date(end_date, ‘YYYYMMDD’) + 1) AS c_next_start_date --(예측)다음 근무 시작일
                     FROM employees
                     AND yyyy = ‘2022’
                   ) x
            ) y
       WHERE ((y.chk1 = 1 AND y.chk = 0) 
               OR (y.chk1 = 1 AND y.chk = 1)
               OR (y.chk1 = 0 AND y.chk = 1))
     ) z
GROUP BY z.yyyy, z.pin, z.grp

입력 모드 타입을 설정하지 않고 (edittype=‘none’)
그리드 내 특정 컬럼의 양수 값을 음수 값으로 보여주고 싶을 때
(데이터 조회 쿼리가 공통 쿼리여서 쿼리문을 바꿀 수는 없는 상황) expr을 이용해 바인딩한 컬럼에 - 붙여주면 됨

예)
expr:-컬럼명

💡라디오버튼 전체를 활성화 또는 비활성화하는 기능은 공식적인 문법으로 제공되지만 특정 항목별에 대한 기능은 제공하고 있지 않음. 그래서 라디오버튼 컴포넌트 내부를 확인해보니 항목들을 items에 배열 형태로 저장하고 있음. 이걸 가지고 항목별 조작은 가능하지만 공식적인 방법은 아님

//활성화
this.컴포넌트ID._items[index].set_enable(true);

//비활성화
this.컴포넌트ID._items[index].set_enable(false);

✅ 그리드(Grid)

• 데이터셋의 내용을 격자 모양으로 표현하는 컴포넌트
• 항상 데이터셋과 바인딩해서 사용하며 한쪽의 데이터가 변경되면 다른 쪽도 변경됨

✅ 셀(Cell)

• 그리드가 출력되는 최소 단위

🔸setCellProperty(sBand, nColIdx, sPropID, sValue)

• 해당 셀 속성을 설정하는 메소드

//head 영역 텍스트를 hello로 변경
this.컴포넌트ID.setCellProperty("head", 2, "text", "hello");		

//body 영역 데이터 표기 타입을 number로 변경
this.컴포넌트ID.setCellProperty("body", 2, "displaytype", "number"); 

//summary 영역 expr(계산식) 변경
this.컴포넌트ID.setCellProperty("summary", 2, "expr", "Math.round(dataset.getSum(\"컬럼명\"))");

🔸setFormatColProperty(nColIdx, sPropID, nColSize)

• 해당 컬럼 영역의 속성을 설정하는 메소드

//그리드의 특정 셀 숨기기
this.컴포넌트ID.setFormatProperty(2, "size", 0);

//그리드의 특정 셀 나타내기
this.컴포넌트ID.setFormatProperty(2, "size", 150);

✅ 넥사크로 플랫폼

1. 화면을 정의하는 부분(XML 기반)
2. 비즈니스 로직을 처리하는 스크립트
 
../ _resource_/
애플리케이션에서 고정으로 사용하는 Resource 폴더로 Theme, UserFont 등의 정보를 관리합니다.

appvariables.xml
Project Explorer의 AppVariables 항목에서 설정한 파일이며, 전역변수와 전역Dataset을 정의한 파일입니다.

environment.xml
Project Explorer의 Environment 항목에서 설정한 파일입니다.

https://docs.tobesoft.com/edu_nexacro17_design_kr/68aacc4ef7ae9bcb#6d44c03c3797ae33

 

넥사크로 플랫폼에서 애플리케이션 개발 시 기본적으로 생성되는 파일

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)이 여러모로 더 좋음