데이터베이스에 대해 정리하면서 데이터베이스 관리 시스템에 대해서도 정리하기는 했지만 DBMS의 내부 구성이 어떤지 어떻게 작동하는지에 대해서도 알아둘 필요가 있다. 

2019/06/07 - [IT 정보 로그캣/데이터베이스] - [데이터 베이스] 데이터베이스란 ?

데이터 언어

 데이터베이스 관리 시스템의 구성을 이해하기 위해 데이터 언어부터 살펴보자.  

데이터베이스 관리 시스템을 사용하기 위해서는 데이터 언어(Data Language)를 사용해야한다.

보통은 데이터 언어라고하면 SQL을 의미한다고 생각하면 되는데 이러한 데이터 언어도 기능에 따라 개념이 나뉘어진다.

• 데이터 정의어(DDL, Data Definition Language) : 스키마를 정의하거나, 수정 또는 삭제하기 위해 사용하는 언어. 데이터 정의어로 정의된 스키마는 데이터 사전에 저장되고, 삭제나 수정이 발생하면 이 내용도 데이터 사전에 반영된다. Create, Alter, Drop 등이 있다.
  
  

• 데이터 조작어(DML, Data Manipulation Language) : 데이터의 삽입, 삭제, 수정, 검색 등의 처리를 요구하기 위해 사용하는 언어. Select, Insert, Delete, Update 등이 있다.
  
  

• 데이터 제어어(DCL, Data Control Language) : 내부적으로 필요한 규칙이나 기법을 정의하기 위해 사용하는 언어. Commit, Rollback, Grant, Revoke 등이 있다. 
  
  

스키마(schema)란
스키마는 데이터베이스에 저장되는 데이터 구조와 제약조건을 정하는 것을 의미한다. 
예를들어 데이터베이스는 데이터에 INT, CHAR 등의 데이터 타입을 지정한다거나, 중복된 값을 허용하지 않는 등의 제약조건을 지정할 수 있다.

데이터베이스 관리 시스템의 구성

 데이터베이스 관리 시스템은 기능에 따라 크게 질의 처리기와 저장 데이터 관리자로 구성되어 있다.

질의 처리기(Query Processor)

 질의 처리기는 사용자의 데이터 처리 요구를 해석하여 처리하는 역할을 한다. 

• DDL 컴파일러(DDL compiler) : 데이터 정의어로 작성된 스키마를 해석한다. 데이터베이스를 생성하거나, 스키마의 정의를 데이터 사전에 저장한다.
  
  

• DML 프리컴파일러(DML precompiler) : 응용 프로그램에 삽입된 데이터 조작어를 추출하여 DML 컴파일러에  전달한다.
  
  

• DML 컴파일러 (DML compiler) : 데이터 조작어 (삽입, 삭제, 수정, 검색) 요청을 분석하여 런타임 데이터베이스 처리기가 이해할 수 있도록 해석한다.
  
  

• 런타임 데이터베이스 처리기 (run-time database processor) : 저장 데이터 관리자를 통해 데이터베이스 접근하여 DML 컴파일러로 부터 전달받은 요청을 데이터베이스에서 실제로 실행한다.
  
  

• 트랜잭션 관리자(transaction manager) : 데이터베이스에 접근하는 과정에서 사용자의 접근 권한이 유효한지 검사하고, 데이터베이스 무결성을 유지하기 위한 제약조건 위반 여부를 확인한다. 회복이나 병행 수행과 관련된 작업도 한다.

컴파일러(compiler)란
컴파일러는 특정 프로그래밍 언어로 쓰여 있는 문서를 다른 프로그래밍 언어로 옮기는 프로그램을 말한다. 컴파일러가 우리가 작성한 고급 프로그래밍 언어는 컴퓨터가 이해할 수 있는 언어(기계어)로 변환해주어야 실행된다.
DBMS 에서도 마찬가지로 사용자가 작성한 데이터 언어가 수행될 수 있도록 컴파일러가 변환해주는 것이다.

저장 데이터 관리자(stored data manager)

 저장 데이터 관리자는 디스크에 저장되어 있는 사용자 데이터베이스와 데이터 사전을 관리하고, 접근한다. 

하지만 디스크에 저장된 데이터에 접근하는 것은 운영체제의 기본 기능이므로 저장 데이터 관리자는 운영체제의 도움을 받아 데이터베이스에 대한 접근을 수행한다.

데이터 사전(data dictionary)란
 데이터 사전이란 시스템 카탈로그(system catalog)라고도 한다. 데이터 사전은 데이터베이스에 저장되는 데이터에 관한 정보를 저장한다.
데이터에 대한 정보를 의미하기 때문에 메타 데이터라고도 한다. 데이터 사전도 그냥 하나의 데이터베이스라고 생각하면 된다.

 HTTP 에는 쿠키라는 개념이 존재하는데, 이름부터가 친숙하고 귀엽다. 

왜 쿠키라는 이름이 붙여졌을까에는 여러가지 이야기들이 있는데, 내가 처음 공부할 때 들었던 이야기는 헨젤과 그레텔 동화에서 쿠키라는 이름이 유래했다는 것이다. 동화에서 헨젤과 그레텔이 자신들이 지나온 길을 표시하기 위해 쿠키조각을 바닥에 떨어뜨린 것과 마찬가지로 서버에 요청한 사람이 누구인지 표시하기 위해 클라이언트에 쿠키를 남긴다해서 쿠키라 부른다는 것이다. ( ..그럴싸 하다.)

또 다른 이야기로는 쿠키 안에 운세 같은 메세지가 담겨있는 포춘쿠키와 유사하다고 해서 쿠키가 되었다라는 이야기도 있다.

하지만 사실은 유닉스 운영체제에서 두 프로그램 사이에 전송되는 작은 데이터 패킷을 매직 쿠키라 불렀는데 여기서 HTTP 쿠키가 유래되었다. HTTP 쿠키를 만든 루 몬텔루 라는 웹 브라우저 개발자가 사용자들의 방문 기록을 남기기 위해 매직 쿠키에서 개념을 차용해서 사용한 것이다.

(.. 출처는 구글질문 에서 찾았는데 루 몬텔루에게 직접 확인된 사실이라 한다. 물론 위키백과에도 나와있다. 위에 언급된 이야기들은 아마 매직쿠키의 유래가 아닌가 싶다. )

HTTP 쿠키( Cookie) 란

 HTTP 쿠키는 웹 쿠키, 브라우저 쿠키로도 불리는데 서버가 사용자의 웹 브라우저에 전송하는 작은 데이터 조각을 의미한다.

위에서 언급했듯이 유닉스의 매직쿠키에서 이름과 개념이 유래하였고, 루 몬텔루라는 웹 브라우저 개발자가 웹 사이트에 접속한 클라이언트를 확인하기 위해 만들었다. HTTP 통신은 stateless 하기 때문에 클라이언트를 확인하기 위해서는 쿠키라는 개념이 따로 필요했기 때문이다.

