솧로그

B-Tree 인덱스 B-Tree 인덱스에 대해 알기 전에 먼저 B-Tree 자료구조에 대해 알아보자. B-Tree는 자식을 2개만 갖는 이진 트리를 확장하여 N개의 자식을 갖는다. 그리고 좌우 자식 간의 균형이 맞지 않을 경우 비효율적이기 때문에 항상 균형을 맞춘다는 의미에서 균형 트리(Balanced Tree) 라고 한다. 즉, B-Tree의 B는 Binary(이진)의 약자가 아니라 Balanced(균형)의 약자이다. B-Tree는 데이터베이스의 인덱싱 알고리즘 중 가장 일반적으로 사용되고, 가장 먼저 도입된 알고리즘이다. B-Tree는 칼럼의 원래 값을 변형시키지 않으며 항상 정렬된 상태로 유지한다. 전문 검색과 같은 특수한 요건이 아닌 경우 대부분의 인덱스는 거의 B-Tree를 사용할 정도로 일반적..

디스크 읽기 방식 컴퓨터의 CPU나 메모리처럼 전기적 특성을 띤 장치의 성능은 짧은 시간 동안 매우 빠른 속도로 발전했지만, 디스크 같은 기계식 장치의 성능을 상당히 제한적으로 발전했다. 비록 최근에는 자기 디스크 원판에 의존하는 HDD(하드 디스크 드라이브)보다 SSD가 많이 활용되고 있지만, 여전히 데이터 저장 매체는 컴퓨터에서 가장 느린 부분이다. 따라서 데이터베이스의 성능 튜닝은 어떻게 디스크 I/O를 줄이느냐가 관건일 때가 상당히 많다. 하드 디스크 드라이브(HDD)와 솔리드 스테이트 드라이브(SSD) 컴퓨터에서 CPU나 메모리 같은 주요 장치는 대부분 전자식 장치이지만 하드 디스크 드라이브(HDD)는 기계식 장치이다. 따라서 데이터베이스 서버에서 항상 디스크 장치가 병목이 된다. 이러한 기계식..

SQL SQL은 Structed Query Language의 약자로 데이터 관리 시스템인 DBMS에서 데이터를 조작하고 조회하기 위해 사용하는 언어이다. DBMS의 종류는 다양한데 이러한 DBMS 벤더들이 각자의 언어와 문법만 고집한다면 사용자들은 DBMS 사용이 어려워진다. 따라서 ANSI는 표준이 되는 SQL을 만들었고 이를 ANSI SQL이라 부른다. 이 ANSI SQL은 현대의 대부분의 DBMS에서 작동한다. 따라서 학습 시간을 줄여주고 벤더 변경시 변경 비용이 적다는 장점이 있다. SQL을 프로그래밍 언어와 비교하면, SQL은 데이터베이스 관리를 위한 언어이며 데이터 조작을 위한 목적으로 사용되지만, C언어 같은 프로그래밍 언어는 다양한 프로그래밍 영역에서 사용되는 일반 목적의 프로그래밍 언어이..

https://school.programmers.co.kr/learn/courses/30/lessons/42627# 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 모든 작업들의 평균 작업시간을 작게 만들어야 하는 문제이다. 운영체제에서 CPU 스케줄링에서 배운 최단작업 우선 스케줄링 기법(SJF)이 생각났는데, 그대로 하면 된다! 아이디어를 떠올리는 건 괜찮았는데, 구현이 어려웠고 자꾸 8번과 18번 테스트 케이스에서 실패해서 고생한 문제이다. 주요 포인트는 다음과 같다. 현재 시간까지 들어온 작업들을 큐에 넣는다. 그런데 이때 매개변수로 주어지는 job..

파일시스템과 데이터베이스의 비교 과거에는 데이터 관리를 위해 파일 시스템을 사용했다. 파일 시스템은 데이터를 프로그램과 분리하여 별도의 파일에 저장하는 방법이다. 파일은 프로그램과 분리되어 컴퓨터의 디스크에 저장되며, 컴퓨터가 꺼진 상태에도 여전히 디스크에 데이터를 유지한다. 그리고 파일 시스템은 응용 프로그램마다 별도의 파일로 관리한다. 따라서 각 프로그램들은 파일을 다뤄야 하는 부담이 생기고, 각 파일별로 저장된 데이터를 공유하지 않기 때문에 데이터의 중복이 발생한다. 그리고 이로 인해 데이터 일관성의 문제가 발생할 수 있다. 반면 DBMS의 경우 데이터 정의 및 관리를 DBMS에게 맡기기 때문에 프로그램 자체가 훨씬 간단하다. 그리고 여러 프로그램에서 하나의 데이터베이스를 공유할 수 있기 때문에 데..

