ER 스키마에서 소유 엔티티 타입 E를 갖는 각 약한 엔티티 타입 W에 대하여 릴레이션 R을 생성한다.
소유 엔티티 타입에 해당하는 릴레이션의 기본 키를 약한 엔티티 타입에 해당하는 릴레이션에 외래 키로 포함시킴
약한 엔티티 타입의 부분 키와 소유 엔티티 타입의 외래 키의 조합으로 기본 키를 구성한다.
단계 2: 약한 엔티티 타입과 단일 값 애트리뷰트
단계 3: 2진 1:1 관계 타입
관계 타입 R에 대하여, R에 참여하는 엔티티 타입에 대응되는 릴레이션 S와 T를 찾음
S와 T 중에서 한 릴레이션을 선택하고, 만일 S를 선택했따면 T의 기본 키를 S의 외래 키로 포함시킨다.
보통 관계 타입에 완전하게 참여하는 릴레이션을 S 릴레이션으로 선택한다. 관계 타입 R이 가지고 있는 단순 애트리뷰트들은 S에 대응되는 릴레이션에 포함시킨다.
두 엔티티 타입이 R에 완전하게 참여할 때는 하나의 릴레이션으로 합치는 방법도 가능하다.
단계 3: 2진 1:1 관계 타입
단계 4: 정규 2진 1:N 관계 타입
관계 타입 R에 대하여 N측의 참여 엔티티 타입에 대응되는 릴레이션 S를 찾는다. 1측의 엔티티 타입에 대응되는 릴레이션 T의 기본 키를 S에 외래 키로 포함시킨다.
S의 기본 키를 T의 외래 키로 포함시키면 정보의 중복이 발생한다.
단계 4: 정규 2진 1:N 관계 타입
단계 5: 2진 M:N 관계 타입
관계 타입 R에 대해서는 릴레이션 R을 생성한다.
참여 엔티티 타입에 해당하는 릴레이션들의 기본 키를 릴레이션 R에 외래 키로 포함시키고, 이들의 조합이 R의 기본키가 된다.
단계 5: 2진 M:N 관계 타입
단계 6: 3진 이상의 관계 타입
3진 이상의 관계 타입 R에 대하여 릴레이션 R을 생성하고, R에 참여하는 모든 엔티티 타입에 대응되는 릴레이션들의 기본 키를 R의 외래 키로 포함 시킨다. 만약 R에 참여하는 엔티티 타입들의 카디날리티가 1:N:N 이면 1의 릴레이션의 기본 키를 참조하는 외래 키를 제외한 나머지 외래 키들의 조합이 릴레이션 R의 기본키가 된다.
단계 6: 3진 이상의 관계 타입
단계 7: 다치 애트리뷰트
각 다치 애트리뷰트에 대하여 릴레이션 R을 생성한다.
다치 애트리뷰트를 애트리뷰트로 갖는 엔티티 타입이나 관계 타입에 해당하는 릴레이션의 기본 키를 릴레이션 R에 외래 키로 포함시킨다.
이와 비슷한 문제로 팩토리얼에서 0의 개수를 구하는 문제와 유사하다. 조합은 팩토리얼들의 연산들로 구할 수 있기 때문이다. 그 문제와 마찬가지로 nCm를 소인수 분해 했을 때 2의 갯수와 5의 갯수가 전체 0의 갯수와 관련있게 된다. 따라서 2와 5로 매번 나누면서 count를 하나씩 증가시켰더니 시간초과가 발생해버렸다. 아무래도 2,000,000,000 와 같이 엄청 큰 수가 들어 있는 것 같다.
따라서 시간초과를 해결하기 위해서 방법을 알아보는 도중에 2의 제곱수로 나눈 몫을 계속해서 더한 것이 2의 총 갯수가 된다는 것이였다. 간략히 그 이유를 설명하면 n!에 2가 들어 있는 수들은 크게 2의 배수, 4의 배수, 8의 배수....와 같이 있다고 생각할 수 있다. 예를 들어 10!이라고 가정하면 먼저 2의 배수를 세면 2, 4, 6, 8, 10이 있고 이 들의 개수를 하나씩 카운트를 증가시킬 수 있고, 그 다음에는 4의 배수는 4, 8이고 8의 배수는 8 하나이므로 총 8개의 2가 있게 된다. 표로 보면 다음과 같다.
2
3
4
5
6
7
8
9
10
계
1
1
1
1
1
5
1
1
2
1
1
1
3
1
3
1
8
이와 같은 방법으로 5를 구한다음에 nCm =n! / (m! * (n-m)!) 이므로 이에 맞춰서 2의 갯수와 5의 갯수를 구한 뒤에 더 작은 값이 0의 갯수가 될 것이다.
N(1<=N<=100,000)개의 로프가 있다. 이 로프를 이용하여 이런 저런 물체를 들어올릴 수 있다. 각각의 로프는 그 굵기나 길이가 다르기 때문에 들 수 있는 물체의 중량이 서로 다를 수도 있다.
하지만 여러 개의 로프를 병렬로 연결하면 각각의 로프에 걸리는 중량을 나눌 수 있다. k개의 로프를 사용하여 중량이 w인 물체를 들어올릴 때, 각각의 로프에는 모두 고르게 w/k만큼의 중량이 걸리게 된다.
각 로프들에 대한 정보가 주어졌을 때, 이 로프들을 이용하여 들어올릴 수 있는 물체의 최대 중량을 구해내는 프로그램을 작성하시오. 모든 로프를 사용해야 할 필요는 없으며, 임의로 몇 개의 로프를 골라서 사용해도 된다. 단, 각각의 로프는 한 개씩만 존재한다.
입력:
첫째 줄에 정수 N이 주어진다. 다음 N개의 줄에는 각 로프가 버틸 수 있는 최대 중량이 주어진다. 이 값은 10,000을 넘지 않는 정수이다.
출력:
첫째 줄에 답을 출력 한다.
풀이 방법:
로프가 중량을 견딜 수 있어야 하므로 로프들 중에 가장 작은 중량을 버틸 수 있는 것에 기준을 맞춰줘야 한다. 따라서 로프의 중량을 모두 받아서 내림차순으로 정렬을 하고 난 뒤에 하나씩 count를 늘려가면서 그 중 작은 로프의 중량과 count를 곱해서 버틸 수 있는 물체의 무게를 구하도록 했다.
한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의들에 대하여 회의실 사용표를 만들려고 한다. 각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 최대수의 회의를 찾아라. 단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다.
입력:
첫째 줄에 회의의 수 N(1<=N<=100,000)이 주어진다. 둘째 줄부터 N+1 줄까지 각 회의의 정보가 주어지는데 이것은 공백을 사이에 두고 회의의 시작시간과 끝나는 시간이 주어진다. 시작 시간과 끝나는 시간은 2^31 -1보다 작거나 같은 자연수 또는 0이다.
출력:
첫째 줄에 최대 사용할 수 있는 회의 수를 출력하여라.
풀이 방법:
그리디 알고리즘을 사용해서 풀어야 하는 문제라고 해서 어떻게 최적값만을 고를지 생각하다가 우선적으로 생각난 것이 시작 시간과 끝 시간의 차이가 작은 순으로 정렬해서 찾아보자고 생각했다. 어느정도 구현이 될 것 같긴 했지만 너무 복잡할 것 같아서 다른 방법을 생각하고자 했다.
그래서 단순하게 끝나는 시간이 작은 순으로 정렬을 하고 먼저 나오는 회의실부터 우선 배정하도록 하게 하고 배정된 끝시간보다 초과된 시작시간을 만나면 회의실을 바꾸도록 한다. (같아도 된다.)
월드전자는 노트북을 제조하고 판매하는 회사이다. 노트북 판매 대수에 상관없이 매년 임대료, 재산세, 보험료, 급여 등 A만원의 고정 비용이 들며, 한 대의 노트북을 생산하는 데에는 재료비와 인건비 등 총 B만원의 가변 비용이 든다고 한다.
예를 들어 A=1,000 B=70이라고 하자. 이 경우 노트북을 한 대 생산하는 데는 총 1,070만원이 들며, 열 대 생산하는 데는 총 1,700만원이 든다.
노트북 가격이 C만원이 책정되었다고 한다. 일반적으로 생산 대수를 늘려 가다 보면 어느 순간 총 수입(판매비용)이 총 비용(=고정비용+가변비용)보다 많아지게 된다. 최초로 총 수입이 총 비용보다 많아져 이익이 발생하는 지점을 손익분기점(BREAK-EVEN POINT)이라고 한다.
A,B,C가 주어졌을 때, 손익분기점을 구하는 프로그램을 작성하시오.
입력:
첫째 줄에 A,B,C 가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 21억 이하의 자연수이다.
출력:
첫 번째 줄에 손익분기점 즉 최초로 이익이 발생하는 판매량을 출력한다. 손익 분기점이 존재하지 않으면 -1을 출력한다.
풀이 방법:
우선 B가 C보다 크다면 A를 메꿀 수 없기 때문에 손익 분기점이 존재할 수 없다.
즉 이 말은 B와 C의 차이가 언제 A만원을 메꿀 수 있냐를 묻는 문제이므로 A를 (c-b) 준 값의 ceil을 해주면 쉽게 구할 수 있다.
위 사이트에서 각자 운영체제에 맞는 Git 설치 파일을 다운받을 수 있다. 설치를 완료한 후 다음과 같은 화면을 얻었다면 옳게 설치를 하게 된 것이다.
잘 설치하셨습니다.
이제 계속해서 다음을 누르며 따라가다보면 여러가지 옵션을 설정하게 되는데, 대부분 기본 설정을 유지하면서 따라가면 됩니다. 하지만 다음과 같이 기본 편집기를 고르는 화면이 나오는데 대부분 default로 vim(vi 편집기)로 설정 되어 있습니다. vi 편집기를 사용해보지 않은 사람이라면 이 편집기를 사용하는 것이 어려울 수도 있기 때문에 다른 편집기로 바꾼 뒤로 설정해주면 됩니다.
저는 VScode를 사용했습니다.
이후에도 계속 많은 설정들을 하는데, 전부 기본 설정 (이미 체크되어 있는)을 따라 가도 문제 없이 진행됩니다. 모든 설치가 완료되었다면 바탕화면이나 임의의 폴더에서 우클릭을 하면 다음과 같이 우클릭 창이 바뀌었을 것입니다.
Git Bash 와 Git GUI가 생겼습니다.
이제 Git Bash를 눌러서 Git의 언어를 사용할 수 있습니다.
여기까지 왔다면 이제 다 설치했습니다.
본격적으로 Git을 사용하기에 앞서서 초기 설정을 해주어야 하는데 사용자 이름과 사용자 메일을 등록해줘야 합니다. 등록하는 방법은 다음과 같습니다.
데이터베이스 설계는 요구사항 분석 - 개념적 설계 - DBMS의 선정 - 논리적 설계 - 스키마 정제 -물리적 설계 - 보안 설계 -구현 단계로 이루어져 있다.
데이터베이스 설계의 주요 단계
개념적 데이터베이스 설계는 실제로 데이터베이스를 어떻게 구현할 것인가와는 독립적으로 정보 사용의 모델을 개발하는 과정이다. 사용자의 요구사항으로부터 개념적 스키마가 만들어지며 실세계의 엔티티, 관계, 프로세스, 무결성 제약조건을 나타내는 추상화 모델을 구축하며 주로 엔티티 - 관계(ER) 모델을 사용한다. 엔티티는 서로 구분이 되면서 조직체에서 데이터베이스에 나타내려는 객체를 의미한다.
DBMS 선정은 기술적인 요인, 정치적인 요인, 경제적인 요인 등을 검토한 후에 DBMS를 선정한다.
논리적 설계는 개념적 스키마에 알고리즘을 적용해서 논리적 스키마를 생성한다. 논리적 스키마를 나타내기 위해 관계 데이터 모델을 사용하는 경우에는 ER모델로 표현된 개념적 스키마를 관계 데이터베이스 스키마로 사상한다. 또한 더 좋은 스키마로 변환하기 위해서 정규화 과정을 적용한다.
물리적 설계는 처리 요구사항들을 만족시키기 위해 저장 구조와 접근 경로 등을 결정한다. 응답 시간, 트랜잭션 처리율 등을 기준으로 성능을 평가한다.
ER 모델
데이터베이스 설계를 용이하기 위해서 제안되었으며, 계속해서 이 모델이 강화되어서 현재는 EER(Enhanced Entity Relationship) 모델이 데이터베이스 설계 과정에 널리 사용되고 있다. 기본적인 구문으로 엔티티, 관계, 애트리뷰트가 있고, 기타 구문으로는 카디날리티 비율, 참여 제약조건 등이 있다.
엔티티
엔티티는 독립적으로 존재하면서 고유하게 식별이 가능한 실세계의 객체를 의미하며 엔티티 타입은 동일한 애트리뷰트들을 가진 엔티티들의 틀이고, 엔티티 집합은 동일한 애트리뷰트들을 가진 엔티티들의 모임이다. 엔티티 타입으로는 크게 강한 엔티티 타입과 약한 엔티티 타입이 있다.
1. 강한 엔티티 타입은 독자적으로 존재하며 엔티티 타입 내에서 자신의 키 애트리뷰트를 사용하여 고유하게 엔티티들을 식별할 수 있는 타입이다.
2. 약한 엔티티 타입은 키를 형성하기에 충분한 애트리뷰트들을 가지지 못한 엔티티 타입으로 이 엔티티 타입이 존재하려면 소유 엔티티 타입이 존재해야하며 소유 엔티티 타입의 키 애트리뷰트를 결합해야만 약한 엔티티 타입을 식별할 수 있다. ER 다이어 그램에서 이중선 직사각형으로 표기하며 부분 키는 점선 밑줄을 그어서 표시한다.
ER모델에서 엔티티는 직사각형으로 표시한다.
애트리뷰트
하나의 엔티티는 연관된 애트리뷰트들의 집합으로 설명된다. 엔티티는 독립적인 의미를 가지지만 애트리뷰트는 독립적인 의미를 가지지 않는다. ER 모델에서 타원형으로 나타내며 기본키의 경우에는 밑줄을 그어준다. 애트리뷰트와 엔티티 타입은 실선으로 연결한다.
1. 단순 애트리뷰트
더 이상 다른 애트리뷰트로 나눌 수 없는 애트리뷰트로 ER 다이어그램에서 실선 타원으로 표현한다. ER 다이어그램에서 대부분의 애트리뷰트는 단순 애트리뷰트인 경우가 많다. 대부분의 단순 애트리뷰트는 단일 값 애트리뷰트이다. 단일 값 애트리뷰트는 각 엔티티마다 정확하게 하나의 값을 가지는 애트리뷰트를 의미한다. 예를 들면 학생의 학번 애트리뷰트는 어떠한 학생도 두 개 이상의 학번을 가지지 않으므로 단일 값 애트리뷰트이다.
단순 애트리뷰트와 복합 애트리뷰트
2. 복합 애트리뷰트
두 개 이상의 애트리뷰트로 이루어진 애트리뷰트로 동일한 엔티티 타입이나 관계 타입에 속하는 애트리뷰트들 중에서 연관된 것을 모아놓은 것이다.
이 외에도 다치 애트리뷰트, 저장된 애트리뷰트, 유도된 애트리뷰트가 있다.
관계와 관계 타입
관계는 엔티티들 사이에 존재하는 연관이나 연결로서 두 개 이상의 엔티티 타입들 사이의 사상으로 생각할 수 있다. 요구사항에서 동사가 ER 다이어그램에서 관계로 표현되며 다이아몬드로 표기한다. 관계 타입은 관계의 특징을 기술하는 애트리뷰트들을 가질 수 있으며, 키 애트리뷰트를 가지지 않는다.
관계와 관계 타입에는 차수와 카디날리티라는 것이 있다. 차수란 관계로 연결된 엔티티 타입들의 개수를 의미하며 주로 2진 관계가 흔하다. 카디날리티 비율은 한 엔티티가 참여할 수 있는 관계의 수를 나타낸다. 흔히 1 : 1, 1:N, M:N으로 구분을 한다.
1. 1:1 관계
E1의 각 엔티티가 정확하게 E2의 한 엔티티와 연관되고, E2의 각 엔티티가 정확하게 E1의 한 엔티티와 연관되었을 경우
ex) 각 학생에 대해 최대한 한 개의 노트북이 있고, 각 노트북에 대해 최대 한 명의 학생이 있다면 학생과 노트북 간의 관계는 1 : 1 관계이다.
2. 1:N 관계
E1의 각 엔티티가 E2의 임의의 개수의 엔티티와 연관되고, E2의 각 엔티티는 정확하게 E1의 한 엔티티와 연관되면 이 관계를 1 : N 관계라고 하며 실세계에서 가장 흔히 나타나는 관계이다.
ex) 각 학생은 한 명의 지도교수님을 가지고 있지만, 지도 교수님은 여러 학생들을 가지고 있다.
3. M:N 관계
한 엔티티 타입에 속하는 임의의 개수의 엔티티가 다른 엔티티 타입에 속하는 임의의 개수의 엔티티와 연관될 경우 M:N 관계이다.
ex) 각 학생은 여러 강의를 수강할 수 있고, 각 강의는 여러 명의 학생들을 가질 수 있으므로 M : N 관계이다.
카디날리티 비율의 최솟값과 최댓값을 관계와 엔티티를 연결하는 실선 위에 (min, max) 형태로 표기한다. 어떤 관계 타입에 참여하는 각 엔티티 타입에 대하여 min은 이 엔티티 타입 내의 각 엔티티는 적어도 min번 관계에 참여함을 의미한다. max는 이 엔티티 타입 내의 각 엔티티는 최대한 max 번 관계에 참여함을 의미한다.
min = 0은 어떤 엔티티가 반드시 관계에 참여해야 할 필요는 없음을 의미하고, max=*는 어떤 엔티티가 관계에 임의의 수만큼 참여할 수 있음을 의미한다.
이와 비슷한 개념으로 전체 참여와 부분 참여가 있다. 전체 참여는 어떤 관계에 엔티티 타입 E1의 모든 엔티티들이 관계 타입 R에 의해서 어떤 엔티티 타입 E2의 어떤 엔티티와 연관되는 것을 의미한다. 부분 참여는 어떤 관계에 엔티티 타입 E1의 일부 엔티티만 참여하는 것을 의미한다. 약한 엔티티 타입은 항상 관계에 전체 참여로 표시되며, 전체 참여는 ER 다이어그램에서 이중 실선으로 표시된다.
위의 내용들에서 사용한 표기법으로 수십 개 이상의 애트리뷰트를 설명한다면 매우 불편하므로 새발 표기법이라는 것을 사용한다.
19세기 독일 수학자 헤르만 민코프스키는 비유클리드 기하학 중 택시 기하학을 고안했다. 택시 기하학에서 두 점 T1(x1,y1), T2(x2,y2) 사이의 거리는 다음과 같이 구할 수 있다.
D(T1,T2) =| x1-x2| + |y1-y2|
두 점 사이의 거리를 제외한 나머지 정의는 유클리드 기하학에서의 정의와 같다.
따라서 택시 기하학에서 원의 정의는 유클리드 기하학에서 원의 정의와 같다.
원 : 평면 상의 어떤 점에서 거리가 일정한 점들의 집합.
반지름 R이 주어졌을 때, 유클리드 기하학에서 원의 넓이와, 택시 기하학에서 원의 넓이를 구하는 프로그램을 작성하시오.
입력:
첫째 줄에 반지름 R이 주어진다. R은 10,000보다 작거나 같은 자연수이다.
출력:
첫째 줄에는 유클리드 기하학에서 반지름이 R인 원의 넓이를, 둘째 줄에는 택시 기하학에서 반지름이 R인 원의 넓이를 출력한다. 정답과의 오차는 0.0001까지 허용한다.
풀이 방법:
수학적 지식을 활용하면 쉽게 풀 수 있는 문제이다. 일반 유클리드 기하학에서의 원의 넓이는 pi*r^2 (r은 반지름)이다. 하지만 비유클리드 기하학, 즉 택시 기하학에서의 원은 우리가 일반적으로 알고 있는 둥근 모양이 아니라 마름모 모양이 나오게 된다.
택시 기하학에서 중심이 원점이고 반지름이 1인 원은 (0,1) (1,0) (-1,0), (0,-1)의 끝 값을 가지고 (+-1/2, +-1/2)인 끝 값 사이의 중간 값을 가져서 이를 모두 이으면 마름모 모양이 나오게 된다. 마름모 모양의 넓이는 지름^2 *(1/2)로 구할 수 있으므로 이 문제에선 2*r^2(r은 반지름) 으로 넓이를 구할 수 있다.
ps)이 문제에서 math 모듈의 pi를 사용해서 문제를 풀었더니 오답을 받아서 직접 pi의 값을 길게 잡아서 계산했더니 맞았다.
지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨다. 그리고 이 각각의 타일들은 0 또는 1이 쓰여 있는 낱장의 타일들이다.
어느 날 짓궃은 동주가 지원이의 공부를 방해하기 위해 0이 쓰여진 낱장의 타일들을 붙여서 한 쌍으로 이루어진 00 타일들을 만들었다. 결국 현재 1 하나만으로 이루어진 타일 또는 0 타일을 두 개 붙인 한 쌍의 00 타일들만이 남게 되었다.
그러므로 지원이는 타일로 더 이상 크기가 N인 모든 2진 수열을 만들 수 없게 되었다. 예를 들어, N=1일 때, 1만 만들 수 있고, N=2일 때는 00,11 을 만들 수 있다. (01, 10 은 만들 수 없게 되었다.) 또한 N=4일 때는 0011, 0000, 1001, 1100, 1111 등 총 5개의 2진 수열을 만들 수 있다.
우리의 목표는 N이 주어졌을 때 지원이가 만들 수 있는 모든 가짓수를 세는 것이다. 단 타일들을 무한히 많은 것으로 가정하자.
입력:
첫 번째 줄에 자연수 N이 주어진다. (N <=1,000,000)
출력:
첫 번째 줄에 지원이가 만들 수 있는 길이가 N인 모든 2진 수열의 개수를 15746으로 나눈 나머지를 출력한다.
풀이 방법:
전형적인 DP문제 이므로 점화식을 찾으면 쉽게 풀 수 있는 문제이다. 그리고 N= 5까지 숫자들을 나열해보면 규칙을 찾을 수 있다.
N=1일 때 1개, N=2일 때 2개, N=3일 때 3개, N=4일 때 5개, N=5일 때 8개 ....
즉 N=n일 때, N=n-2인 경우 + N=n-1인 경우임을 알 수 있다. 이를 바탕으로 계산을 하면서 각 계산 값에 대해 15746으로 나누면 통과할 수 있다.(맨 마지막 값에 대해서만 나누면 시간초과가 발생할 수 도 있다.)