쿠키는 주로 세션 관리( 서버에서 관리하는 로그인 등의 정보를 의미한다. ), 개인 설정유지, 사용자 트래킹( 사용자의 행동을 기록하고 분석하는 것 ) 용도로 사용된다.

HTTP의 stateless 란
statsless 라는 것은 번역하자면 상태가 없다는 뜻이다. HTTP에서 stateless 하다는건 서버 입장에서 클라이언트의 상태가 없다는 의미로 동일한 클라이언트의 요청이라도 매번 각 요청은 독립적이라는 의미이다. 예를들어 놀이공원(서버)에서 손님이 입장(요청)했다가 퇴장(응답)했을 때 손님들을 한명 한명 다 기억할수가 없다. 그렇기 떄문에 놀이공원에서는 재입장하는 손님을 구분하기 위해 팔찌같은 입장권을 준다.
마찬가지로 서버에서도 이미 요청을 했었던 클라이언트인지 매번 확인하기 어렵기 때문에 입장권처럼 쿠키를 주는 것이다.

HTTP 쿠키의 특징

• 쿠키는 한개에 4KB 까지 저장 가능하며, 최대 300개 까지 저장할 수 있는 텍스트 파일이다.
  
  

• 쿠키는 클라이언트에 저장된다.
  
  

• 쿠키에는 이름, 값, 만료날짜, 경로 정보가 들어있다.
  
  

• 기본적으로 쿠키는 웹 브라우저가 종료되면 삭제된다. ( 만료날짜를 지정해 주면 만료일이 되야 삭제된다.)
  
  

• 웹 브라우저에 해당 서버의 쿠키 정보가 있으면 HTTP 요청 (HTTP 헤더의 Cookie)에 무조건 담아 보낸다.

HTTP 쿠키 작동방식

 쿠키도 결국 HTTP 통신에서 이루어지는 것이기 때문에 HTTP 의 응답과 요청에 따라 작동한다.

요청을 받은 서버에서 쿠키를 클라이언트(웹 브라우저)로 보내고 클라이언트는 쿠키를 받으면 도메인 서버 이름으로 정렬된 쿠키 디렉토리에 쿠키(정보)를 저장한다. 이후 클라이언트가 동일한 서버로 HTTP 요청을 보내면 저장된 쿠키도 같이 전송되며, 만약 서버에서 쿠키에 업데이트된 내용이 있으면 응답할 때 다시 업데이트된 쿠키를 보내준다.

HTTP 세션(seesion) 이란

 세션이란 통신을 하기 위해 서로 연결된 순간부터 통신을 마칠 때 까지의 기간을 의미한다.

단순히 session 의 뜻을 찾아보아도 시간, 시즌 이라고 나온다.

HTTP 세션이란 클라이이언트가 웹서버에 연결된 순간부터 웹 브라우저를 닫아 서버와의 HTTP 통신을 끝낼 때 까지의 기간이다.

하지만 보통 세션이라고 말할 때에는 서버에 세션에 대한 정보(세션 상태, 클라이언트 상태, 세션 데이터 등)를 저장해 놓고 세션 쿠키( 고유한 세션 ID 값 )를 클라이언트에게 주어 서버가 클라이언트를 식별할 수 있도록 하는 방식자체를 의미하는 경우가 많다.

세션의 특징

• 따로 용량의 제한이 없다. ( 서버의 능력에 따라 다를 수 있다. )
  
  

• 서버에 세션 객체를 생성하며 각 클라이언트 마다 고유한 세션 ID 값을 부여한다.
  
  

• 쿠키를 사용하여 세션 ID 값을 클라이언트에 보낸다.
  
  

• 웹 브라우저가 종료되면 세션 쿠키는 삭제된다.

세션 작동방식

 세션의 작동방식을 보면 우선 클라이언트가 서버에 요청을 보내면 서버에서는 요청헤더( Cookie )를 확인하고 세션 ID가 있는지 확인한다. 

만약 요청에 세션 ID가 없다면 서버에서는 세션 ID를 생성한 뒤 응답을 보낼 때 쿠키에 세션 ID를 담아 보낸다. (서버에서는 이때 가장 먼저 세션 객체를 생성하여 정보를 저장한다.)

클라이언트는 응답에서 받은 세션 쿠키(세션 ID 값)를 저장해두고, 매번 해당 서버에 요청을 보낼 때마다 세션 쿠키를 함께 보내서 자신이 누구인지 인증한다. 세션 쿠키는 브라우저가 종료되면 삭제된다.

쿠키와 세션의 관계

 흔히 쿠키와 세션을 비교할 때 쿠키는 클라이언트(웹 브라우저)에 정보를 저장하는 것이고, 세션은 서버에 정보를 저장하는 것이다 라고 비교한다. 맞는 말이지만 마치 서로 반대되는 개념처럼 오해할 수 있는데, 결국 세션은 쿠키를 이용하는 하나의 방식일 뿐이다. ( 쿠키와 세션은 방식의 차이일 뿐 반대 개념이 아니다. )

쿠키는 stateless 한 HTTP 통신에서 클라이언트에게 정보(표시)를 주어 해당 클라이언트를 식별하기 위해 만들어졌다.

클라이언트가 식별이 가능해야 서버는 특정 클라이언트와 계속해서 통신을 하고 있는지 확인이 가능하기 때문이다.

하지만 클라이언트에 저장된다는 쿠키의 특징은 보안에 있어서는 치명적인 단점이다.

예를들어 로그인을 위해 사용자가 입력한 아이디와 비밀번호를 쿠키에 담아 클라이언트에 저장한 뒤 서버에서는 쿠키로 해당 사용자가 로그인한 사용자인지 확인한다고 생각해보자. 그러면 누군가 마음만 먹으면 쿠키를 확인해 클라이언트에 저장된 아이디와 비밀번호를 볼 수 있다.

그래서 세션이라는 개념을 통해 중요한 정보는 서버에서 관리하고 클라이언트에게는 세션 쿠키( 세션 ID )를 주어 식별이 가능하도록 한 것이다. 

결론적으로 사전적 정의로 보면 세션( 통신을 시작하고 마칠 때 까지의 기간)을 유지하기 위해 쿠키를 사용하는 것인데, 용어 상으로는 세션이란 서버에 정보를 저장하고 세션 쿠키를 통해 클라이언트를 식별하는 방식을 통틀어 말하는 것으로 보면 되겠다.

쿠키와 세션 정리

 쿠키와 세션도 결국 목적( 클라이언트에서 관리하느냐, 서버에서 관리하느냐 )에 맞게 사용하면 되겠다.

(.. 클라이언트는 믿을 수 없다. 중요한 정보나 처리는 서버에서 다뤄야한다! 만 명심하자.)

