SLENDER ANKLES's 개발블로그

데스트탑 애플리케이션 vs 웹 애플리케이션?

데스크톱 어플리케이션

사용자가 직접 아이콘을 더블 클릭하거나 명령 창(터미널)을 통해 실행시키는 프로그램

웹 애플리케이션

사용자가 웹 서버를 통해 간접적으로 실행시키는 프로그램

CGI(Common Gateway Interface)란 무엇인지?

웹 브라우저에서 웹 서버로 정보를 요청하면 웹 서버는 프로그램에 작업을 요청하여

CGI규칙을 통해 결과를 받아서 클라이언트로 응답한다.

이 때 웹 서버와 프로그램 사이의 데이터를 주고받는 규칙을 CGI(Common Gateway Interface)라고 한다.

CGI 프로그램에서 컴파일 방식 vs 인터프리터 방식

CGI프로그램은 C, C++, Java와 같은 컴파일 방식의 언어로 작성 할 수도 있고

Perl, PHP, Python과 같이 스크립트 언어로도 작성 할 수 있다.

컴파일 방식은 

기계어로 번역된 코드를 바로 실행하기 때문에 실행 속도가 빠르지만,

변경 사항이 발생할 때마다 다시 컴파일하고 재배포해야하는 문제가 있다.

스크립트 방식은

실행할 때마다 소스 코드의 문법을 검증하고 해석해야 하기 때문에 속도가 느리지만,

변경 사항이 발생하면 단지 소스 코드를 수정하고 저장만 하면 되기 때문에 편리하다.

서블릿(Servlet)이란 무엇인가?

자바로 만든 CGI프로그램을 서블릿(서버 + 애플릿의 합성어)이라고 함

자바 서블릿이 다른 CGI프로그램과 다른 것은 웹 서버와 직접 데이터를 주고 받지 않으며,전문 프로그램에 의해 관리된다는 것

서블릿 컨테이너?

서블릿의 생성과 실행, 소멸 등 생명주기를 관리하는 프로그램, "서블릿 컨테이너"

서블릿 컨테이너가 서블릿을 대신하여 CGI 규칙에 따라 웹서버와 데이터를 주고 받음.

개발자들은 CGI 규칙을 알 필요가 없지만 서블릿 규칙에 대해서 알아야 함.

WAS(Web Application Server)란 무엇인지?

서블릿과 서블릿 컨테이너와 같은 웹 기술 기반으로 동작하는 애플리케이션 서버를 

"WAS(Web Application Server)"라고 함

서블릿을 시작하기 전에 웹 어플리케이션 및 기초적 용어와 과정에 대해서 공부를 시작해보고자 한다.

웹 애플리케이션을 개발하다보면 다음과 같은 용어에 대해서 정리할 필요가 있게된다.

SOAP(Simple Object Access Protocol)과 RESTful(REpresentational State Transfer)에 대해서 아는가?

 SOAP  

일반적으로 널리 알려진 HTTP, HTTPS, SMTP 등을 통해 XML 기반의 메시지를 컴퓨터 네트워크 상에서 교환하는 프로토콜. SOAP은 프로그래밍 언어마다 지원해주는 것이 필요하다.

 REST  

기본 HTTP 프로토콜의 메소드 GET/PUT/POST/DELETE를 이용하여 서비스 제공자에게 서비스를 요청하여 JSON, XML, RSS 등으로 리소스를 반환하는 것을 말한다. 프로그래밍 언어에 독립적이다.

프록시서버(Proxy Server)란 무엇인가?

클라이언트와 서버 사이에서 통신을 중계해 주는 컴퓨터나 프로그램을 말한다.

 프록시 서버는 두는 이유 

1) 빠른 전송을 위하여 서버의 응답 결과를 캐시해 두는 것

예를 들어 클라이언트의 요청이 이전에 프록시 서버에 캐시되어있다면 서버에 요청을 생략하고 바로 응답해 줄 수 있게 된다.

2) 보안상의 이유로 프록시 서버를 둔다.

외부로 전달되는 데이터를 검사하여 특정 단어가 포함된 자료의 송, 수신을 차단하거나 보안 팀에 경고메시지를 전달 할 수 있게 된다.

웹 환경에서의 Server-Client 구조의 장점

이전의 서버 - 클라이언트 구조는 비즈니스 로직이 클라이언트에 있었기 때문에 

변경이 필요하게 되면 클라이언트의 프로그램을 다시 깔아야 한다. 

하지만 웹 환경에서의 서버 클라이언트의 구조에서는 클라이언트는 UI의 역할만 하게 된다. 

변경이 필요하더라도 서버에서만 바꾸어주면 된다. 

배치하는 즉시, 사용자는 재설치 없이 추가된 기능이나 변경된 기능을 이용할 수 있게 된다. 

단점 : 다만 웹을 사용 할 때마다 UI를 계속 다운받는 형식이기 때문에 네트워크 오버헤드가 큰 편이다.

전통적인 서버-클라이언트 구조의 단점을 내세우며, 

웹 환경의 서버 클라이언트 구조에 대해서 설명해본다면...

웹 환경에서의 서버 클라이언트의 구조(CS) 역시 단점 존재. 매번 클릭할때마다 UI를 다운 받아야한다. 

하지만, 이러한 단점을 보완하고자 AJAX(Asynchronous Javascript And Xml) 등장

AJAX는 페이지를 전체를 갱신하는 것이 아니라 부분, 부분 갱신할 수 있게 해준다.

