Goyummy

'면접을 위한 CS 전공지식 노트' 책을 보며 공부한 내용입니다.그래프정점과 간선으로 이루어진 자료 구조간선(edge), 정점(vertex)단방향 간선이 있고, 양방향 간선이 있다.정점에서 나가는 간선을 해당 정점의 outdegree, 들어오는 간선을 indegree라고 한다.정점은 약자로 V나 U라고 하며, 어떤 정점으로부터 시작해서 어떤 정점까지 간다는 것을 "U에서 V로 간다"라고 한다. 가중치: 간선과 정점 사이에 드는 비용트리그래프 중 하나로 그래프의 특징처럼 정점과 간선으로 이루어져 있지만, 트리 구조로 배열된 계층적 데이터의 집합이다. 루트 노드, 내부 노드, 리프 노드 등으로 구성된다.참고로, 트리로 이루어진 집합을 숲이라고 한다 .특징부모, 자식 계층 구조V = E - 1임의의 두 노드 ..

'면접을 위한 CS 전공지식 노트' 책을 보며 공부한 내용입니다. 연결 리스트데이터를 감싼 노드를 포인터로 연결해서 공간적인 효율성을 극대화한 것이다.prev와 next로 연결한다.싱글 연결 리스트: next만 사용이중 연결 리스트: prev와 next 사용원형 이중 연결 리스트: prev와 next를 사용하고, 마지막 노드의 next는 첫 노드를 가리킨다.삽입과 삭제는 O(1), 탐색은 O(n)배열같은 타입의 변수들로 이루어져 있다. 크기가 정해져 있고, 인접한 메모리 위치에 있는 데이터들을 모아놓은 집합이다.중복을 허용하고, 순서가 있다.접근(참조)에 O(1)이고 랜덤 접근이 가능하다. 삽입과 삭제는 O(n)랜덤 접근직접 접근동일한 시간에 배열과 같은 순차적인 데이터가 있을 때, 임의의 인덱스에 해당..

'면접을 위한 CS 전공지식 노트' 책을 보며 공부한 내용입니다. 빅오 표기법시간 복잡도입력 크기에 대해 어떠한 알고리즘이 실행되는데 걸리는 시간주요 로직의 반복 횟수에 중점을 둠보통 빅오 표기법으로 나타낸다.for (int i = 0; i => 10n^2 + n => O(n^2)가장 영향을 많이 끼치는 상수 인자를 빼고 나머지 항을 없앤 것.   시간 복잡도가 필요한 이유 효율적인 코드로 개선하는데 쓰이는 척도가 된다.  공간 복잡도프로그램을 실행시켰을 때 필요로 하는 자원 공간의 양정적 변수로 선언된 것 말고도 동적으로 재귀적인 함수로 인해 공간을 계속해서 필요로 할 경우도 포함한다. int a[1004];이면 int의 크기는 4byte이므로 1004 * 4 btye만큼의 공간이 필요하다.  자료 구..

'면접을 위한 CS 전공지식 노트' 책을 보며 공부한 내용입니다. 조인은 조인의 원리를 기반으로 조인 작업이 이루어진다.조인의 원리는 중첩 루프 조인, 정렬 병합 조인, 해시 조인이 있다. 중첩 루프 조인중첩 for문과 같은 원리로 조건에 맞는 조인을 하는 방법이다.랜덤 접근에 대한 비용이 많이 증가해서 대용량의 테이블에서는 사용하지 않는다. (디스크 접근 문제)예시t1, t2 테이블을 조인한다라고 했을 대, t1 테이블에서 한번에 하나의 행을 가져와서 읽고, t2 테이블에서도 한번에 하나의 행을 가져와서 읽어서 조건에 맞는 레코드를 찾아 결과값을 반환한다.중첩 루프 조인에서 발전한 조인할 테이블을 작은 블록으로 나누어서 블록 하나씩 조인하는 블록 중첩 루프 조인도 있다.pseudo codefor eac..

'면접을 위한 CS 전공지식 노트' 책을 보며 공부한 내용입니다. 조인이란 하나의 테이블이 아닌 두 개 이상의 테이블을 묶어서 하나의 결과물을 만드는 것이다. MySQL에서는 JOIN이라는 쿼리로, MongoDB에서는 lookup이라는 쿼리로 이를 처리할 수 있다. (MongoDB를 사용할 때 lookup은 되도록 사용하지 말기. 관계형 데이터베이스에 비해 lookup의 성능이 떨어진다. -> 여러 테이블을 조인하는 작업이 많을 경우에는 MongoDB보다는 관계형 데이터베이스를 써야 한다.) 내부 조인(inner join)왼쪽 테이블과 오른쪽 테이블의 두 행이 모두 일치하는 행이 있는 부분만 표기된다.교집합SELECT * FROM TableA AINNER JOIN TableB B ONA.key = B.k..

'면접을 위한 CS 전공지식 노트' 책을 보며 공부한 내용입니다.인덱스의 필요성인덱스를 통해 빠르게 테이블에 있는 데이터를 찾기 가능하다. B-트리인덱스는 보통 B-트리라는 자료 구조로 이루어져 있다. 이는 루트 노드, 리프 노트, 브랜치 노드로 나뉜다.   인덱스가 효율적인 이유효율적인 단계를 거쳐 모든 요소에 접근할 수 있는 균현 잡힌 트리 구조와 트리 깊이의 대수 확장성 때문이다.대수 확장성트리 깊이가 리프 노드 수에 비해 매우 느리게 성장하는 것.기본적으로 인덱스가 한 깊이 증가할 때마다, 최대 인덱스 항목의 수는 4배씩 증가한다. 트리 깊이인덱스 항목 수364425651024640967163848653369262144101048576실제 인덱스는 이보다 더 효율적이다. 인덱스 만드는 방법DB마다..

'면접을 위한 CS 전공지식 노트' 책을 보며 공부한 내용입니다. 관계형 데이터베이스RDBMS는 행과 열을 가지는 표 형식의 데이터를 저장한다.SQL이라는 언어를 써서 조작한다.예시) MySQL, PostgreSQL, 오라클, SQL Server, MSSQL관계형 데이터베이스의 경우 표준 SQL을 지키기는 하지만, 각각의 제품에 특화된 SQL을 사용한다. 오라클은 PL/SQL, MySQL은 SQLMySQL대부분의 OS와 호환된다. 현재 가장 많이 사용된다쓰레드 기반의 메모리 할당 시스템. 매우 빠른 조인, 최대 64개의 인덱스를 제공한다.대용량 DB를 위해서 설계되어 있고, 롤백, 커밋, 이중 암호 지원 보안 등의 기능을 제공한다.MySQL의 스토리지 엔진 아키텍쳐 DB의 심장과도 같은 역할을 하는게 스..

