CodeDrive

문제:

입력:

출력:

풀이 방법:

관계 데이터 모델에서 지원하는 언어에는 크게 두 가지가 있다.

1. 관계 해석 - 원하는 데이터만 명시하고 질의를 어떻게 수행할 것인가는 명시하지 않는 선언적인 언어

2. 관계 대수 - 어떻게 질의를 수행할 것인가를 명시하는 절차적 언어, SQL의 이론적인 기초

관계 대수

기존의 릴레이션들로부터 새로운 릴레이션을 생성한다. 즉 입력값, 출력 값이 모두 릴레이션이다.

연산자들을 적용하여 보다 복잡한 관계 대수식을 점차적으로 만들 수 있음. 기본적인 연산자들의 집합으로 이루어짐.

결과 릴레이션은 또 다른 관계 연산자의 입력으로 사용될 수 있다.

실렉션 연산자

σ<실렉션 조건>(릴레이션) 과 같이 사용하며 한 릴레이션에서 조건을 만족하는 투플들의 부분 집합을 생성한다.

단항 연산자이며 결과 릴레이션의 차수는 항상 입력 릴레이션의 차수와 같으며 카디날리티는 결과가 항상 작거나 같다.

프로젝션 연산자

π<애트리뷰트 리스트>(릴레이션) 과 같이 사용하며 한 릴레이션의 애트리뷰트들의 부분 집합을 구한다.

결과 릴레이션은 애트리뷰트 리스트에 명시된 애트리뷰트들만 가진다. 실렉션의 결과로는 중복 투플이 존재할 수 있지만 프로젝션의 결과에는 중복된 투플이 존재하지 않음

집합 연산자

릴레이션이 투플들의 집합이기 때문에 기존의 집합 연산이 릴레이션에 적용된다. 집합 연산자에는 합집합, 교집합, 차집합이 있다. 집합 연산자의 입력으로 사용되는 두 개의 릴레이션은 합집합 호환이어야 한다.

*합집합 호환

두 릴레이션 R1(A1, A2,..., An)과 R2(B1, B2,... , Bm)이 합집합 호환일 필요충분조건은 n=m이고, 모든 1 <=i <=n에 대해 domain(Ai)=domain(Bi)이다.

합집합 연산자

릴레이션 1 ∪ 릴레이션 2와 같이 사용하며 릴레이션1에 있거나, 릴레이션2에 있는 투플들로 이루어진 릴레이션을 반환

결과 릴레이션에서는 중복된 투플들은 제거한다.

교집합 연산자

릴레이션1 ∩ 릴레이션2 와 같이 사용하며 릴레이션 1, 릴레이션 2에 동시에 속하는 투플들로 이루어진 릴레이션

차집합 연산자

릴레이션 R, S에 대해 차집합 R-S는 R에는 속하지만 S에는 속하지 않은 투플들로 이루어진 릴레이션

문제:

입력:

출력:

풀이 방법:

문제:

이렇게 A->C->B의 순서로 처리하면 각 작업의 요청부터 종료까지 걸린 시간의 평균은 9ms(=(3+7+17)/3)가 됩니다.

각 작업에 대해 [작업이 요청되는 시점, 작업의 소요시간]을 담은 2차원 배열 jobs가 매개변수로 주어질 때, 작업의 요청부터 종료까지 걸린 시간의 평균을 가장 줄이는 방법으로 처리하면 평균이 얼마나 되는지 return 하도록 solution 함수를 작성해주세요. (단, 소주점 이하의 수는 버립니다)

풀이 방법:

문제:

입력:

출력:

풀이 방법:

문제:

문제:

입력:

출력:

풀이 방법:

데이터 무결성

데이터의 정확성 또는 유효성을 의미한다. 일관된 데이터베이스 상태를 정의하는 규칙들을 묵시적, 명시적으로 정의한다. 데이터베이스가 갱신될 때마다 자동적으로 검사하므로 따로 검사할 필요가 없다.

도메인 제약조건

애트리뷰트 값이 반드시 원자값이어야 한다. 데이터 형식을 통해 값들의 유형을 제한하고, check 제약 조건을 통해 값들의 범위를 제한할 수 있음

키 제약조건

키 애트리뷰트에 중복된 값이 존재해서는 안된다는 것이다.