예를들어 쿠키는 쇼핑몰의 장바구니, 개인 설정(팝업창 표시여부 등) 같은 것들에 많이 사용되고 세션은 로그인 유지 등에 많이 사용된다. 

 개인 혹은 기업의 필요에 따라 데이터베이스 모델을 선택하여 사용하는데 아직까지는 관계형 데이터베이스가 주류를 이룬다. 데이터베이스에서 간단하게 설명을 했지만 자주 사용하는 것인 만큼 자세히 알아둘 필요가 있다.

2019/06/07 - [IT 정보 로그캣/데이터베이스] - [데이터 베이스] 데이터베이스란 ?

관계형 데이터베이스( Relational DataBase )란

 관계형 데이터베이스는 1970년대에 IBM에서 일하던 에드거 F. 커드가 제안한 데이터베이스 모델이다.

관계형 데이터 베이스는 데이터를 테이블 형태로 저장한다.

쉽게 생각하면 엑셀 표에 데이터를 저장하는 것과 동일하다고 보면된다.

실제로 각 데이터 항목들은 행(row)에 저장되고, 항목의 속성은 열(column)이라고 표현한다. 열은 항목의 속성인 만큼 입력되는 데이터의 유형이 정해진다.

용어 정리
* 열(column) : 필드(field) 라고도 부르며, 항목의 속성(명칭)을 나타낸다.  필드 마다 각각 정수, 텍스트 같은 데이터 유형을 정할 수 있다. 

* 행(row) : 레코드(record) 라고도 부르며, 각 데이터 항목을 저장한다. 

* 스키마(schema) : 필드는 데이터 유형뿐만 아니라 제약사항도 지정할 수 있는데 이러한 제약사항을 스키마라고 부른다. 예를들어 필드는 중복 값을 해당 행에 저장할 수 없다거나, 반드시 값을 가져야 한다(not null)는 조건 등을 걸 수 있다.

관계형 데이터베이스에서의 관계

 관계형 데이터베이스는 왜 관계라는 이름이 붙여졌을까?

결론부터 말하자면 각 테이블의 행과 행이 연결되는 관계를 맺을 수 있기 때문이다. 

테이블 간의 관계는 일 대 일(1:1), 일 대 다(1:N), 다 대 다(N:N) 의 관계가 있다.

우리는 하나의 테이블에 필요한 모든 필드를 넣고 모든 데이터 항목을 저장할 수 있다. 하지만 이렇게하면 데이터들이 중복해서 저장되는 상황이 발생할 수 있어 다음 그림 테이블과 같이 비효율적이다. 

그림과 같이 고객의 상품 주문을 저장하는 테이블이 있다고 가정하면 특정 고객이 여러 상품을 구매하는 경우 고객 이름과 고객 지역 데이터가 계속 해서 중복된다. 얼핏보기에는 별 문제 없어보이지만 만약에 고객의 지역이 변경된다고 생각해보자.

그림은 데이터가 3개 뿐이지만 만약 수십, 수백만 그 이상의 데이터라면 쉬운일이 아니다.

그래서 관계형 데이터베이스 모델에서는 다음 그림과 같이 테이블을 분리하여 행과 행을 연결할 수 있다.

그림과 같이 테이블 간의 관계는 기본 키(primary key) 와 외래 키(foreign key) 라는 개념을 사용하여 맺어질 수 있다.

기본 키는 고유한 ID 필드로 그림에서는 고객 번호 필드이다. 이 필드는 각 행이 중복된 값을 가질 수 없다.

외래 키는 기본 키를 참조하는 필드로 그림에서는 주문 테이블의 고객 번호 필드이고 각 테이블의 행을 연결시켜주는 역할을 한다.

이렇게 테이블을 분리하고 관계를 형성해 데이터를 효율적으로 관리할 수 있다.

( 테이블을 분리하고 중복 데이터를 제거하는 과정을 정규화 라고 한다.)

SQL(Structured Query Language) 이란 

 관계형 데이터베이스에서 주요한 특징 중 하나는 SQL이라는 구조화 질의어를 사용한다는 것이다. SQL은 RDBMS에서 사용하는 프로그래밍 언어라고 보면 된다. SQL을 통해 RDBMS에서 데이터를 검색하고, 추가하고, 업데이트하고, 삭제하는 작업 등 데이터를 관리한다.

SQL의 종류로는 데이터 정의 언어, 데이터 조작 언어, 데이터 제어 언어 가 있는데 결국 RDBMS를 다루려면 모두 알아야하기 때문에 종류가 나뉘어 진다라는 정도만 알면 될 것 같다.

트랜잭션(transaction)이란

 트랜잭션은 데이터베이스 관리시스템(DBMS)에서 하나의 작업의 단위이다.

데이터베이스는 여러 사람들이 데이터를 공유하고 사용할 목적으로 사용된다. 그렇기 때문에 다수의 사람들이 동시에 사용하더라도 데이터에 문제가 없어야한다. 트랜잭션은 모든 명령문을 완벽하게 처리하거나, 하나의 명령문이라도 문제가 발생하면 모든 명령문을 수행하지 않고 데이터를 보존하는 기능을 하고 해야한다.

트랜잭션의 예시에 가장 적합한게 은행이라고 볼 수 있다. 예를들어 A계좌에 1000원이 있다고 하자. 이때 서로 다른 2대의 ATM 기기에서 동시에 A계좌의 1000원을 인출하려고 한다. 정말 거의 동시에 인출을 시도했을 때 트랜잭션이 제대로 기능하지 않아 두명 다 각각 1000원씩 인출해 간다면 은행은 아마 파산할 것이다. 그래서 은행은 두 트랜잭션을 모두 수행하지 않거나, 0.000001 초라도 빠른 사람의 요청을 수행하고 나머지 사람에게는 지급부족으로 요청을 거절해야 한다.

이러한 트랜잭션의 기능을 제대로 수행하기 위해서는 네 가지 특성을 만족해야하는데 ACID 특성이라고 부른다.

• 원자성 (Atomicity) : 원자성이란 트랜잭션이 수행하는 연산들을 모두 정상적으로 처리하거나 모두 처리하지 않아야 한다는 all-or-nothing 방식을 의미한다. 
  
  

• 일관성 (Consistency) : 일관성은 트랜잭션이 성공적으로 수행된 이후에도 데이터베이스의 데이터는 일관된 상태를 유지해야 한다는 의미이다.
  
  

• 격리성 (Isolation) : 격리성은 하나의 트랜잭션이 완료될 때까지 다른 트랜잭션이 간섭하지 못하도록 하여 각각의 트랜잭션이 독립적으로 수행되어야 한다는 의미이다.
  
  

• 지속성 (Durability) : 지속성은 트랜잭션이 성공적으로 완료된 이후에 데이터베이스의 데이터들이 영구적으로 보존되어야 한다는 의미이다. 
  
  

 우리는 자료와 정보라는 말을 많이 사용한다. 보통 두 단어를 혼동해서 많이 사용하는데  엄밀히 따지자면 각각 정의가 다르다.

