Today I Learned🧤

선형 자료 구조란 요소가 일렬로 나열되어 있는 자료 구조를 말한다. 연결 리스트 연결 리스트는 데이터를 감싼 노드를 포인터로 연결해서 공간적인 효율성을 극대화시킨 자료 구조이다. 삽입과 삭제가 O(1)이 걸리며, 탐색에는 O(n)이 걸린다. 위 그림과 같이 prev 포인터와 next 포인터로 앞 뒤의 노드를 연결시킨 것이 연결 리스트이다. 참고로, 맨 앞에 있는 노드를 head라 한다. 싱글 연결 리스트 : next 포인터만 가지며, 한쪽 방향으로만 이동이 가능하다. 이중 연결 리스트 : next 포인터와 prev 포인터를 가지며, 양방향으로 이동이 가능하다. 원형 이중 연결 리스트 : 이중 연결리스트와 동일하지만, 마지막의 노드의 next 헤더가 head 노드를 가리킨다. 배열 배열은 같은 타입의 변수..

자료구조는 효율적으로 데이터를 관리하고 수정, 삭제, 탐색, 저장할 수 있는 데이터 집합을 의미한다. 복잡도 복잡도는 시간 복잡도와 공간 복잡도로 나뉜다. 시간 복잡도(time complexity) 시간 복잡도란 '문제를 해결하는 데 걸리는 시간과 입력의 함수 관계'를 가리킨다. 어떤 알고리즘의 로직이 '얼마나 오래' 걸리는지를 나타내는 데 쓰이며, 보통 빅오 표기법으로 나타낸다. 예를 들어, 입력 크기 n에 대한 알고리즘에 필요한 시간이 10n^2+n이라고 하면 빅오 표기법으로는 O(n^2)가 된다. '가장 영향을 많이 끼치는 항'의 상수 인자를 빼고 나머지 항을 없애서 표현한 것이다. 다른 항들도 신경 쓰일 수 있지만 증가 속도를 고려한다면 입력 크기가 커질수록 연산량이 가장 많이 커지는 항은 n의 ..

https://1eehyunji.tistory.com/entry/%EB%8D%B0%EC%9D%B4%ED%84%B0%EB%B2%A0%EC%9D%B4%EC%8A%A4-%EC%A1%B0%EC%9D%B8Join [데이터베이스] 조인(Join) 조인(Join)이란 하나의 테이블이 아닌 두 개 이상의 테이블을 묶어서 하나의 결과물을 만드는 것을 말한다. MySQL에서는 JOIN이라는 쿼리로, MongoDB에서는 lookup이라는 쿼리로 이를 처리할 수 있다. ( 1eehyunji.tistory.com 위 게시글에서 설명한 조인은 조인의 원리를 기반으로 작업이 이루어진다. 조인의 원리인 중첩 루프 조인, 정렬 병합 조인, 해시 조인에 대해 알아보자! 중첩 루프 조인(NLJ, Nested Loop Join) 중첩 루프..

조인(Join)이란 하나의 테이블이 아닌 두 개 이상의 테이블을 묶어서 하나의 결과물을 만드는 것을 말한다. MySQL에서는 JOIN이라는 쿼리로, MongoDB에서는 lookup이라는 쿼리로 이를 처리할 수 있다. (단, MongoDB를 사용할 때, lookup은 되도록 사용하지 않아야 한다. 이는 관계형 데이터베이스의 JOIN 연산에 비해 성능이 떨어진다고 알려져 있다.) 조인의 종류 조인의 종류 중 대표적으로 내부 조인, 왼쪽 조인, 오른쪽 조인, 합집합 조인을 살펴보자! 아래 그림처럼 두 테이블간의 교집합이 있다고 할 때, 다음과 같은 네 가지 조인이 있다. 내부 조인(Inner join) 왼쪽 테이블과 오른쪽 테이블의 두 행이 모두 일치하는 행이 있는 부분만 표기한다. 즉, 두 테이블 간의 교집..

인덱스는 데이터를 빠르게 찾을 수 있는 하나의 장치이다. B-트리 인덱스는 보통 B-트리라는 자료 구조로 이루어져 있다. 이는 루트 노드, 리프 노드, 브랜치 노드로 나뉜다. 예를 들어 설명하자면 다음 그림과 같다. 키가 "57"인 데이터를 검색하는 과정이라고 가정하자. 트리 탐색은 맨 위 루트 노드부터 탐색이 일어나며, 브랜치 노드를 거쳐 리프 노드까지 내려온다. 각 노드의 시작부터 57보다 크거나 같은 수를 만날 때까지 정렬된 값을 기반으로 탐색한다. 즉, 루트 노드의 경우 39,83을 거치고, 그 밑의 브랜치 노드로 내려와서 46,53,57을 거치고, 그 밑의 리프 노드로 내려와서 55,57을 거쳐 원하는 데이터를 찾는다. 루트 노드에서 시작해서 리프 노드까지 도달해서 찾은 57을 가리키는 데이터 ..