HTTP 프로토콜 이란?

HTTP 프로토콜은 웹 브라우저와 웹 서버 사이의 데이터 통신 규칙을 말한다.

즉 HTTP 통신 규약에 맞추어서 요청한다면

HTML파일을 요청하면 HTML파일을 보내주고, 이미지 파일을 요청하면 이미지 파일을 보내준다는 것이다.

http요청 응답에 대한 내부적으로 어떻게 동작하고 있는가?

요청과정(Request)

요청라인, 요청헤더, 공백라인과 요청 데이터로 구성

요청 라인(Request-Line)

요청헤더

  * 요청이나 응답 모두에 적용 할 수 있는 "일반헤더(General Header)"

  * 요청 또는 응답 둘 중에 하나에만 적용 할 수 있는 "요청 헤더 또는 응답 헤더(Request Header / Response Header)"

  * 보내거나 받는 본문 데이터를 설명하는 "엔티티 헤더(Entity-Header)"

HTTP헤더들

GET요청 

공백 라인으로 끝납니다. 서버에 보낼 데이터가 있다면 URL주소에 붙여 보냅니다.

POST요청

그에 비해 로그인이나 게시글을 등록하는 경우 POST를 사용하는데, POST요청은 공백 라인 다음에 메시지 본문이 들어갑니다.

응답과정(Response)

GET과 POST 요청 방식의 차이는 무엇인가?

URL에 데이터가 있는 것은 GET방식, URL에 데이터가 없고 메시지 본문에 있는 것은 POST방식

GET요청의 특징

- URL에 데이터를 포함 - 데이터 조회에 적합

- 바이너리 및 대용량 데이터 전송 불가

- 요청라인과 헤드 필드의 최대 크기

  * HTTP 사양에는 제한사항 없음

  * 대용량 URL로 인한 문제 발생 => 웹 서버에 따라 최대 크기 제한

  * 마이크로소프트 IIS 6.0 16KB

  * APACHE 웹 서버 8KB

GET요청의 데이터 전달 형식은 어떻게 되는가?

서비스 주소 ? V1 = 23 & V2 = 15

서비스주소와 데이터를 ? 라는 문자를 이용해서 구분한다.

예) http://www.naver.com?v1=23&v2=15

GET 요청의 장점은 무엇인가?

URL에 데이터가 섞여 있기 때문에 결과 화면을 다른 사람들과 공유 할 수 있다. 

링크를 클릭하게 되면 바로 결과화면을 볼 수 있다.

GET 요청의 문제점은 무엇인가?

(1) 보안에 좋지 않다.

주소에 데이터가 섞여있기 때문에 사용자의 로그인이나 중요 정보 요청에서 데이터가 밖으로 보인다.

그렇기 때문에 보안상의 이슈가 발생 할 수 있다. 

(2) 바이너리 데이터를 전송 할 수 없다.

파일의 데이터는 URL에 붙여서 전송 할 수 없다.

BASE 64라는 인코딩 방식을 통해 바이너리 데이터를 문자화해서 보낼 수도 있지만, URI나 헤더 정보가 너무 크면

웹 서버에서 처리 할 수 없다.

이런 것은 POST를 통해 전송해야 한다.

POST요청의 특징

- URL에 데이터가 포함되지 않음 => 외부 노출 방지

- 메시지본문에 데이터 포함 => 실행 결과 공유 불가

- 바이너리 및 대용량 데이터 전송 가능

POST요청의 요청은 어떻게 이루어지는가?

요청라인과 요청헤더 다음에 공백라인이 있고 그 다음에 메시지 본문(Message Body)라 불리는 부분에 데이터가 위치해서 전송된다.

POST요청의 장점은 무엇인가?

입력값을 URL에 노출 시키지 않는다. 당연히 보안상으로 GET에 비해 좋다.

폼 태그를 통해 보내진 POST데이터는 Content-Length 와 Content-Type 등으로 구분한다.

Content-Type은 기본적으로 application/x-www-form-urlencoded형식으로 인코딩되어 보내진다.

POST요청의 문제점은 무엇인가?

(1) 요청 결과를  공유 할 수 없다.

즐겨찾기, 메일 등으로 그 결과값을 공유 할 수 없다.

POST요청은 데이터를 메시지 본문에 붙여서 전송하기 때문이다.

(2) GET방식과 마찬가지로 POST도 데이터를 전달 할 때 '이름=값&이름=값'형태로 보내진다.

결국 문자데이터를 보낼 때는 상관없지만 바이너리 데이터 등을 전송할 때는 이러한 '='이나 '&'값이 섞여 있을 수 있기 때문에 문제가 발생할 수 있다.

그래서 바이너리 데이터 등을 보낼 때는 멀티 파트 인코딩 방식을 통해 보내야 한다.

멀티 파트 인코딩 방식은 어떨때 사용하며 그렇게 사용하는 이유는 무엇인가?

POST형식 역시 데시지 본문에 '이름=값&이름=값'형태로 보내지기 때문에 

바이너리 데이터에 혹시 = 이나 &가 섞여있으면 문제가 발생 할 수 있다.

그래서 멀티 파트 인코딩 방식을 사용하여 요청정보와 데이터를 확실히 구분 할 수 있게 한다.

예를들어 <form>태그의 enctype 속성을 'multipart/form-data'로 지정해서 file 전송을 할 수 있게 합니다.