자료(Data) 는 숫자, 영상, 단어 등의 형태로 된 의미 단위로 날것(raw)에 가깝다. 이러한 자료에 의미를 부여하거나 정리하면 정보가 된다.  

실제로 크게 구분하진 않지만 알아두면 좋을 것 같다!

데이터베이스 (DB, database )란

 데이터베이스란 여러 사람들이 공유하고 사용할 목적으로 통합 관리되는 데이터들의 모임이다.

등산할 때 기반이 되는 기지를 베이스캠프라 하듯이 데이터베이스라는 용어도 1950년대 미국에서 데이터의 기지라는 뜻에서 데이터베이스라는 용어를 처음 사용했다고 한다. 

(..데이터를 모아둔 창고라고 생각하면 되겠다.)

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

 데이터베이스 관리 시스템이란 다수의 사용자들이 데이터베이스 내의 데이터를 접근할 수 있도록 해주는 소프트웨어들을 의미한다.

데이터베이스 관리 시스템이 존재하기 이전에는 파일 시스템을 이용하여 데이터를 관리하였다.

파일 시스템은 응용 프로그램을 이용해 데이터를 파일로 관리하는 것이다.

예를들어 쇼핑몰의 경우 고객관리 프로그램과 주문관리 프로그램이 존재하여 각각 데이터를 파일로 저장해 관리한다.

파일을 기반으로 데이터를 관리하게되면 데이터 중복, 데이터 불일치 등 문제가 발생한다.

이러한 파일 시스템의 단점을 보완하기 위해 데이터베이스가 생겨났다.

데이터베이스는 곧 데이터베이스 관리 시스템이라 할만큼 데이터베이스 관리 시스템은 중요하다고 볼 수 있다.

데이터베이스 관리 시스템을 전문적으로 운영하는 인력을 DBA (DataBase Administrator)라 한다.

데이터 불일치 문제란?
데이터 불일치 문제는 데이터를 파일로 저장했을 때 파일을 수정하는 도중에 해당 파일을 불러온다면 데이터가 동기화 문제가 발생하여 데이터가 불일치하는 문제가 발생할 수 있다.

데이터베이스 관리 시스템의 특징

데이터베이스 관리 시스템은 파일 시스템의 문제점을 해결하기 위해 만들어졌기 때문에 

데이터베이스 관리 시스템의 특징은 곧 파일 시스템의 단점을 의미한다.

1. 데이터의 독립성 ( 파일 시스템은 데이터와 응용 프로그램이 상호 의존 관계에 있다. )

• 물리적 독립성 : 데이터베이스 사이즈를 늘리거나 성능 향상을 위해 데이터 파일을 늘리거나 새롭게 추가하더라도 관련된 응용 프로그램을 수정할 필요가 없다.
  (파일 시스템은 응용 프로그램의 기능을 확장하려면 파일의 구조를 재조직해야 한다.)
  
  

• 논리적 독립성 : 데이터베이스는 다양한 응용 프로그램의 논리적 요구를 만족시켜줄 수 있다.
  ( 파일 시스템에서는 파일의 구조가 응용 프로그램에 반영되어 있기 때문에 파일의 구조가 바뀌면 영향을 받는 모든 응용 프로그램들을 수정해야 한다. )
  
  

2. 데이터의 무결성 

 : 여러 경로를 통해 잘못된 데이터가 발생하는 경우의 수를 방지하는 기능으로 데이터의 유효성 검사를 통해 데이터의 무결성을 구현하게 된다. 예를들면 입력 조건에 맞지 않는 입력값은 저장할 수 없도록 방지하는 기능이 있을 수 있다.

( 파일 시스템은 응용 프로그램 별로 제약 조건을 하나하나 처리해야하기 때문에 무결성을 유지하기가 어렵다. )

3. 데이터의 보안성 

 :  허가된 사용자들만 데이터베이스나 데이터베이스 내의 자원에 접근할 수 있도록 계정 관리 또는 접근 권한을 설정함으로써 모든 데이터에 보안을 구현할 수 있다.

( 파일 시스템은 파일 단위로 검색, 갱신, 실행 등의 권한을 부여할 수 있어서 사용자 별 세밀한 접근 제어가 어렵다.)

4. 데이터의 일관성 

 : 연관된 정보를 논리적인 구조로 관리함으로써 어떤 하나의 데이터만 변경했을 경우 발생할 수 있는 데이터의 불일치성을 배제할 수 있다.

또한 작업 중 일부 데이터만 변경되어 나머지 데이터와 일치하지 않는 경우의 수를 배제할 수 있다.

( 파일 시스템에서는 중복된 데이터를 변경하는 게 어렵기 때문에 중복 데이터 중 일부만 변경된다고 하면 중복 데이터 간에 불일치가 발생할 수 있다. )

5. 데이터의 중복 최소화 

 : 데이터베이스는 데이터를 통합해서 관리함으로써 데이터 중복 문제를 해결할 수 있다.

( 파일 시스템은 응용 프로그램별로 데이터를 파일로 관리하기 때문에 같은 데이터가 여러 파일에 저장되어 데이터 중복 문제가 발생할 수 있다. )

데이터베이스 관리 시스템의 종류

DBMS는 시간이 지남에 따라 계속해서 새로운 모델들이 제시되어 왔다.

기존의 DBMS 모델의 문제점이나 단점을 보완하기 위해 계속해서 새로운 모델들이 만들어지기 때문이다.

각 DBMS 모델을 간단히 정리해보면 다음과 같다.

계층형 ( Hierarchical DataBase )

• 데이터 간의 관계가 트리 형태의 구조이다. 트리는 부모-자식 관계로 표현되며 부모와 자식 간에는 1:N ( 일 대 다 )로 구성될 수 있다.
  데이터를 세그먼트 ( 레코드 ) 단위로 관리하며 세그먼트 간 계층을 트리구조로 관리한다. 구조가 간단하고 구현, 수정, 검색이 쉽지만 부모 자식 간에 N:N (다 대 다) 관계 처리가 불가능하고, 구조 변경이 어렵다.

• DBMS 예 : IMS ( IBM 의 Information Management System )

네트워크형 ( Network DataBase )

• 계층형 데이터베이스의 단점을 보완하여 데이터 간 N:N ( 다 대 다) 구성이 가능한 망 형 모델이다. 계층 구조에 링크를 추가하여 유연성과 접근성을 높였다. 하지만 구조가 복잡해 유지보수가 어렵다.

• DBMS 예 : IDMS ( Integrated Data Store ) 

관계형 ( Relational DataBase )

• 관계형 데이터베이스 모델은 키( key )와 값 ( value )으로 이루어진 데이터들을 행( row )과 열 ( Column )로 구성된 테이블 구조로 단순화 시킨 모델이다. SQL ( Structured Query Language ) 를 사용하여 테이터를 처리한다. 데이터 모델링이 간단하지만 CAD/CAM , GIS 등과 같은 비정형 데이터들을 다루거나 실시간 분석에는 적합하지 않다.