https://school.programmers.co.kr/learn/courses/30/lessons/43164 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 이동 가능한 모든 경로 중 알파벳 순서가 앞서는 경로를 return하면 된다. 그리고 모든 항공권을 사용해야 한다. 따라서 dfs를 사용했다. 그리고 dfs 중간에 usedTicket[i] = false로 초기화해줘야 한다. 예를 들어 JFK를 먼저 방문했으면 그 다음 경로에서는 JFK를 방문하지 못하도록 방문처리를 해줬지만, 다른 공항을 먼저 방문한 후의 경로에서는 JFK를 방문할 수 있어야 하..

디스크는 컴퓨터 시스템의 대표적인 2차 저장장치이다. 메모리는 휘발성 저장장치이므로 전원이 나가면 그 내용이 모두 사라진다. 따라서 컴퓨터에서 수행한 작업의 결과를 영구적으로 보관하기 위해서는 디스크 같은 2차 저장장치를 이용해야 한다. 디스크의 구조 논리블록: 디스크 외부에서는 디스크를 일정한 크기의 저장공간들로 이루어진 1차원 배열처럼 취급하게 된다. 그리고 이때 이 일정한 크기의 저장공간을 논리블록이라고 한다. 디스크에 데이터가 저장될 때 논리블록 단위로 저장되고, 디스크 외부로 입출력이 일어날 때도 논리블록 단위로 전송된다. 섹터: 각 논리블록이 저장되는 디스크 내의 물리적 위치이다. 디스크 컨트롤러가 논리블록을 디스크 내의 섹터 번호로 매핑하는 역할을 담당한다. 즉, 해당 논리블록이 저장된 물리..

https://www.acmicpc.net/problem/1082 1082번: 방 번호 첫째 줄에 N이 주아진다. 둘째 줄에는 공백으로 구분된 P0, ..., PN-1이 주어진다. 마지막 줄에는 M이 주어진다. www.acmicpc.net 그리디 문제로, 주요 포인트는 다음과 같다. 가격이 싼 숫자를 우선으로 골라야 많은 숫자를 구매할 수 있어서 자릿수가 길어진다! 그런데 가격이 가장 싼 숫자가 0(인덱스가 0)이라면, 맨 앞자리 수가 0이 되어 자릿수랑 무관하게 큰 숫자가 될 수 없다. 따라서 가격이 가장 싼 숫자가 0이라면, 그 다음으로 싼 숫자를 제일 앞에 두고, 나머지 자릿수는 가장 싼 숫자를 둔다. 반면 가격이 가장 싼 숫자가 0이 아니라면, 해당 숫자를 최대한 많이 고른다. 위 과정으로 최대한..

https://www.acmicpc.net/problem/1034 1034번: 램프 첫째 줄에 N과 M이 주어진다. N은 행의 개수이고, M은 열의 개수이다. N과 M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 램프의 상태가 주어진다. 1이 켜져있는 상태이고, 0이 꺼져 www.acmicpc.net 처음에는 완전 탐색으로 m개의 열 중 k번 스위치를 눌러 켜진 행의 갯수를 구하려고 했다. 그런데 이렇게 하면 m개의 열 중 중복을 허용하여 k개를 고르는 것이기 때문에 m^k (50 ^ 1000)으로 시간초과가 날 것이다. 주요 포인트는 다음과 같다. 행 단위로 생각해보자. 하나의 행을 모두 1로 만들어야 켜진 행이 된다. (1) 만약 하나의 행에 0의 갯수가 k보다 크면, 그 행은 절대..

RDB 사전에 정의된 스키마 RDB는 사전에 스키마를 정의하고 정의된 스키마에 맞춰서 데이터를 저장하기 때문에 명확한 데이터 구조를 보장한다. 그러나 이러한 특성으로 인해 확장성이 부족하다. 만약 스키마에 새로운 컬럼을 추가하려고 하는데 이미 테이블에 수많은 데이터가 존재한다면, 칼럼을 추가하는 작업은 부담스러울 수 있다. 데이터 중복 RDB의 기본 철학은 데이터의 중복을 허용하지 않는다. 따라서 데이터 중복을 제거하기 위해 정규화를 진행한다. 그러나 이로 인해 통합된 데이터를 읽어오기 위해 여러 테이블을 조인하는 작업이 일어나고 이로 인해 조회 성능이 하락한다. 스케일 아웃 RDB는 스케일 아웃에 유연한 DB가 아니다. 따라서 성능 향상을 위해 스케일 업을 진행하며 이로 인해 비용이 늘어날 수 있다. ..