SQL 데이터베이스 시스템에서 자료를 처리하는 용도로 사용되는 언어. 목적에 따라서 DDL(데이터 정의어 - 테이블이나 관계 생성), DML(데이터 조작어 - 테이블의 데이터 CRUD), DCL(데이터 제어어 - 데이터의 사용 권한 관리)로 구분된다. DML (데이터 조작어) 테이블에 데이터를 검색/삽입/수정/삭제하는데 사용되며, select, insert, delete, update문 등이 있다. - SELECT : 테이블에 데이터를 검색하여 출력하는 목적으로 사용되는 쿼리문. 1. ALL | DISTINCT : ALL은 중복허용을 의미하고 (default값), DISTINCT는 중복을 제거하고 집계하는 것을 의미한다. ex) select distinct * from Book; 2. WHERE 절에는 ..
키 키: 특정 튜플을 식별할 때 사용하는 속성(의 집합) 슈퍼키: 유일성을 가진 속성(의 집합) 후보키: 유일성&최소성을 가진 속성(의 집합) 기본키(pk): 후보키 중 대표로 삼는 하나의 키 대리키(pk): DBMS가 임의로 생성하여 사용하는 기본키 외래키(fk): 다른 릴레이션의 기본키를 참조하는 속성 관계대수 1. 셀렉션: 릴레이션에서 조건에 맞는 튜플을 추출하는 연산 2. 프로젝션: 릴레이션의 속성을 추출하기 위한 연산 3. 합집합: 속성이 동일한 두 릴레이션을 합침. 동일튜플 존재시 하나만 표시한다. 4. 교집합: 합병가능한 두 릴레이션이 공통으로 가지고 있는 튜플을 반환 5. 차집합: 첫번째 릴레이션에는 속하고 두번째 릴레이션에는 속하지 않는 튜플을 반환 6. 카티전 프로덕트: 두 릴레이션의 ..
개요다익스트라(Dijkstra) 알고리즘은 BFS와 Dynamic Programming을 활용한 최단경로 검색 알고리즘이다. 다익스트라 알고리즘은 가중치가 존재하는 그래프의 하나의 정점에서 다른 정점들로 가는 최단 경로를 알려준다. 만약에 가중치가 존재하지 않는다면 단순 BFS를 통해서 최단 경로를 구할 수 있지만, 가중치가 존재한다면 Dijkstra를 사용할 수 있다. 다익스트라는 일반적으로 인접 행렬(O(N^2))이나 우선순위 큐(O(ElogV), E:edge, V:vertex)를 사용하여 구현한다. 시작 전에 간단하게 설명하면, 다익스트라 알고리즘은 방문하지 않은 노드들 중에서 시작점으로부터 최소거리를 갖는 노드를 선택하여 노드들의 거리를 갱신하는 것을 반복하는 알고리즘이다. 일단 시작 노..
예전에 풀고 정리했었는데 까먹어서 다시 정리해봄. 분명히 이해하고 넘어갔는데 왜 지금 보니깐 이해가 안되지?? BOJ 12865) 평범한 배낭 물건을 쪼개어 가져갈 수 있는 fraction knapsack문제에서는 무게당 가치(v/w)가 높은 순으로 가져가면 된다. 하지만 위와 같은 0-1 knapsack 문제는 greedy한 방법으로는 풀 수 없다. for(int i = 1; i
실제 데이터가 하드디스크에 저장되는 데이터베이스부터, 데이터 모델과 DBMS까지를 데이터베이스 시스템이라고 부른다. 이러한 데이터베이스 시스템 조작을 위해서 SQL문이 사용된다. 데이터베이스: 데이터가 구조적으로 통합되어 하드디스크에 저장된 형태 데이터베이스 관리 시스템(DBMS): 데이터를 관리하는 소프트웨어 프로그램. 사용자와 db 사이에서 둘을 연결한다. 데이터 모델: 데이터를 저장하는 이론적 방법. 데이터, 연산자, 무결성 제약조건을 요소로 갖는다. 데이터베이스 시스템: DB, DBMS, 데이터 모델로 구성된 시스템 - SQL의 종류 데이터 정의어(테이블 구조 정의): create, alter, ... 데이터 조작어(데이터 조작): select, insert, delete, update, ... ..
//init.c 일부 for(;;){ printf(1, "init: starting sh\n"); pid = fork(); if(pid = 0 && wpid != pid) printf(1, "zombie!\n"); } init.c는 xv6에서 가장 먼저 실행되는 user-level 프로그램이다. make-qemu를 통해서 xv6를 실행하면 init:starting sh라는 메세지와 함께 쉘이 실행된다. init.c에는 무한루프가 존재하고, ..
0. 쉘 명령어(커널명령어) 추가 Makefile의 UPROG와 EXTRA부분에 다음과 같이 추가해준다. 1) UPROG=\ ... _new\ 2) EXTRA=\ umalloc.c new.c\ 1. 파일 추가 README file in Xv6 is a generic file too. Searching for occurrences of README in the MakeFile and adding your required file will be sufficient. Suppose new.txt is the file you want to add. Parts of the MakeFile to be changed are: 1) fs.img: mkfs README new.txt $(UPROGS) ./mkfs fs...
LCS(Longest Common Subsequence, 최장 공통 부분수열) 최장 공통 부분수열이란, 존재하는 두 문자열 사이에 공통으로 존재하는 부분수열 중에 가장 길이가 긴 부분수열을 의미한다. 즉, ACAYKP와 CAPCAK라는 두 문자열이 존재한다면, ACAK(ACAYKP, CAPCAK)가 두 문자열의 LCS가 된다. 부분수열이기 때문에 수열이 연속될 필요는 없다. 수열이 반드시 연속된 문자여야 할 경우 최장 공통 문자열(LCS, Longest Common Substring)이라고 한다. LCS의 풀이는, 먼저 비교 문자열들의 길이에 따라 2차원 배열을 생성한다. 문자열 A("ACAYKP")와 문자열 B("CAPCAK")를 비교하는 상황이라고 하자. LCS[i][j]의 값은 문자열 A의 i번째 ..
트랜잭션 격리 수준이란 트랜잭션끼리 얼마나 고립되었는지를 나타내는 것이다. 트랜잭션 격리 수준이 높아질수록(트랜잭션 레벨이 높아질수록) 트랜잭션간의 고립도가 높아지는 대신 성능이 떨어지게 된다. 트랜잭션 레벨 0: READ UNCOMMITED 트랜잭션 레벨 1: READ COMMITED 트랜잭션 레벨 2: REPEATABLE READ 트랜잭션 레벨 3: SERIALIZABLE 이러한 트랜잭션 격리의 이유는 동시성 제어(Concurrency Control)때문이다. 동시성 제어란 DB 시스템에서 실행되고 있는 여러 개의 트랜잭션이 작업을 성공적으로 마칠 수 있도록 트랜잭션의 실행 순서를 제어하도록 하는 것. 이를 위해서 일부 트랜잭션에 변경이 생기더라도 하나의 트랜잭션이 시작되고 종료되기까지 데이터를 중도..
유클리드 호제법? 두 양의 정수, 혹은 두 다항식의 최대공약수(gcd)를 구하는 방법을 말한다. gcd, lcm관련 문제를 풀 때 거의 필수적으로 사용된다고 느껴질 정도로 많이 사용되는 것 같다. 두 양의 정수 a,b(a>b)에 대하여 a = bq+r (0
리눅스에는 '프로그램'과 그 프로그램이 실행되는 환경인 '프로세스'라는 개념이 있다. 제목으로 써놓은 함수들이 바로 해당 프로세스를 제어하는 함수들이다. 1. fork() #include pid_t fork(void); fork()는 기존 프로세스가 새 프로세스를 생성할 때 사용하는 시스템 호출 함수이다. fork()함수를 사용하여 생성한 프로세스를 자식 프로세스라고 하며, 함수가 호출된 기존 프로세스를 부모 프로세스라고 한다. fork()함수는 한번 호출되나, 호출한 프로세스에 따라 다른 값을 리턴한다. 부모 프로세스에는 새로 생성된 자식 프로세스의 ID를 리턴하고, 자식 프로세스에는 0을 리턴한다. 프로세스 생성에 실패한 경우는 -1을 리턴하고 errno값을 갱신한다. 부모 프로세스는 자식 프로세스의..
개요 OS에서 프로세스가 프로그램을 실행시키기 위해서, 메모리에 접근 (load, save)하는데, OS는 프로그램에 크게 코드, 데이터, 힙, 스택의 4부분으로 분할하여 접근토록 한다. 1. Code(Text) area프로세스가 실행할 코드와 매크로 상수 등의 기계어의 형태로 저장된 공간이다. CPU는 코드영역에 저장된 명령을 가져가서 처리한다. 이 영역은 컴파일 타임에 결정되고 런타임에 수정이 이루어지지 않는다. 2. Data area전역변수 혹은 정적변수 등의 변수들이 저장된 공간이다. 전역변수나 정적변수는 프로그램의 시작과 함께 할당되며, 프로그램 종료시 소멸한다. 3. Heap area힙 영역은 프로그래머가 직접 공간을 할당/해제하는 공간이다. 힙 영역은 메모리의 낮은 주소부터 높은 주소까지..