'면접을 위한 CS 전공지식 노트' 책을 보며 공부한 내용입니다.트랜잭션데이터베이스에서 하나의 논리적인 기능을 수행하기 위한 작업의 단위 => 데이터베이스에서 접근 방법은 쿼리 => 여러개의 쿼리들을 하나로 묶는 단위이에 대한 특징은 원자성, 일관성, 독립성, 지속성이 있다. 이를 한꺼번에 ACID라고 한다. 원자성(atomicity)트랜잭션과 관련된 일이 모두 수행되었거나 되지 않았거나를 보장ex) 트랜잭션을 커밋했는데, 문제가 발생하여 롤백하는 경우. 그 이후에 모두 수행되지 않음을 보장하는 것.트랜잭션 단위로 여러 로직들을 묶을 때 외부 API 호출이 있으면 안된다. 만약 있다면, 롤백이 일어났을 때 어떻게 할 것인지에 대한 해결 방법이 있어야 하고, 트랜잭션 전파를 신경써서 관리해야 한다.커밋과 ..

'면접을 위한 CS 전공지식 노트' 책을 보며 공부한 내용입니다. ERD(Entity Relationship Diagram)은 DB를 구축할 때 가장 기초적인 뼈대 역할을 하며 릴레이션 간의 관계들을 정의한 것이다. 서비스를 구축할 때 가장 먼저 신경써야할 부분이다. ERD의 중요성ERD는 시스템의 요구사항을 기반으로 작성되며 이 ERDㄹ르 기반으로 DB를 구축한다. DB를 구축한 이후에도 디버깅 또는 비즈니스 프로세스 재설계가 필요한 경우에도 설계도 역할을 담당한다. 하지만, ERD는 관계형 구조로 표현할 수 있는 데이터를 구성하는데 유용할 수 있지만, 비정형 데이터를 충분히 표현하지 못한다. (비정형 데이터:  비구조화 데이터. 미리 정의된 데이터 모델이 없거나 미리 정의된 방식으로 정리되지 않은 정..

'면접을 위한 CS 전공지식 노트' 책을 보며 공부한 내용입니다. 데이터베이스는 일정한 규칙 혹은 규약을 통해 구조화되어 저장되는 데이터의 모음이다. 데이터베이스를 제어, 관리하는 통합 시스템을 DBMS(DataBase Management System)이라 한다.특정 DBMS마다 정의된 쿼리 언어를 통해 삽입, 삭제, 수정, 조회 등을 수행할 수 있다. 또한, 데이터베이스는 실시간 접근과 동시 공유가 가능하다. 데이터베이스 위에 DBMS가 있고 그 위에 응용 프로그램이 있다.ex) MySQL이라는 DBMS가 있고, 그 위에 응용 프로그램에 속하는 Node.js나 php에서 MySQL의 DB의 데이터를 가져와 해당 데이터 관련 로직을 구축할 수 있다. 엔티티(Entity)사람, 장소, 물건 등 여러 개의 ..