싱글톤 패턴이란?

인스턴스를 하나만 만들어 사용하기 위한 패턴이다.

이유?

커넥션 풀, 스레드 풀, 디바이스 설정 객체 등과 같은 경우에 인스턴스를 여러 개 만들게 되면 불필요한 자원을 사용하게 되고,

또 프로그램이 예상치 못한 결과를 낼 수 있다. 

싱글톤 패턴은 의미상 두 개의 객체(인스턴스)를 가질 수 없다. 

이를 구현하려면, 객체 생성을 위한 new 제약을 걸어야 하고, 만들어진 단일 객체를 반환 할 수 있는 메서드가 필요하다.

따라서 필요한 요소를 생각하면 다음의 세 가지가 있다.

- new를 실행 할 수 없도록 생성자에 private 접근 제어자를 지정한다.

- 유일한 단일 객체를 반환할 수 있는 정적 메서드가 필요하다.

- 유일한 단일 객체를 참조할 정적 참조 변수가 필요하다.

클라이언트 코드

해시라는 것은 DB를 공부할 때 많이 들었다. 테이블 구조에서 성능을 끌어올 때 해시구조로 변형시키는 튜닝방법이 있었다. 

또 암호화 할 때 해시라는 것을 많이 들었는데, 정확히 무엇이다 규정을 내릴 수 없는 상태였다. 해시라는 것을 정리해보겠다.

해시(Hash)

-주어진 키를 이용해서 실제 레코드의 주소를 직접적으로 계산해내는 것을 해시라고 한다. 

-임의의 데이터를 고정 길이의 데이터로 변화한 값을 해시값, 이 과정을 해시라고 한다. 

(쫌 어렵다)

해시에 대한 정의도 중요하지만 어디에 해시가 사용하는지를 알아야 한다.

해시의 궁극적인 목표

데이터 개수 N개와 무관하게 단번에 찾겠다는 것, 탐색효율이 logN도 아니라 O(1)을 지향한다!

어떻게?

키를 입력하면 해시함수를 통해서 해시테이블의 인덱스로 바로 접근한다!

해시함수(Hash Function)란?

해시함수(Hash Function)란 탐색키를 입력으로 받아 해시주소(Hash Address)를 생성하고 

이 해시 주소가 배열로 구현된 해시 테이블(Hash Table)의 인덱스가 된다.

ex) 영어 사전에서는 단어(탐색키)를 이용하여 해싱 함수를 통과하면 적절한 정수 i가 도출되는데 

이를 통해 ht[i]에 접근하면 단어에 대한 내용을 볼 수 있게 되는 것이다.

해시테이블(Hash Table)의 구조?

-해시테이블은 M개의 버켓(bucket)과 S개의 슬롯(Slot)으로 구성된다. 

-하나의 버켓은 여러 개의 슬롯을 가질 수 있다.

해시(Hash)의 방법?

1) 제산법

나머지 연산자(%)를 사용하여 테이블 주소를 계산하는 방법

레코드 키 값을 수치 자료로 간주하여 어떤 양의 정수(대개 해시 테이블의 크기)로 나눈 나머지를 홈 주소로 결정하는 간단한 방법

ex) 버킷 주소 = 키 값 % 해쉬 테이블의 크기

12 = 512 % 100

2) 제곱법

- 제곱법은 레코드 키 값을 제곱한 후에 결과 값의 중간 부분에 있는 몇 비트를 선택하여 해시 테이블의 홈 주소로 사용

- 제곱된 결과의 중간 비트는 대개 레코드의 모든 문자에 의존하므로, 레코드를 구성하는 몇 개의 문자가 같은 지라도 서로 다른 레코드 키는 다른 홈 주소를 갖게 될 확률이 높다

- 홈 주소를 얻기 위해 사용되는 비트 수는 테이블의 크기에 따라 달라지는데, 중간 부분의 자릿수를 n이라 하면 각 레코드 값들이 가지는 범위인 해시 테이블의 크기는 2n 이 된다.

- 키 값 제곱 => 해시 테이블 크기에 따라 주소 값 산출

ex) 레코드 키 값이 K = 512이고, 해시테이블의 크기가 100일 때 제곱법에 의한 레코드 주소는?

512제곱 = 262144

====> 중간 2자리 "21"최종 주소값이 됨

3) 숫자 분석법

- 레코드 키를 구성하는 수들이 모든 키들 내에서 각 자리별로 어떤 분포인지를 조사하여 비교적 고른 분포를 나타내는 자릿수를 필요한 만큼 선택하여, 레코드의 홈 주소로 사용하는 방법

ex) 해시 테이블의 크기 = 1000, 홈 주소 : 0 ~ 999까지(3자리 필요) 레코드 키 값이 다음의 (a)와 같을 때 숫자 분석법을 이용하여 각 키들에 대한 홈 주소를 결정하시오.

012 - 452 - 0236   =>     426

012 - 153 - 0530   =>     150

015 - 342 - 0935   =>     395

012 - 752 - 1032   =>     702

012 - 852 - 0470   =>     840

012 - 543 - 0231   =>     512

     (레코드 키값)         (각 키의 홈 주소)

(1) (a)에서 왼쪽 3자리는 거의 같으므로 제거

(2) 왼쪽 5열, 6열, 7열, 9열 역시 동일 숫자가 많이 분포하였으므로 무시

(3) 비교적 고른 숫자 분포를 가진 4열, 8열, 10열을 선택하여 주소로  사용