• DBMS 예 : MySQL 

객체 지향형 ( Object-Oriented DataBase )

• 객체지향 프로그래밍 개념에 기반하여 만든 데이터베이스 모델이다. 정보를 객체의 형태로 표현한다. 객체지향 프로그래밍 개념 ( 클래스, 상속 등 )을 사용할 수 있다.
  CAD/CAM. GIS 등의 비정형 데이터들을 데이터베이스화 할 수 있도록 하기 위해 만들어진 모델이다.
  멀티미디어 데이터 지원이 가능하지만 SQL 쿼리를 사용할 수 없고 ( OQL 이 있긴하다. ), 검색이나 대규모 트랜잭션 처리에서 성능이 떨어지는 단점이 있어 몇몇 특수한 전문분야 정도에서만 사용되고 있다.

• DBMS 예 : O2, ONTOS

객체 관계형 ( Object-Relational DataBase )

• 관계형 데이터베이스에 객체 지향 개념을 도입하여 만든 데이터베이스 모델이다. 객체지향 개념을 지원하는 표준 SQL을 사용할 수 있고, 데이터 타입도 관계형 데이터베이스 보다 더 다양하게 추가되었다.

• DBMS 예 : UniSQL, Object store

NoSQL 

• Not Only SQL 의 줄임말로 SQL 뿐만 아니라 다양한 특성을 지원한다는 의미라고 해석할 수 있다. 데이터 간에 관계를 정의하지 않는 데이터베이스 모델로 기존의 RDBMS 의 복잡도와 용량의 한계를 극복하기 위한 목적으로 만들어졌다. 비정형 데이터 처리에 유리하지만 스키마 변경이 불가능해  데이터값에 문제가 발생하면 감지가 어렵다. 

• DBMS 예 : redis

NewSQL

• New 와 SQL 의 합성어이다. RDBMS 의 SQL 과 NoSQL 의 장점을 결합하여 관계형 모델, 트랜잭션 지원 및 확장성과 고 가용성을 모두 만족시키려는 목적에서 만들어진 데이터베이스 모델이다.

• DBMS 예 : VoltDB

GET 과 POST 는 HTTP 메서드로 클라이언트에서 서버로 무언가를 요청할 때 사용한다. 

2019/06/01 - [IT 정보 로그캣/CS] - [네트워크] http 란

과거에  5년차 이상 서버 개발자와 일한 경험이 있는데, 로그인 API를 요청했는데 GET 과 POST 둘 다 요청이 가능하도록 만들어 주는 것이었다... 암호화를 한것도 아니라서 POST도 완벽한 보안이 되는건 아니지만 정말 최소한의 보안 의식도 없는건가 아니면 구분을 못해서 그런건가 싶었다. 이렇듯 HTTP 통신을 제대로 사용하기 위해서도 둘의 차이를 아는 게 중요하다.

GET 이란?

 GET 은 클라이언트에서 서버로 어떠한 리소스로 부터 정보를 요청하기 위해 사용되는 메서드이다. 

예를들면 게시판의 게시물을 조회할 때 쓸 수 있다.

GET을 통한 요청은 URL 주소 끝에 파라미터로 포함되어 전송되며, 이 부분을 쿼리 스트링 (query string) 이라고 부른다.

방식은 URL 끝에 " ? " 를 붙이고 그다음 변수명1=값1&변수명2=값2... 형식으로 이어 붙이면 된다.

예를들어 다음과 같은 방식이다. 

www.example.com/show?name1=value1&name2=value2

서버에서는 name1 과 name2 라는 파라미터 명으로 각각 value1 과 value2 의 파라미터 값을 전달 받을 수 있다.

GET의 특징

• GET 요청은 캐시가 가능하다. 

   : GET을 통해 서버에 리소스를 요청할 때 웹 캐시가 요청을 가로채 서버로부터 리소스를 다시 다운로드하는 대신 리소스의 복사본을 반환한다. HTTP 헤더에서 cache-control 헤더를 통해 캐시 옵션을 지정할 수 있다.
  
  

• GET 요청은 브라우저 히스토리에 남는다.
  
  

• GET 요청은 북마크 될 수 있다.
  
  

• GET 요청은 길이 제한이 있다.

   : GET 요청의 길이 제한은 표준이 따로 있는건 아니고 브라우저마다 제한이 다르다고 한다. 
  
  

• GET 요청은 중요한 정보를 다루면 안된다. ( 보안 )

   : GET 요청은 파라미터에 다 노출되어 버리기 때문에 최소한의 보안 의식이라 생각하자.
  
  

• GET은 데이터를 요청할때만 사용 된다.

POST 란?

 POST는 클라이언트에서 서버로 리소스를 생성하거나 업데이트하기 위해 데이터를 보낼 때 사용 되는 메서드다. 예를들면 게시판에 게시글을 작성하는 작업 등을 할 때 사용할 된다.

POST는 전송할 데이터를 HTTP 메시지 body 부분에 담아서 서버로 보낸다. ( body 의 타입은 Content-Type 헤더에 따라 결정 된다.)

GET에서 URL 의 파라미터로 보냈던 name1=value1&name2=value2 가 body에 담겨 보내진다 생각하면 된다.

POST 로 데이터를 전송할 때 길이 제한이 따로 없어 용량이 큰 데이터를 보낼 때 사용하거나 GET처럼 데이터가 외부적으로 드러나는건 아니라서 보안이 필요한 부분에 많이 사용된다. 

( 하지만 데이터를 암호화하지 않으면 body의 데이터도 결국 볼 수 있는건 똑같다. )

POST를 통한 데이터 전송은 보통 HTML form 을 통해 서버로 전송된다. 

POST의 특징

• POST 요청은 캐시되지 않는다.
  
  

• POST 요청은 브라우저 히스토리에 남지 않는다.
  
  

• POST 요청은 북마크 되지 않는다.
  
  

• POST 요청은 데이터 길이에 제한이 없다.

GET 과 POST 의 차이점 

 GET과 POST의 특징만 보아도 차이가 나긴하지만 추가적으로 차이점을 정리해보면 다음과 같다.

• 사용목적 : GET은 서버의 리소스에서 데이터를 요청할 때, POST는 서버의 리소스를 새로 생성하거나 업데이트할 때 사용한다.

  DB로 따지면 GET은 SELECT 에 가깝고, POST는 Create 에 가깝다고 보면 된다.
  
  

• 요청에 body 유무 : GET 은 URL 파라미터에 요청하는 데이터를 담아 보내기 때문에 HTTP 메시지에 body가 없다. POST 는 body 에 데이터를 담아 보내기 때문에 당연히 HTTP 메시지에 body가 존재한다.
  
  

• 멱등성 (idempotent) : GET 요청은 멱등이며, POST는 멱등이 아니다.
  
  

멱등이란?