관계형 데이터베이스(RDBMS) 관계형 데이터베이스는 행과 열을 가지는 표 형식 데이터를 저장하는 형태의 데이터베이스를 가리키며, SQL 언어를 사용해서 조작한다. MySQL, PostgreSQL, 오라클, SQLserver, MSSQL 등이 있다. 관계형 데이터베이스의 경우, 표준 SQL을 지키기는 하지만, 각 제품에 따라 특화시킨 SQL을 사용해서 문법이 조금씩 다를 수 있다. 이렇게 특화시킨 SQL을 오라클의 경우 PL/SQL, SQLserver의 경우 T-SQL, MySQL은 SQL이라 부른다. MySQL MySQL은 대부분의 운영체제와 호환되며 현재 가장 많이 사용하는 데이터베이스이다. C,C++로 만들어졌으며, MyISAM 인덱스 압축 기술, B-트리 기반으 인덱스, 스레드 기반의 메모리 할당..

트랜잭션은 데이터베이스에서 하나의 논리적 기능을 수행하기 위한 작업의 단위를 말한다. 데이터베이스에 접근하는 방법은 '쿼리'이므로, 여러 개의 쿼리를 하나로 묶는 단위를 의미한다. 트랜잭션에 대한 특징은 원자성(Atomicity), 일관성(Consistency), 격리성(Isolation), 지속성(Durability)이 있으며 이를 약자로 ACID 특성이라고 부른다. 원자성(Atomicity) 원자성은 트랜잭션과 관련된 모든 일이 수행되었거나, 수행되지 않았음을 보장하는 특징이다. 트랜잭션을 커밋했는데 문제가 발생하여 롤백하는 경우 그 이후에 모두 수행되지 않음을 보장하는 것을 말한다. 예를 들어, 1000만원을 가진 홍철이가 0원을 가진 규영이에게 500만원을 이체한다면, 홍철이는 500만원, 규영이..

데이터 이상 현상 삽입 이상(Insertion Anomaly) 특정 데이터가 존재하지 않아 다른 데이터를 데이터베이스에 삽입할 수 없는 경우 발생한다. 예를 들어, 대학교 테이블에 (학번, 학생명, 학과명, 학과코드) 컬럼이 존재하고, 학번이 기본키인 경우, 새로운 학과인 '수학과'를 데이터베이스에 삽입하려고 할 때, 해당 학과인 학생의 정보가 없어서 학번이 NULL이 되는데, 학번은 기본키이므로 NULL 값을 가질 수가 없다. 따라서 새로운 학과인 '수학과'의 데이터를 데이터베이스에 삽입할 수 없는 상황이 발생한다. 학번 학생명 학과명 학과 코드 2018111111 홍길동 통계학과 001 2018222222 임꺽정 전자공학과 002 2018333333 이현지 컴퓨터공학과 003 수학과 004 마지막 행..

ERD는 데이터베이스를 구축할 때 가장 기초적인 뼈대 역할을 하며, 릴레이션 간의 관계를 정의한 것이다. 만약 서비스를 구축한다면 가장 먼저 신경써야 할 부분이다. ERD의 중요성 ERD는 시스템의 요구 사항을 기반으로 작성되며, 이 ERD를 기반으로 데이터베이스를 구축한다. 데이터베이스를 구축한 이후에도 디버깅 또는 비즈니스 프로세스 재설계가 필요한 경우에 설계도 역할을 담당하기도 한다. 하지만, ERD는 관계형 구조로 표현할 수 있는 데이터를 구성하는 데 유용할 수 있지만 비정형 데이터를 충분히 표현할 수 없다는 단점이 있다. * 비정형 데이터 : 비구조화 데이터를 말하며, 미리 정의된 데이터 모델이 없거나 미리 정의된 방식으로 정리되지 않은 정보를 말한다. 예제로 배우는 ERD 다음 예제의 서비스 ..

관계(relationship) 데이터베이스에 테이블은 하나만 있는 것이 아니고, 여러 개의 테이블이 있기 때문에 이러한 테이블들은 서로의 관계가 정의되어 있다. 이러한 관계를 다음과 같이 관계 화살표로 나타낸다. 1:1 관계 하나의 레코드가 다른 테이블의 레코드 한 개와 연결된 경우이다. 예를 들어, '유저' 테이블의 '이름'은 외래키로, '유저 이메일' 테이블의 '이름'과 연결되어 있다. 각 이메일이 단 한 명의 유저와 연결되어 있고, 그 반대도 동일하다면 유저 테이블과 유저 이메일 테이블은 1:1 관계이다. 하지만, 이러한 1:1 관계는 잘 사용하지 않는다. 왜냐하면 이러한 경우 유저 테이블에 이메일 컬럼을 추가해서 직접 저장하는 것이 나을 수 있기 때문이다. 그래도 1:1 관계를 사용한다면, 테이블..