목록공부 (38)
pizzaroot
정렬이란 무엇인가? 정렬은 집합 속 모든 원소들을 순서대로 나열하는 것이다. 정렬은 꼭 수를 정렬할 때만 쓰이는 것은 아니다. 영어 단어들은 알파벳 사전순으로 정렬할 수 있고 한국어 단어들은 가나다순으로 정렬할 수 있다. 정렬 알고리즘은 여러가지가 있다. 프로그래밍을 처음 입문하면서 배우는 버블 정렬, 선택 정렬, 삽입 정렬과 퀵 정렬, 합병 정렬, 힙 정렬 등 매우 많이 존재한다. 하지만 오늘은 이런 정렬 알고리즘에 대해 소개하지는 않을 것이다. 간단하게 언급만 하자면 정렬할 원소의 개수가 \(n\)일 때, 버블/선택/삽입 정렬은 \(O(n^2)\)의 시간복잡도를, 합병/힙 정렬은 \(O(n\log n)\)의 시간복잡도를 가진다. 퀵 정렬은 좀 더 생각해봐야 될 점이 있기 떄문에 여기서는 언급하지 않으..
PS에서 시간복잡도는 매우 중요하다. 시간복잡도는 보통 Big O notation으로 나타낸다. 그래서 시간복잡도가 무엇인가? PS에서 시간복잡도는 문제를 해결하는 데에 걸리는 시간을 입력 크기를 나타내는 변수(들)로 나타낸 함수이다. 하지만 우리가 관심을 가지는 것은 최악의 경우이다. Big O notation의 formal한 정의를 설명하자면 만약 모든 실수 \(x>x_0\)에 대하여 \(f(x)\leq cg(x)\)를 만족하는 실수 \(x_0\)와 양의 실수 \(c\)가 존재한다면, \(f(x)\in O(g(x))\)로 표현한다. 정확하게는 \(O(g(x))\)는 함수들의 집합이지만 다음과 같이 많이 나타낸다. \[f(x)=O(g(x))\] 다른 표기법도 존재하지만 Big O notation을 거의..
1. 동아리 한손 동아리 가입, SAL 1기 부원 모집 SAL 연습대회 1, 2 개최 2. 중간고사 실패한 체리픽 3. 오픈소스 우산남 내 마음은 오픈 소스 4. 기말고사 방방다망함 5. 기타 고학번 형 누나들과 말을 하다
Get ready 하셔야죠 Canonical Cover 구하기 Extraneous attribute를 좌항에서 지운 FD를 F1이라 하면 F⊆F1은 보장됨 Extraneous attribute를 우항에서 지운 FD를 F2이라 하면 F2⊆F은 보장됨 따라서, α→β의 좌항에서 attribute A를 지울때는 F에서 α-{A}→β가 유도될수 있는지만 확인하면 됨 α→β의 우항에서 attribute B를 지울때는 F2에서 α→β가 유도될수 있는지만 확인하면 됨 또한 F-(α→β)≡F를 만족하면 α→β를 아예 삭제하면 됨 즉, α→β에서 α-{A}의 closure가 β를 포함하면 A는 extraneous attribute임 F2에서 α의 closure가 β를 포함하면 α→β의 우항에서 attribute B가 e..
2023년 4월 15일 DBMS 3-Level Architecture [1번 0.5점 예상] External Level - Conceptual Level - Internal Level 아래는 Relation인가 Relation이 아닌가? ID NAME SEMESTER 998 Alice 7 100 Bob 4 101 Bob 4 Relation이다. 각 tuple은 유일하다. [2번 0.5점 예상] 아래는 Relation인가 Relation이 아닌가? ID NAME SEMESTER 244 Park 5 350 Jane 2 350 Jane 2 Relation이 아니다. Tuple (350, 'Jane', 2)는 유일하지 않다. relation \(r\)의 cardinality가 \(10\)일 때, \(r\bowt..
2023년 04월 12일 확률변수 \(X\)를 같은 면이 세 번 연속으로 나올 때까지 동전을 던진 횟수라고 할 때, \(P(X\leq9)\)의 값을 구하시오. 상태 \(i\)가 현재 연속 스트릭을 나타내는 마르코프 체인을 정의하면 상태공간은 \(\{1, 2, 3\}\)이 되고, 전이행렬 \(\mathbf P\)는 다음과 같다. \(\displaystyle\mathbf P=\begin{bmatrix}\frac{1}{2} & \frac{1}{2} & 0 \\ \frac{1}{2} & 0 & \frac{1}{2} \\ 0 & 0 & 1 \end{bmatrix} \) 구하려는 값은 \(\displaystyle\mathrm P_{13}^{(8)}=\frac{201}{256}\)이다.
먼저 \(N\)이 \(10\,000\)까지 들어오는 것을 보아서 각 선풍기마다 시간 간격만큼씩 더해가며 시뮬레이션 하는 풀이는 통과하기 힘들것이라는 짐작이 벌써 든다. 각 선풍기 마다 \(O(1)\)만에 가격을 구하는 풀이도 존재할 것 같지만, 일단은 쉽게 구현한다는 생각이 들어서 이분탐색을 떠올리게 된다. 대충 구상을 했으니 이제 코드를 짜기 시작한다. 라고 생각하고 코드를 짜다보니 시간이 이미 주어지므로 이분탐색이 전혀 필요 없다는 사실을 깨닫게 된다. 그렇다면 총 몇번을 추가 결제 해야 하는가를 구할 때 \(\displaystyle\left\lfloor\frac{Q}{K}\right\rfloor\)번인지 \(\displaystyle\left\lceil\frac{Q}{K}\right\rceil\)번인..