멱등의 사전적 정의는 연산을 여러 번 적용하더라도 결과가 달라지지 않는 성질을 의미한다.

GET은 리소스를 조회한다는 점에서 여러 번 요청하더라도 응답이 똑같을 것 이다. 반대로 POST는 리소스를 새로 생성하거나 업데이트할 때 사용되기 때문에 멱등이 아니라고 볼 수 있다. (POST 요청이 발생하면 서버가 변경될 수 있다.)

GET과 POST는 이런 차이들이 있기 때문에 사용하려는 목적에 맞는 확인한 후에 사용해야한다.

GET과 POST 이외에도 PUT , DELETE 등을 적절히 사용하는게 좋은데 예를들어 봇의 경우에 사이트를 돌아다니면서 GET 요청을 날린다. 이럴 때 DELETE 등을 GET으로 처리하면 봇에 의해 서버에 있는 리소스들이 삭제 되는 상황이 일어 날수 있다! 항상 기술을 사용할 때 왜 를 잊지말자.

 기본적으로 네트워크 통신을 할 때 처음 접하는게 http 통신이다. 

개발자가 아니더라도 http는 많이 듣는 용어일 정도로 우리가 많이 접하고 있고, 중요하다.

내가 사용하는 기술이 최소한 어떤 건지, 왜 사용하는지 정도는 알고 있어야 한다고 생각하기 때문에 이번 기회에 간략히 정리를 한다.

HTTP 란?

 HTTP 는 HyperText Transfer Protocol 의 줄임말로 www 상에서 사용하는 프로토콜이다.

1990년 대 팀 버너스리가 월드와이드웹을 만들어서 하이퍼텍스트 문서들을 주고 받기 위한 규약으로 만든 것이 HTTP 이다. 현재에는 문서들 뿐만 아니라 이미지, 비디오, 음성 등 거의 모든 형식의 데이터를 전송하는데 사용 되고있다.

HTTP는 서버와 클라이언트 사이에 요청과 응답을 주고 받는 프로토콜로 우리가 흔히 웹브라우저 주소창에 입력하는 웹 주소인 URL을 통해 요청과 응답이 이루어진다.

실제 전송은 TCP를 통해 이루어 지며 포트는 80번을 이용한다.

용어 정리

• 하이퍼텍스트(HyperText) : 참조(하이퍼링크)를 통해 한 문서에서 다른 문서로 즉시 접근할 수 있는 텍스트를 의미한다. 하이퍼텍스트라는 용어는 1965년 테드 넬슨이라는 철학자가 만들었다. 

• 월드와이드 웹(www, World Wide Web) : 인터넷에 연결된 컴퓨터를 통해 사람들이 정보를 공유할 수 있는 가상의 공간이다. 1990년대 팀 버너스리가 하이퍼텍스트들을 인터넷 상에서 웹주소인 URL(Uniform Document Idenfier) 을 통해 연결 시키려고 만든 것이다. 팀 버너스리는 www 를 모두 공개했고, 이후 웹이 퍼져나가면서 웹 브라우저도 개발 되었다. 

HTTP 버전

 HTTP는 초기에 버전 표기가 없었고, 이후 업데이트되면서 버전 표시가 필요하게 되어 1991년 HTTP/0.9 부터 시작하여 1996년 HTTP/1.0 을 거쳐  1999년  HTTP/1.1 까지 확장 되었다. HTTP/1.1 이후로는 버전 업 없이 계속 사용되고 있다. 

 하지만 오늘날 웹 환경은 과거에 비해 더 많은 리소스를 사용하고, 동적인 부분이도 많아지고, 보안이 중요해지는 등의  변화를 겪다 보니 HTTP/1.1에 한계를 많이 느끼게 된다. 그래서 2015년 구글이 SPDY 프로토콜을 기반으로 만든 HTTP/2 가 공식적으로 표준화 되어 나왔다.

아직까지 많은 사이트들에서  HTTP/1.1을 사용하지만 HTTP/2을 지원하는 사이트들도 늘어나고 있다.

버전 정리

• HTTP/0.9 :  단순한 구성으로 이루어져 요청가능한 메서드는 GET 이 유일했고, HTTP 헤더가 존재하지 않아 HTML 파일만 전송이 가능했다. 
  
  

• HTTP/1.0 : HTTP 헤더 개념이 도입되어, 브라우저가 요청에 대한 성공과 실패를 알 수 있게 되었다. 데이터에 대한 정보를 담고 있는 메타데이터 전송도 허용하고, Content-Type 의 추가는 HTML 외에 다른 문서들도 전송 가능하게 하였다.
  
  

• HTTP/1.1 : HTTP의 표준 프로토콜이며 많은 부분들이 개선되었다. 개선된 부분 중에는 커넥션 제어에 관한 두가지 모델의 추가도 있다. 하나는 커넥션이 재사용될 수 있는 모델로 서버를 다루다 보면 보게되는 Keep-Alive 옵션이다. 또 다른 하나는 파이프라이닝을 추가하여 요청에 대한 응답이 완전히 전송되기 이전에 두번째 요청을 전송 가능하게 하여 네트워크 지연을 줄이는 모델이다.

단일 모델

커넥션 재사용 모델

파이프라이닝 모델

• HTTP/2 : 구글이 만들었고, 네트워크 지연 시간을 줄이기 위한 성능에 목표를 둔 HTTP의 두 번째 버전. HTTP 헤터 데이터 압축이나 서버 푸시기술 추가 등 많은 부분들이 보완되었다.
  ( HTTP/2 공부를 따로 해야할 정도이다.. )
  하지만 중요한 점은 HTTP/2 가 HTTP 표준을 대체하는 것이 아니라 확장한다는 점이다.
  (구글이 직접 발표한 부분이다!)

HTTP 메시지 구조 

 HTTP  메시지는 ASCII 로 인코딩된 텍스트로 되어 있다. 

기본적인 메시지 구조는 다음과 같다.

 HTTP 메시지는 기본적으로 클라이언트가 요청하고 서버가 응답하는 구조이기 때문에 메시지는 요청이냐 응답이냐에 따라 각 메시지의 구성 내용이 달라 진다.

HTTP 메서드 

 HTTP 메서드는 클라이언트가 서버에 요청의 목적 및 종류를 알리는 수단이다.

HTTP 요청시에 메세지 시작줄에 표시된다.

RestFul API 구조 등이 많이 사용되기 때문에 주로 GET , POST, PUT, DELETE 정도의 메서드 위주로 알아 두면 좋다.

HTTP 헤더 

 HTTP 메시지 구조를 보면 HTTP 헤더가 들어가는데 요청/응답 헤더 , general 헤더, entity 헤더 로 구분된다.

헤더는 기본적으로 key : value 방식으로 표기되며, 헤더안에 들어갈 수 있는 종류는 매우 많다.

하지만 주로 많이 사용되는 헤더들을 정리해보자면 다음과 같다.

요청(request) 헤더