4) 폴딩법

- 폴딩법은 레코드의 키를 마지막 부분을 제외한 모든 부분의 길이가 동일하게 여러 부분으로 나누고, 이들 부분을 모두 더 하거나 배타적 논리합(XOR)을 취하여, 해시 테이블의 홈 주소로 이용하는 방법으로 두 가지 방법이 사용 된다.

(1) 이동 폴딩(shift Folding)

(2) 경계 폴딩(Boundary Folding)

이동폴딩 => 

P1 + P2 + P3 + P4 + P5 

= 301 + 230 + 123 + 213 + 30 = 897

897 = 홈주소

경계폴딩 => 

P1 + P2(역) + P3 + P4(역) + P5

= 301 + 032 + 123 + 312 + 30 = 798

798 = 홈주소

5) 기수변환법

- 기수 변환법은 어떤 진법으로 표현된 주어진 레코드 키를 다른 진법으로 간주하고 키를 변환하여 홈 주소를 얻는 방법으로, 어떤 키 값이 16진법으로 표현되어 있다면 이를 10진법으로 표현된 것으로 간주하고 키 값을 변환하여 해당 레코드의 홈 주소를 구한다.

- 해시 테이블의 크기가 10의 멱승으로 표현되어 변환된 해당 레코드의 주소 값이 테이블의 크기를 초과할 때는 주소 값의 최하위 자리부터 해시 테이블의 크기가 허용하는 멱승수만큼 취하여 해당 레코드의 홈 주소로 사용한다.

ex) 해시 테이블의 크기 = 10000()

- 십진수로 입력된 키 값(B2538)10을 16진수로 간주하여 그 값을 다시 10진수로 계산하는 기수 변환법을 이용하여 홈 주소를 구하시오. 

(풀이) (1 * 165) + (3 * 164) + (2 * 163) + (5 * 163) + (4 * 161) + (8 * 160)

= 1048576 + 196608 + 8192 + 1280 + 64 + 8

= (1254728)10

홈 주소 = 4728

- 레코드의 주소값 (1254728)10에서 해시 테이블이 허용하는 하위 4자리를 선택한다.

6) 무작위방법

- 난수 발생 프로그램을 이용하여 난수(random number)를 발생시켜 각 레코드 키의 홈 주소를 결정하는 방법으로, 보통 난수는 1보다 작은 양의 실수를 산출하므로,

- 해시 테이블의 크기인 n을 산출된 난수에 곱하여 0~(n-1)까지의 범위 값으로 변환하여 사용하며, 만일 충돌이 발생하게 되면 그 다음 난수를 레코드의 홈 주소로 사용한다.

해시충돌(Hash Collision)이란?

- 서로 다른 두 개의 탐색키와 k1과 k2에 대하여

- h(k1) = h(k2)인 경우에는 충돌이 일어난다.

- 이러한 충돌이 버켓이 할당된 슬롯 수보다 많이 발생하게 되면 

버켓에 더 이상 항목을 저장할 수 없게 되는 오버플로우(Overflow)가 발생한다.

해시충돌을 해결하는 방법?

- 선형 검색법

- 2차 검색법

- 무작위 검색법

- 체인 이용법

* 해시 함수에 의해 같은 기억공간에 할당되어 충돌이 발생한 레코드들을 연결 리스트(Linked List)로 연결하는 방법으로

해시 테이블 자체는 포인터의 배열로 만들고, 같은 버켓에 할당되는 레코드들을 체인으로 만들어 연결한다.

=> 해시 연쇄법은 연결 리스트를 사용하므로 해시 테이블에서의 삽입이나 삭제 연산이 용이하며, 충돌의 횟수를 감소시키지는 못하지만 다른 충돌 해결 방법에 의해 해시 테이블을 검색 할 때 발생하는 소요시간을 감소 시킬 수 있다.

* 장점 

=> 충돌이 발생한 명칭들만 연결 리스트에서 검색해 주면 되므로 속도가 빠르다.

=> 삽입 가능한 명칭의 수가 해시 테이블 크기에 영향을 받지 않는다.

* 단점

=> 구조가 복잡하고 기억 장소 소모량이 많다.

검색트리가 디스크에 있는 상태로 사용되면 외부검색트리라고 함

분기(자식노드)의 수가 2개를 넘으면 다진검색트리라고 함

B-트리는 디스크 환경에서 사용하기에 적합한 외부 다진검색 트리이다.

이진트리와 B-Tree는 차이는?

이진트리와 B-Tree는 비슷하다. 

하지만 이진트리는 편향된 트리 구조가 발생할 수 있는데 반해 

1) B-Tree는 트리의 균형을 유지해주는 성질을 가지고 있어 응답속도를 보장해준다.

2) 또한 하나의 노드에 여러개의 값을 가질 수 있는 성질을 가지고 있다. 이러한 성질은 하나의 노드에 여러개의 값을 가질 수 있으므로 당연히 트리의 높이도 낮아지므로 검색의 성능이 좋아질 수 있다.

하나의 노드에 많은 데이터를 가질 수 있는 점 

=> 대량의 데이터를 처리해야 하는 검색 구조에서 큰 장점

=> 대량의 데이터는 메모리보다는 하드디스크 혹은 SSD에 저장

(이러한 보조 기억 장치는 블럭 단위로 입출력을 하기 때문에 Disk I/O단위로 노드의 크기를 정할 수 있는 B-Tree가 유리)

