pizzaroot

pizzaroot 의 올해 ICPC는 작년에 같이 나갔던 형 한명 wlsth1004100 과 동아리에서 발굴한 새로운 한명 javago 와 같이 나갔다. 나는 수학, 기하, 애드 혹, DP, 조합론, 정수론 담당이였고 wlsth1004100 는 이제 그래프, 구현, 템플릿 담당 그리고 javago 는 이제 애드 혹, 게임 이론, 그리디, DP 담당이였다. 예비소집날에는 건대 팀 Ilgam Rangers, Saenaegi 와 함께 저녁 식사를 했다. 우리는 Default 라는 팀명으로 세종대에서 나왔다. 팀노트는 그동안 한번도 사용한 적이 없지만 보험용으로 잘 만들어서 갔다. 사실 예선 성적이 기대보다 많이 높게 나와서 본선 기대치가 많이 올라간 상황이였다. 잠을 잘 잔 후에 커피로 도핑을 한 후 대회장에..

26등이라는 성과를 냈다. 여러가지 생각이 들었다. 문제가 쉬웠나? 만약 문제가 쉬웠다면 다른 팀들도 많이 풀었을 것이다. 잘하는 팀들이 많이 빠졌나? 잘 모르겠다 실력이 늘었나? 는것은 맞지만 이렇게 까지 등수가 오른것은 이상하다. 운이 좋았나? 푼 문제중에서 어렵게 느껴진 문제는 없었다. 누군가가 설계한 몰래카메라에 당한 것인가? 그럴지도 모른다. 어쨌든 CDGK를 매우 빠르게 내가 풀어서 다른 문제에 할당할 시간이 많았던 것 같다. I를 풀었고 J는 아쉽게 못풀었다. 흠.. J가 세제곱에 돈다는 소문이 있는데 벡터로 짜서 그런지 TLE가 났다.

정렬이란 무엇인가? 정렬은 집합 속 모든 원소들을 순서대로 나열하는 것이다. 정렬은 꼭 수를 정렬할 때만 쓰이는 것은 아니다. 영어 단어들은 알파벳 사전순으로 정렬할 수 있고 한국어 단어들은 가나다순으로 정렬할 수 있다. 정렬 알고리즘은 여러가지가 있다. 프로그래밍을 처음 입문하면서 배우는 버블 정렬, 선택 정렬, 삽입 정렬과 퀵 정렬, 합병 정렬, 힙 정렬 등 매우 많이 존재한다. 하지만 오늘은 이런 정렬 알고리즘에 대해 소개하지는 않을 것이다. 간단하게 언급만 하자면 정렬할 원소의 개수가 \(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..