응답(response) 헤더

general 헤더

entity 헤더 ( body 가 없는 경우 전송되지 않음)

HTTP 상태코드

 HTTP 상태코드는 응답 메시지 중에서도 start-line 에 표기 된다. 

HTTP 상태코드는 요청에 대한 처리 결과를 알려 준다.

상황에 따라 상태코드는 3자리 숫자로 표현하는데 100 대 부터 500 대까지가 있다. 

상태 코드별 값과 의미가 다양 하지만 각 번호대의 대략적인 의미는 다음과 같다.

• 1xx : 정보성 

• 2xx : 성공 

• 3xx : 리다이렉션

• 4xx : 클라이언트 오류

• 5xx : 서버 오류

알고리즘 문제를 풀다보면 프랙탈(fractal)  과 같이 패턴이 반복되는 구조를 마주칠 때가 있다. 

반복되는 구조를 코드로 작성하려면 for 문을 사용하면 되지만 재귀함수를 통해서도 구현할 수 있다.

결국 자신이 원하는 결과를 얻기 위해 올바른 코드를 작성했으면 for 문이든 재귀함수든 결과는 똑같겠지만

그럼에도 불구하고  for문과 재귀함수에 어떤 차이가 있는지 알고 사용하는게 중요하다. 

개인적으로는 자신에게 쉽고 빠른 방법을 선택하는게 좋은 것 같다 :) 

재귀함수 (Recursive Function) 란?

 재귀라는 단어는 원래 자리로 되돌아가거나 되돌아옴 을 뜻한다.

프로그래밍에서 재귀는 자기 자신을 호출하는 것을 의미한다.

이러한 재귀의 의미를 사용하여 자기 자신을 다시 호출하여 재참조하는 구조의 함수를 재귀함수라고 한다.

재귀함수의 구조

 재귀 함수는 보통 피보나치 수열이나 하노이의 탑 알고리즘에서 많이 사용된다. 

이외에도 1 부터 n 까지 숫자의 합이나 팩토리얼 ( ! ) 같은 연산을 할 때에도 사용될 수 있다.

예를들어 1 부터 n 까지 숫자의 합을 구하는 재귀함수는 아래와 같다.

public int sum(int n){
	
    if(n==0) {
    return 0;
    }
    
    return n + sum(n-1);
}

int total = sum(10); // 55 ( 1 부터 10까지의 합 ) 

재귀함수를 살펴보면 return 을 통해 다시 자기자신을 호출하고 있는 걸 볼 수 있다.

그런데 재귀함수를 사용할 때 주의할 점이 있다. 재귀함수가 종료되는 조건을 넣어 줘야한다는 것이다. 그렇지 않으면 재귀함수는 무한루프에 빠지게 된다.

코드에서 보듯이 처음에 if 문을 통해 n 이 0 인지 체크하고 0 이면 0 값을 반환하고 함수를 종료한다. 

재귀함수의 특징

1. 코드의 가독성이 좋다. 

2. 스택 메모리를 사용한다.

재귀함수와 for 문 (반복문) 의 차이

1. 메모리 

 : 재귀함수는 함수를 반복적으로 호출하기 때문에 스택 메모리를 사용한다.

(스택 오버플로우가 발생할 수 있다. )

반면 반복문은 메모리 힙을 사용한다.

2. 코드길이

 - 재귀함수를 사용하면 반복문에 비해 코드수를 줄일 수 있다. 

컴퓨터의 언어는 기계어라고 불리는 이진수이다. 

이진수는 독일의 철학자 라이프니츠가 발명한 수 체계이다. 

컴퓨터가 이진수를 사용하는 이유는 무엇일까?

그 이유는 전기신호로 작동하는 컴퓨터에게 전기가 통할 때 (1), 전기가 통하지 않을 때(0) 2가지 신호를 나타낼 수 있는 이진수가 가장 효율적이기 때문이다.

예를 들어 단순히 생각해보면 이진수는 전선이 하나만 있으면 표현이 가능하다. 

하지만 십진수의 경우 0부터 9까지 숫자를 표현 해야하기 때문에 10개의 전선이 필요하다.

십진수 체계에서 하나의 전기신호만 보내면 되는 상황이면 나머지 9개의 전선은 낭비인 것이다.

그래서 필요에 따라 이진수를 여러번 사용하는게 가장 효율적이다.

비트(bit) 란?

 비트는 데이터를 나타내는 최소 단위로 이진수의 한자리인 0 또는 1 의 값을 가진다. 

비트라는 이름은 바이너리 디지트(binary digit)의 약자를 의미한다.

부호 없는 N비트 정수형 변수는 N자리의 이진수로 나타낼 수 있다.

이때 비트가 표현하는 값은  부터  까지이다. 

여기서 에 해당하는 비트값을 최상위 비트(Most Significant Bit) 라 하고,   에 해당하는 비트값을 최하위 비트(Least Significant Bit) 라고 한다.

예를 들어 부호없는 4비트 정수형은 네 자리 이진수로 표시할 수 있는 모든 정수를 나타낼 수 있다. 

( 아래 그림과 같이 4칸의 공간에 이진수 0 또는 1을 넣은 모든 경우의 수를 의미한다. )

이때 비트가 표현하는 값은  부터 이다.

그리고 여기서 에 해당 하는 비트값(1) 이 최상위 비트이고  에 해당하는 비트값(1)이 최하위 비트이다.

비트마스크란?

 비트마스크에 대해 알기위해 기본적으로 컴퓨터의 언어인 이진수와 비트에 대해 알아보았다.

비트마스크란 컴퓨터의 언어인 이진수를 사용하면 연산이 빠른점을 이용해 어떠한 정수를 이진수 형태로 표현하여 자료구조로써 사용하는 기법이다.

비트마스크의 장점

 1. 다른 자료 구조에 비해 수행 시간이 더 빠르다. 

 2. 비크 연산자를 사용하여 코드가 더 간결해 진다. 

 3. 비트마스크를 사용하여 더 작은 메모리를 사용할 수 있다.

비트 연산

 비트 연산은 이진수에 대해 비트 단위로 적용되는 연산을 의미한다.

비트 연산자 ( java 기준 )

 1. AND 연산자( & ) : 두 정수를 한 비트씩 비교하면서 양쪽 비트가 모두 1이면 결과도 1 이고 나머지는 0 을 반환

예) 101 & 100 = 100

 2. OR 연산자( | ) : 두 정수를 한 비트씩 비교하면서 양쪽 비트 중 하나라도 1이면 결과가 1 이고 나머지는 0 을 반환

예) 101 | 100 = 101

 3. XOR 연산자 ( ^ ) : 두 정수를 한 비트씩 비교하면서 양쪽 비트가 서로 다르면 1 , 같으면 0을 반환

예) 101^100 = 010

 4. NOT 연산자 ( ~ ) : 정수 하나의 각 비트를  1 이면 0 , 0 이면 1 로 바꾸는 연산