(예를 들어 1024바이트 블럭이라면, 2바이트를 읽으나 1024바이트를 읽으나 입출력에 대한 비용은 동일하다)

이러한 장점 때문에 B트리는 데이터베이스에 이용되는 자료구조이다. 

이러한 B-Tree에 대해서 알아보자!

Balanced Tree(B-Tree)

* 이진 검색 트리의 문제점은

  - 좌우 균형이 맞지 않으면 비효율적이다. 보통 O(logN)이지만 O(N)까지 갈 수 있다.

* Balanced Tree

  - 삽입과 삭제시 필요하면 스스로 균형을 유지함

  - AVL Tree, 2-3(-4) Tree, Red-Black Tree, B-Tree....

  - 항상 O(logN)의 검색성능

* B-Tree란?

  - 하나의 노드에 여러자료가 배치되는 자료구조

  - 한 노드에 M개의 자료가 배치되면 M차 B-Tree

    * M이 짝수냐 홀수냐에 따라 알고리즘이 다르다.

* B-Tree의 규칙

  규칙1)

  - 노드의 자료수가 N이라면, 자식의 수는 N+1 이어야 한다.

  - 각 노드의 자료는 정렬된 상태여야 한다. 

  - 노드이 자료 Dk의 왼쪽 서브트리는 Dk보다 작은 값들이고, Dk의 오른쪽 서브리는 Dk보다 큰 값들이어야 한다. 

  규칙2)

  - Root노드는 적어도 2개이상의 자식을 가져야 한다. 

  - Root노드를 제외한 모든 노드는 적어도 M/2개의 자료를 가지고 있어야 한다. 

  - 외부노드로 가는 경로의 길이는 모두 같다. (외부노드는 모두 같은 레벨에 있다.)

  - 입력자료는 중복될 수 없다.

* B-Tree의 검색

노드내에서는 순차검색

전체적으로 트리검색

* B-Tree의 삽입 알고리즘1

* B-Tree의 삽입 알고리즘

  - 자료는 항상 Leaf노드에 추가된다. 

    * Leaf노드의 선택은 삽입될 키의 하향 탐색에 의해 결정

  - 추가될 Leaf노드에 여유가 있다면 그냥 삽입

  - 추가될 Leaf노드에 여유가 없다면 "분할"하기

  - 분할을 위해서는 키 하나를 부모로 올려야 함

    * 부모가 꽉 차 있다면 문제!

  - 삽입을 위한 하향탐색을 하면서 꽉찬 노드는 분할해 주어야 함

* B-Tree의 삭제 알고리즘

  - 삭제하고자 하는 자료가 있는 노드가

     * 삭제 후 자료수가 M/2 이상이 되도록 보장해야 함!

  - 형제에게서 빌리기 vs 형제와 결합하기

     * 빌리기 : 형제가 M/2보다 많은 자료를 가지고 있다면

     * 결합하기 : 형제에게서 빌릴 수 없다면

  - 삭제키가 있는 노드가 내부노드인 경우

     * 대체키를 찾아 대체해야 한다. (Right Subtree중 가장 큰값으로)(이진트리와 동일)

  - 삭제를 위한 하향탐색을 하면서 자료수가 M/2이하인 노드는 형제에게 빌리든지 결합해야 함

분석과 특성

* B-Tree는 외부검색에 적합함

  - 하나의 노드크기를 Disk I/O단위의 크기로!

  - 순차검색과 트리검색의 잇점을 취함

    * B-트리는 Balanced Tree로 최악의 경우가 없음

    * 퀵정렬에서 소구간에 대한 삽입정렬이 성능이 좋았다.

    * 노드내에서 순차검색 대신 이분검색은?

Index(색인)이 가져야 할 특성

1. 일반적으로 보조 기억 장치에서의 탐색은 시간적인 부하가 많이 걸리기 때문에 탐색을 쉽게 하기 위해

file과는 별도로 index를 만들어 사용한다.

2. Index가 커질 경우 index 역시 보조 기억 장치에 저장하는데 보조 기억 장치는 상대적으로 느리므로 

보조 기억 장치의 access 횟수를 최대한 억제시켜야 한다. 

3. Index에의 access회수를 줄이기 위해서는 최대 탐색 길이 즉, 트리의 높이를 줄여야 한다. 

4. 높이를 낮추기 위해서는 하나의 노드에서 나가는 branch의 개수를 증가한다. 

=> B-Tree를 데이터베이스의 인덱스 자료구조로 사용하는 이유!

스택이나 큐는 시간에 우선순위를 두어, 후입선출(Last-In-First-Out), 선입선출(First-In-First-Out)의 방법을 사용한다.

하지만, 예를 들어, 응급실에 실려오는 환자들을 생각해보자. 단순히 머리가 아픈 사람들보다는 손가락이 절단된 환자가 더 우선적으로 치료받아야 될 사람이다. 이러한 우선순위를 두는 자료구조를 우선순위 큐(Priority Queue)라고 한다. 

우선순위를 매기는 기준은 당연히 여러가지가 있지만, 

학습의 의미로써 우선순위 큐를 표현 할 때는 보통 숫자 혹은 알파벳으로 표현한다. 

우선순위 큐(Priority Queue)를 배열로써 표현하거나, 연결 리스트로도 표현 할 수 있다. 

둘 다 구현 효율은 O(N)이다. 

또한, 이진탐색트리(Binary Search Tree, BST)로 구현할 때는 O(NlogN)이지만 