엔티티 무결성 제약조건

기본 키가 각 투플들을 식별하기 위해 사용되기 때문에 릴레이션의 기본 키를 구성하는 어떤 애트리뷰트도 널값을 가질 수 없다는 제약조건이다. 단 대체 키에는 적용되지 않는다.

참조 무결성 제약조건

참조 무결성 제약조건은 두 릴레이션의 연관된 투플들 사이의 일관성을 유지하는 데 사용된다. 릴레이션 R2의 외래 키가 릴레이션 R1의 기본 키를 참조할 때 참조 무결성 제약조건은 아래의 두 조건 중 하나가 성립되면 만족된다.

1. 외래 키의 값은 R1의 어떤 투플의 기본 키 값과 같음.

2. 널 값을 가진다.(외래 키가 자신의 릴레이션에서 기본키가 아니다.)

데이터베이스를 갱신할 때마다 무결성 제약조건을 유지시켜줘야 한다. 데이터베이스에 대한 갱신 연산은 삽입, 삭제, 변경 연산으로 구분하는데 DBMS는 각 갱신, 연산마다 필요한 조치를 취한다.

삽입

새로 삽입되는 투플의 기본 키 애트리뷰트의 값에 따라 도메인 제약조건, 키 제약조건, 엔티티 무결성 제약조건을 위배할 수 있다. 참조되는 릴레이션에 새로운 투플이 삽입되면 참조 무결성 제약조건은 위배되지 않으나, 참조하는 릴레이션에 삽입될 경우에는 위배될 수 있다.

삭제

참조하는 릴레이션에서 투플이 삭제되면 도메인 제약조건, 키 제약조건, 엔티티 무결성 제약조건, 참조 무결성 제약조건을 위배하지 않는다. 하지만 참조되는 릴레이션에서 투플이 삭제된다면 참조 무결성 제약조건을 위배하는 경우가 생긴다.

수정

DBMS는 수정하는 애트리뷰트가 기본 키인지 외래 키인지 검사한다. 수정하려는 애트리뷰트가 둘 다 아니면 참조 무결성 제약조건을 위배하지 않는다. 기본 키나 외래 키를 수정하는 것은 삽입이나 삭제를 하는 것과 같으므로 동일하게 적용된다.

참조 무결성 제약조건을 만족시키기 위한 DBMS가 제공하는 옵션

제한(restricted)

위배를 야기한 연산을 단순히 거절한다.

연쇄(cascade)

참조되는 릴레이션에서 투플을 삭제하고, 참조하는 릴레이션에서 이 투플을 참조하는 투플들도 함께 삭제해버린다.

널값(nullify)

참조되는 릴레이션에서 투플을 삭제하고, 참조하는 릴레이션에서 이 투플을 참조하는 투플들의 외래 키에 널값을 삽입한다.

디폴트 값

널값을 넣는 대신에 디폴트 값을 넣는다.

문제:

입력:

출력:

풀이 방법:

문제:

입력:

첫째 줄에 포도주 잔의 개수 n이 주어진다. (1<=n<=10,000) 둘째 줄부터 n+1번째 줄까지 포도주 잔에 들어있는 포도주의 양이 순서대로 주어진다. 포도주의 양은 1,000 이하의 음이 아닌 정수이다.

출력:

첫째 줄에 최대로 마실 수 있는 포도주의 양을 출력한다.

풀이 방법:

 동적계획법을 사용해서 최댓값을 찾아내야 한다. 일단 크게 두 가지 경우로 나눌 수 있다. 3이상 n 이하의 수 i에 대해서 i를 선택하는 경우와 선택하지 않는 경우이다.

i) i번째 값을 선택하고자 할 때

i번째 값을 선택하고자 하면 다시 두 개의 경우로 나눌 수 있다.

0x00   ,    ?0x0

전자는 i번째와 i번째를 연속해서 고르는 경우, 후자는 그렇지 않은 경우이다. 전자의 경우에는 i번째와 i번째를 더하고 거기에 dp[i-3]번째 값을 더하고, 후자의 경우에는 i번째 값에 dp[i-2]를 더하는 경우이다. 

ii) i번째 값을 선택하지 않을 때

위 경우를 먼저 계산해준 후 dp[i-1] 과 dp[i] 중 최댓값을 선택하면 된다.