본문 바로가기

CS

 (22)
[자료구조] 5.1 복잡도 복잡도는 시간 복잡도와 공간 복잡도로 나뉜다. 5.1.1 시간 복잡도 빅오 표기법 시간 복잡도란 문제를 해결하는 데 걸리는 시간과 입력의 함수 관계를 가르킨다. 알고리즘의 로직이 얼마나 오랜 시간이 걸리는지를 나타내는 데 쓰임 시간 복잡도 존재 이유 효율적인 코드 개선을 위한 척도 시간 복잡도의 속도 비교 5.1.2 공간 복잡도 공간 복잡도는 프로그램을 실행시켰을 때 필요로 하는 자원 공간의 양을 말한다. 정적 변수로 선언된 것 말고도 동적으로 재귀적인 함수로 인해 공간을 계속해서 필요로 할 경우도 포함된다. int a[1004]; 1004 *4바이트의 크기를 가짐 5.1.3 자료 구조에서의 시간 복잡도 자료 구조를 쓸 때는 이러한 시간 복잡도를 잘 생각해야한다.
4.7 조인의 원리 조인의 원리인 중첩 루프 조인, 정렬 병합 조인, 해시 조인에 대해 알아보자 앞의 글에서 조인의 종류는 이 원리를 기반으로 조인을 하는 것이다. 4.7.1 중첩 루프 조인 중첩 루프 조인은 중첩 for 문과 같은 원리로 조건에 맞는 조인을 하는 방법이며, 랜덤 접근에 대한 비용이 많이 증가하므로 대용량의 테이블에서는 사용하지 않는다. 예를 들어 "t1, t2 테이블을 조인한다" 라고 하면, 첫 번째 테이블에서 행을 한 번에 하나씩 읽고 그다음 테이블에서도 행을 하나씩 읽어 조건에 맞는 레코드를 찾아 결괏값을 반환 4.7.2 정렬 병합 조인 각각의 테이블을 조인할 필드 기준으로 정렬하고 정렬이 끝난 이후에 조인 작업을 수행하는 조인 조인할 때 쓸 적절한 인덱스가 없고 대용량의 테이블들을 조인하고 조인 조건..
4.6 조인의 종류 조인이란 하나의 테이블이 아닌 두 개 이상의 테이블로 묶어서 하나의 결과물을 만드는 것을 말한다. MySQL에서는 JOIN이라는 쿼리로, MongoDB에서는 lookup이라는 쿼리로 이를 처리할 수 있다. 참고로 MongoDB를 사용할 때 lookup은 되도록 사용하지 말아야한다. (MongoDB는 조인 연산에 대해 관계형 데이터베이스보다 성능이 떨어짐) 조인의 종류 INNER JOIN LEFT OUTER JOIN RIGHT OUTER JOIN FULL OUTER JOIN CROSS JOIN SELF JOIN INNER JOIN 가장 많이 사용하는 조인 두 테이블 간에 교집합을 나타낸다. SELECT table1.col1, table2.col1 FROM table1 JOIN table2 ON table1..
4.5 인덱스 4.5.1 인덱스의 필요성 인덱스는 데이터를 빠르게 찾을 수 있는 하나의 장치 4.5.2 B-트리 인덱스는 보통 B-트리라는 자료 구조로 이루어져 있다. 이는 루트 노드, 리프 노드, 그리고 루트 노드와 리프 노드 사이에 있는 브랜치 노드로 나뉜다. B-트리 설명된 게시글 인덱스가 효율적인 이유와 대수 확장성 인덱스가 효율적인 이유는 효율적인 단계를 거쳐 모든 요소에 접근할 수 있는 균형 잡힌 트리 구조와 트리 깊이의 대수 확장성 때문 대수확장성이란 트리 깊이가 리프 노드 수에 비해 매우 느리게 성장하는 것을 의미 인덱스가 한 깊이씩 증가할 때마다 최대 인덱스 항목의 수는 4배씩 증가 4.5.3 인덱스 만드는 방법 인덱스를 만드는 방법은 데이터베이스마다 다르며 MySQL과 MongoDB를 기준으로 설명한..
4.4 데이터베이스의 종류 4.4.1 관계형 데이터 베이스 관계형 데이터베이스(RDBMS)는 행과 열을 가지는 표 형식 데이터를 저장하는 형태의 데이터베이스를 가르키며 SQL이라는 언어를 써서 조작한다. MySQL, PostgreSQL, 오라클, SQL server, MSSQL 등이 있다. RDBMS의 경우 표준 SQL은 지키기는 하지만 각각의 제품에 특화시킨 SQL을 사용한다. 오라클의 경우 PL/SQL, SQL server는 T-SQL, MySQL은 SQL을 쓴다. MySQL 대부분의 운영체제와 호환되며 가장 많이 사용하는 데이터베이스 C, C++로 만들어졌으며 myISAM 인덱스 압축기술, B-트리 기반의 인덱스, 스레드 기반의 메모리 할당 시스템, 매우 빠른 조인, 최대 64개의 인덱스 제공 대용량 데이터베이스를 위해 설계..
4.3 트랜잭션과 무결성 4.3.1 트랜잭션 트랜잭션은 데이터베이스에서 하나의 논리적 기능을 수행하기 위한 작업의 단위를 말하며 데이터베이스에 접근하는 방법은 쿼리이므로 여러 개의 쿼리들을 하나로 묶는 단위를 말함 원자성, 일관성, 독립성, 지속성이 있으며 한꺼번에 ACID 특징이라 한다. 원자성 원자성은 트랜잭션과 관련된 일이 모두 수행되었거나 되지 않았거나를 보장하는 특징 트랜잭션을 커밋하는데 문제가 발생하여 롤백하는 경우 그 이후에 모두 수행되지 않음을 보장하는 것 ex) 1000만원을 가진 홍철이 0원인 규영이에게 500만원을 보내면 홍철 잔고 조회 홍철에게서 500만원 뺀다. 규영에게 500만원 넣는다. 1~3의 poeration 중 데이터베이스 사용자는 이 세가지의 과정을 볼수도 참여할 수도 없다. 이 과정이 모두 끝..
4.2 ERD와 정규화 과정 ERD는 데이터베이스를 구축할 때 가장 기초적인 뼈대 역할을 하며 릴레이션 간의 관계들을 정의한 것이다. 서비스를 구축한다면 가장 먼저 신경써야 하는 부분이다. 1) ERD의 중요성 ERD는 시스템의 요구 사항을 기반으로 작성되며 이 ERD를 기반으로 데이터베이스를 구축한다. DB를 구축한 이후에도 디버깅 또는 비즈니스 프로세스 재설계가 필요한 경우에 설계도 역할을 담당하기도 한다. 그러나 ERD는 관계형 구조로 표현할 수 있는 데이터를 구성하는 데 유용하지만 비정형 데이터를 충분히 표현할 수 없다는 단점이 있다. 2) 정규화 과정 정규화 과정은 릴레이션 간의 잘못된 종속 관계로 인해 데이터베이스 이상 현상이 일어나서 이를 해결하거나, 저장 공간을 효율적으로 사용하기 위해 릴레이션을 여러 개로 분리하는 ..
4.1 데이터베이스의 기본 데이터베이스는 일정한 규칙, 규약을 통해 구조화되어 저장되는 데이터의 모음이다. 해당 데이터베이스를 제어, 관리하는 통합 시스템을 DBMS라고 하며, 데이터베이스 안에 있는 데이터들은 특정 DBMS마다 정의된 쿼리 언어를 통해 삽입, 삭제, 수정, 조회 등을 수행할 수 있다. 데이터베이스는 실시간 접근과 동시 공유가 가능하다. 데이터베이스 위에 DBMS, 그 위에 응용 프로그램이 있으며 이러한 구조를 기반으로 데이터를 주고 받는다. MySQL이라는 DBMS가 있고 그 위에 응용프로그램에 속하는 Node.js나 php에서 해당 데이터베이스 안에 있는 데이터를 끄집어내 관련 로직을 구축한다. 4.1.1 엔터티 사람, 장소, 물건, 사건, 개념 등 여러 개의 속성을 지닌 명사를 의미 ex) 회원이라는 엔터티가..

티스토리툴바