이 것은 균형잡혀있는 이진탐색트리라는 전제조건이 있을 때이다. 

하지만, 이제 자세히 알아 볼 우선순위 큐(Priority Queue)의 자료구조는 

힙(Heap)이다. 

힙은 완전이진트리로 표현되어야 하는데, 그래서 반드시 트리가 균형잡혀 있을 수 밖에 없다는 특징 때문에

시간효율을 O(NlogN)을 보장한다!!

힙의 정의

1) 항상 완전 이진트리의 모습을 지닌다. 

2) A. 빈 트리거나,

    B. 루트의 키가 왼쪽 자식, 오른쪽 자식의 키보다 크거나 같다. 

        왼쪽 자식과 오른쪽 자식 자시에는 어느 쪽 키가 크든지 상관없다.

        단, 왼쪽 자식, 오른쪽 자식을 루트로 하는 하위트리는 힙이어야 한다.

다음은 맥스 힙(Max Heap)을 나타낸 것이다. 

200은 왼쪽 자식인 100보다 크고, 오른쪽 자식인 80보다 크다. 

200의 왼쪽 서브 트리 역시 힙의 형태를 띈다. 200의 오른쪽 서브 트리 역시 힙의 형태를 띈다. 

- 대상 노드가 자식보다 크기만 하면 된다. 

- 약한 정렬 형태를 가진 것을 알 수 있다.

- 완전 이진 트리 형태를 반드시 띄어야 하므로 배열로 표현하는 것이 유리하다.

우선순위의 기준?

맥스 힙(Max Heap), 민 힙(Min Heap)으로 나눌 수 있다. 

루트노드가 자식노드들보다 큰 형태로 힙이 만들어지는 것을 맥스 힙(Max Heap)이라고 한다.

루트노드가 자식노드들보다 작은 형태로 힙이 만들어지는 것을 민 힙(Min Heap)이라고 한다.

힙의 특징?

힙의 가장 큰 특징은 완전이진트리로 표현해야 된다는 것이다. 그러므로 배열로써 자료구조를 표현한다.

위와 같은 힙이라는 트리를 배열로 표현하기에 

1) 인덱스 K에 있는 모든 왼쪽 자식은 (2K+1), 오른쪽 자식은 (2K+2)에 있다.

2) 인덱스 K에 있는 모든 부모 노드는 (K-1) / 2 에 있다.

힙의 삭제?

힙의 삭제는 우선 순위가 가장 높은 루트 노드(Root Node)가 삭제되어야 한다. 

배열로 구현하므로 24라는 노드를 할당해제 하는 식으로 삭제하는 것이 아니라 그 값을 지우고 

힙의 마지막 값인 7로 대체한다.

7을 루트노드로 옮기면 자식노드보다 커야하는 힙의 성질이 깨지게 된다. 

따라서 왼쪽 자식과

오른쪽 자식을 모두 비교해 가장 큰 것과 루트를 스와핑(Swap)해야한다.

7과 19, 7과 12를 비교  => 19가 가장 크므로 19와 7을 스왑

7과 17, 7과 10을 비교  => 17이 가장 크므로 17과 7을 스왑

7과 9를 비교 => 9가 더 크므로 9와 7을 스왑

이 처럼 힙 모습을 되찾으려면 루트로부터 시작해서 제자리 찾기까지 굴러 떨어져야 한다. => Down Heap

이 과정을 거치면 힙의 형태가 완성된다. => Heap Rebuilding

힙의 삭제 과정은 O(logN)이다. 배열의 마지막 레코드를 복사하는 것이 O(1)이다. 

최악의 경우 리프노드까지 굴러 떨어져야 한다. 이 것은 logN이다. 그런데 비교때마다 왼쪽 오른쪽을 다 비교해야하므로

=> 2logN 이다. 

힙이 이진탐색트리에 비해 유리한 이유는?

트리의 높이 때문이다. 

이진탐색트리는 균형트리를 유지한다는 보장이 없지만, 힙은 반드시 균형트리를 이뤄야한다.

완전 이진트리이기 때문이다.

힙의 삽입?

힙의 삽입은 "새로 들어 온 직원을 말단의 자리에 앉히고 어디까지 올라가나 해봐라" 이렇게 말할 수 있다. 

삽입 할 값을 마지막 노드에 삽입 한 후에 아래에서부터 부모와 비교하여 제 자리를 찾아간다.

22를 마지막에 삽입한다.

부모노드(10)과 비교한다. => 22가 더 크므로 스왑한다.

부모노드(19)와 비교한다. => 22가 더 크므로 스왑한다.

힙이 리빌딩됐다!

힙의 삽입 작업은 O(logN)이다. 

최악의 경우 루트 노드까지 타고 올라가야 하므로 비교 횟수는 logN이다.

(삭제 노드는 자식 2개와 비교해야 되는데, 삽입 작업은 부모노드와 한 번만 비교하면 된다)

역시 이진탐색에 비한 장점은 균형트리를 보장하므로 logN을 보장한다는 것이다.

힙 정렬?

힙정렬은 힙의 형태를 이용해서 정렬을 하는 것이다. 

최대 힙의 부모를 삭제하고 가져 온다. => 힙 리빌딩한다.

....(반복)

그러면 내림차순으로 값이 정렬된다.

반대로 

최소 힙으로 하면 오름차순으로 값이 정렬된다. 