예) ~101 = 010

 5. 쉬프트 연산자 ( a << b ) : 정수 a 를 왼쪽으로 b 비트 만큼  이동

예) 0000101 << 3 = 0101000

 6. 쉬프트 연산자 ( a >> b ) : 정수 a 를 오른쪽으로 b 비트 만큼 이동

예) 111000 >> 3 = 000111

 7. 쉬프트 연산자 ( a >>> b ) : 정수 a를 오른쪽으로 b 비트 만큼 이동 한뒤 왼쪽에는 모두 0 으로 채움

예) 11110000 >>> 3 = 00011110

비트마스크를 이용한 집합 

 비트마스크의 연산을 이용하면 비트마스크를 이용한 집합을 구현할 수 있다. 

기본적으로 0 을 공집합으로 여기고, 꽉찬 집합 ( 비트가 모두 1 인 집합) 을 구할 수 있다.

또한 집합에 원소를 추가하거나 삭제, 번경을 할 수 있으며 두 집합에 대해 연산도 가능하다.

집합의 크기 또한 구할 수 있는데 예를 들어 32비트 부호없는 정수를 a 에서 켜진 비트 (1) 의 수를 구할 수 있다. 구하는 방법은 언어 또는 컴파일러 별로 최적화되어 구현되어 있기 때문에 사용할 수 있다.

 1. gcc/g++ : __builtin_popcount(a)

 2. Visual C++ : __popcnt(a)

 3. java : Integer.bitCount(a)

 연결 리스트는 동적배열과 마찬가지로 배열의 단점을 보완하기 위해 만들어진 자료구조이다.

그렇다고해서 연결 리스트나 동적배열이 항상 배열 보다 좋다는 의미는 아니다. 

상황마다 장단점이 있기 때문에 자신의 필요에 따라 사용하면 된다.

C++에서는 STL 의 list , 자바에서는 LinkedList 로 표준 라이브러리에 구현되어 있다.

연결 리스트(Linked list) 란?

 연결 리스트란 자료구조의 각 부분부분인 노드들이 연결되어 있는 방식으로 데이터를 저장하는 자료구조이다. 노드는 데이터를 담는 박스 같은 개념으로 생각하면 된다.

연결리스트는 택배박스를 생각하면 쉽다. 

물건(데이터)이 담긴 택배 박스(노드)를 보면 보낸 곳(이전 노드 포인터)과 보낼 곳(다음노드 포인터)이 쓰여 있다. 여기서 포인터는 현실에서 처럼 주소값을 의미한다.

연결 리스트는 각 노드에 이전과 다음 노드에 대한 포인터를 가지고 있어 배열과 다르게 메모리 여기저기에 노드들이 흩어져 있다.

연결 리스트가 필요한 이유

 연결 리스트는 노드들 사이에 데이터를 삽입하거나 삭제하는 작업이 많을 때 필요하다.

노드에 이전 데이터와 다음 데이터의 포인터를 가지고 있어서 삽입과 삭제 작업을 O(1)에 처리 할 수 있기 때문이다. ( 포인터만 바꿔주면 된다! )

만약 배열로 이러한 작업들을 하게 되면 평균적으로 데이터 개수에 선형 비례하는 시간이 소요되어 비효율 적이다. 배열에서는 중간에 데이터를 삽입하거나 삭제할 때 데이터들을 한칸 씩 옮겨야 해서 

시간복잡도가 O(n) 이다.

하지만 특정 위치의 데이터를 찾는 작업에서는 시간복잡도가 O(n) 이기 때문에 오히려 배열 보다 비효율 적이다. (배열은 데이터 검색 시 시간복잡도가 O(1) 이다. )

연결 리스트에서 데이터가 추가되는 경우

연결 리스트에서 데이터가 삭제되는 경우

연결 리스트의 종류

연결 리스트에는 대표적으로 3가지 종류가 있다.

1. 단일 연결 리스트

단일 연결 리스트는 각 노드에 데이터와 다음 노드를 가리키는 포인터가 담겨있다.

가장 단순한 형태의 연결 리스트다.

2. 이중 연결 리스트

이중 연결 리스트는 각 노드에 데이터와 이전 노드와 다음 노드의 포인터가 담겨있다.

단일 연결 리스트에서는 각 노드가 다음 노드는 알고 있으나 이전 노드를 알지 못해 이전 노드로 접근할 수가 없다. 이러한 단점을 보완하기 위해 이중 연결 리스트가 생겨났다.

3. 원형 연결 리스트

원형 연결 리스트는 단일 연결 리스트에서 마지막 노드와 처음의 노드를 연결시켜 원형 구조로 만든 것이다. 단인 연결 리스트는 임의의 노드 위치에서부터 이전에 위치한 노드에 접근할 수 없기 때문에 원형 구조를 만들어 순환해서 접근할 수 있도록 만든 것이다. 

 배열이란 같은 종류의 데이터들 일렬로 저장하는 자료구조이다. 

배열에 저장된 각 데이터들은 번호(index)를 가지고 있다.

하지만 이러한 배열만으로는 비효율적이거나 한계가 있는 작업이 있기 때문에 동적배열이나 연결 리스트 등과 같은

자료 구조를 만들어 사용한다. 

(동적배열이든 연결 리스트든 모두 기본적으로 배열을 이용하여 만들어낸 자료구조이다.)

동적배열(Dynamic Array) 이란?

 동적 배열이란 크기가 고정되지 않은 배열을 의미한다. (이름 그대로 단순하다!)

보통 우리가 흔히 말하는 배열은 동적(Dynamic)의 반대인 정적(Static) 즉, 정적배열을 의미한다. 정적배열은 크기가 고정되어 있어 데이터를 크기 만큼만 저장할 수 있다.

대표적으로 C++ 의 vector 나 자바의의 ArrayList 등이 있다.

동적배열이 필요한 이유

 동적배열은 이름에서 나타나듯이 배열의 크기를 동적으로 늘려서 사용하고 싶을 때 필요하다. (이유도 단순하다!)

배열은 크기가 고정해야 되기 때문에 이를 해결하기 위해 동적배열이 고안된 것이다.

처음부터 자신이 사용할 배열의 크기를 알면 좋겠지만 크기를 너무 크게 잡으면 메모리가 낭비되고, 그렇다고 크기를 작게 잡으면 매번 배열을 새로 만들어서 기존의 배열을 옮겨 담아야 해서 번거롭다.

동적배열의 시간복잡도

1. 특정 위치의 데이터를 반환하거나 변경하는 작업을 시간복잡도 O(1) 에 처리할 수 있다. 

(배열과 공통)

동적배열은 배열을 이용하여 구현되어 있기 때문에 데이터들이 메모리의 연속된 위치에 저장되어 있고, 각 데이터들은 번호(Index)를 가지고 있다. 그래서 특정 위치의 데이터를 호출하거나 변경하는 O(1)에 처리할 수 있다.