힙 구성(Heap Building)?

힙 정렬을 위해서는 다음과 같은 두 가지 방법이 있다.

(1) 하향식 힙 구성(Top-Down)

반복적으로 힙에 삽입 작업을 가하는 것이다.

하향식 힙 구성의 시간 효율은

삽입 될 때마다 logN의 시간이 걸린다. 

N개가 삽입 되므로 NlogN이 된다. 

또한 정렬을 위한 힙의 삭제 단계에서 NlogN이 걸린다.

그러므로 O(NlogN) + O(NlogN) = O(NlogN) 이 된다. 

(2) 상향식 힙 구성(Bottom-Up)

들어오는 키 값 순서대로 일단 트리를 구성한 후에 힙 구조가 되도록 재조정하는 방식이다. 

그러한 후에 가장 아래서부터 오른쪽에서 왼쪽 순으로 힙의 구조인지 검사한다. 

검사 할 때는 해당 노드와 해당 노드의 아래 쪽만 검사한다. 

** 하향식과 상향식의 비교

- 둘 다 힙의 형태를 띄지만 그 트리가 완전히 똑같지는 않다.

- 완전 이진트리의 특성상 리프노드가 전체 노드의 반 또는 반이상을 차지하게 된다. (균형되게 유지되므로)

(1) 하향식 힙 구성 방법은

노드를 아래에 삽입 한 후에 위로 올라가면서 비교하여 리빌딩한다.

그러므로 가장 많은 노드를 차지하는 리프노드들이 logN의 시간을 타고 위로 올라가게 된다.

(2) 상향식 힙 구성 방법은 

위에서 아래로 내리는 방법으로 리빌딩한다. 

가장 많은 수를 차지하는 리프노드는 그 아래 노드가 없으므로 아예 비교조차 하지 않는다. 

그 바로 위 레벨의 노드 역시 바로 아래와만 비교한다. 

결국 logN의 장거리 여행을 하는 것은 루트노드와 같이 최상단에 있는 것만 한다.

하향식 힙 구성 방법이 O(NlogN)인데 반해

상향식 힙 구성 방법은 O(N)에 가까운 효율을 보인다. 

트리(Tree)의 정의

: 트리는 계층적인 형태를 띄는 구조를 표현 할 때 쓰이는 자료구조이다.

트리의 용어

부모노드(Parent Node): 계층적구조에서 어느 한 노드의 바로 위의 노드를 부모노드라고 한다. 

자매,형제노드자매,형제노드(Sibling Node): 계층적구조에서 어느 한 노드의 아래로 연결된 노드를 자매,형제노드라고 한다. 

루트노드(Root Node) : 트리의 가장 위에 있는 원조노드를 말한다.

리프노드(Leaf Node) : 자식이 없는 노드를 리프노드라고 한다. 

터미널노드(Terminal Node) : 리프노드와 같다.(끝난다는 의미이다.)

일반트리(General Tree) : 둘 이상의 자식 노드를  가질 수 있는 트리를 말한다.

이진트리(Binary Tree) : 자식이 없거나, 최대 두개인 트리를 말한다.

트리의 레벨(Level) 

: 루트노드를 레벨 0으로 하고 아래로 내려오면서 증가한다. 

트리의 높이(Height)

: 트리의 최대 레벨 = 트리의 높이

포화이진트리(Full Binary Tree)

: 1) 리프노드의 위쪽 노드는 반드시 자식 노드 두개를 거느리고 있어야 한다. 2) 모든 노드의 왼쪽 자식의 높이와 오른쪽 자식의 높이는 같아야 한다.

완전이진트리(Complete Binary Tree)

: 레벨(높이-1)까지는 모든 노드들이 자식을 두 개로 다 채워야하고, 마지막 리프노드는 왼쪽에서 오른쪽으로 채워져 있는 트리를 말한다.

트리를 배열로 구현하는 방법(간략소개)

: 완전이진트리를 배열로써  표현 할 수 있다. 

다음과 같은 규칙으로 노드에 접근 할 수 있다.

루트노드를 기준으로 

n은 부모노드의 인덱스를 말한다.

왼쪽 자식에 접근하는 법 => (2n + 1)

오른쪽 자 식에 접근하는 법 => (2n + 2)

(2 * 0 + 1) => B [1]로써 0번인덱스노드의 왼쪽 자식노드에 접근

(2 * 0 + 2) => C [2]로써 0번인덱스노드의 오른쪽 자식노드에 접근

E에 접근하기 위해서는 ? 

=> (2*2 + 1) = 5인덱스로 접근하면 된다. 

D에 접근하기 위해서는 ?

=> (2*2 + 2) = 6인덱스로 접근하면 된다.

트리를 포인터로 구현하는 방법(간략소개)

: 노드를 데이터값, 다음왼쪽노드주소값, 다음오른쪽노드주소값 으로 구성한 후에 연결하면 된다.

트리를 배열로 표현할때와 포인터로 표현할때의 장단점?

=> 리스트와 비슷하다. 

[배열로 표현]

장점 : 인덱스로 접근하므로 굉장히 빠르게 접근이 가능하다.

단점 : 사용될 메모리를 미리 선언해야한다. 10000개의 노드를 사용하겠다고 선언해놨지만 100개밖에 사용하지 않는다면 낭비가 될 수 있다.

[리스트로 표현]

장점 : 사용될 메모리를 프로그램을 실행하면서 늘릴 수 있다. 메모리를 효율적으로 사용 할 수 있다.

단점 : 주소를 타고 타고 들어가야하므로 탐색성능은 배열에 비해 느리다.

스레드트리(Thread Tree)란?

이진탐색트리(Binary Search Tree)란?

이진탐색트리의 조건

1) 노드 N에 대하여 N의 왼쪽 하위트리는 N보다 작고, N의 오른쪽 하위트리는 N보다 크다.

2) 노드 N에 대해여 N의 왼쪽 하위트리와 오른쪽 하위트리 모두 이진탐색트리이다.

다음과 같은 트리가 이진탐색트리(Binary Search Tree)이다.

이진탐색트리의 탐색, 삽입, 삭제의 방법?

[탐색방법]

* 8을 찾고 싶다?

(1) 루트노드인 7보다 찾는 노드(8)가 크다 => 오른쪽 자식 노드로 진입

(2) 현재노드인 21보다 찾는 노드(8)가 작다. => 왼쪽 노드로 진입

(3) 현재노드인 8과 찾는 노드(8)가 같다! (찾음)

[삽입방법]

* 6을 삽입하고 싶다?

(1) 루트노드인 7보다 찾는 노드(6)가 작다 => 왼쪽 자식 노드로 진입

(2) 현재노드인 3보다 찾는 노드(6)가 크다 => 오른쪽 노드로 진입

(3) 현재노드인 5보다 찾는 노드(6)가 크다 => 오른쪽 노드로 진입

(4) 오른쪽 노드가 NULL이다. => 이 곳에 삽입

[삭제방법]

삭제하는 유형과정에는 크게 세 가지가 있다. 

[1] 삭제하려는 노드가 자식노드가 없다. => 그냥 삭제하면 된다.

[2] 삭제하려는 노드가 자식노드가 1개다. => 삭제하고 자식노드로 대체한다.

[2] 삭제하려는 노드가 자식노드가 2개다. => 삭제하고 왼쪽서브트리 중에서 가장 큰거 OR 오른쪽서브트리 중에서 가장 작은거를 선택해서 대체한다.

* 5를 지우고 싶다(자식노드가 없는 경우)

이진탐색을 통해 5를 찾는다. => 5를 그냥 삭제한다.

* 2를 지우고 싶다(자식노드가 1개인 경우)

이진탐색을 통해 2를 찾는다. => 2를 삭제하고 그 자식노드를 연결한다.

* 3을 지우고 싶다(자식노드가 2개인 경우)

이진탐색을 통해 3을 찾는다 

=> 오른쪽 서브 트리 중에서 가장 작은 수 OR 왼쪽 서브 트리 중에서 가장 큰 수를 선택 찾는다.

=> 3을 지우고 위에 선택된 수로 대체한다. 

=> 가장 작은 수 또는 가장 큰 수의 노드를 제거한다. 

* 6을 지우고 싶다(해당하는 노드가 없는 경우)

6을 탐색한다. 없다. 끝.

==> 이 부분은 실제 소스를 통해서 구현하면서 자잘한 부분에 대해서 설명하는 편이 낳을 것 같다.

이진탐색트리의 효율 및 최악의 케이스?

이진탐색트리는 보통 O(logN)의 시간효율을 갖는다. 

하지만 다음과 같은 경우(편향이진트리) 에는 O(N)시간이 걸린다.

편향이진트리 역시 이진트리이다. 자식을 두 개까지 가질 수 있는 트리이기 때문이다. 하지만 이건 트리가 아니라 리스트라고 할 수 있겠다.

편향이진트리에서 리프노드까지 5번이동해야 한다.

보통의 이진트리에서는 리프노드까지 logN의 이동만에 도달할 수 있는데에 비해서 정말 느린것이다.

그렇다면 O(logN)과 O(N)의 시간 차이가 그렇게 큰 것인가?

예를 들어 트리노드의 개수가 100,000개라고 쳐보자!

O(log100000) => 5

O(100000) => 100000

이렇게나 엄청난 차이가 난다.!!!

위상정렬을 왜 쓰는가? 

쉬운 예로 설명할 수 있겠다. 

1) 스타크래프트를 할 때 고급 건물을 짓기 위해서 먼저 지어야 되는 건물들이 있다.

이러한 순서를 나타낸 것을 위상정렬이라고 할 수 있겠다. 

이러한 순서와 관계를 정리해주는 것을 위상정렬이라고 하겠다. 

2) 학교 수강 과목 중에 반드시 선수되어야 할 과목들이 있을 것이다. 이렇게 어떠한 과목을 듣기 전에 듣고 가는 과정을 나타내는 것을

위상정렬이라고 할 수 있겠다. 

위상정렬를 구하는 방법에 대해서 간단히 설명하겠습니다.

우선 위상정렬은 방향이 있는 비순환 그래프에서 가능한 것입니다. 

위와 같은 그래프가 있습니다. 

1) 우선 위상정렬을 구하기 위해서는 진입하는 간선이 없는 노드를 찾습니다.

2) 찾은 노드를 저장합니다.

3) 이 노드에서 빠져나가는 간선들을 다 지워줍니다.

4) 1)의 과정으로 돌아갑니다. 

자신으로 들어오는 간선이 없는 노드를 indegree가 0인 노드라고 표현합니다.

이러한 과정을 반복해서 나온 노드들의 번호들의 순서가 위상정렬이 됩니다. 

다음과 같은 반복이 I까지 가게됩니다.