본문 바로가기

전체 글

 (159)
UCPC 2021 본선 후기 6솔 12등 5등상으로 마감했다. 당장 대회 이틀 전에 굉장한 소식이 들려온 뒤라 좀 시작할 때 분위기는 조금 어수선한 상태였던 거 같다. 여러분 Redshift가 월파를 가요!! 19년도 서울 ICPC 결과로 와일드카드 슬롯을 받아서 간다고 합니다. 19년도 결과다 보니 전 못갑니다. UCPC 예선이 굉장히 쉬운 셋이어서 본선도 평소보다 좀 할만하지 않을까란 생각을 했지만 어림도 없었다. 노솔 문제가 2개나 있는 헬 셋이다. 시프트님이 A, D, F 3솔, 샘터님이 E, H 2솔, 내가 J 1솔이다. 대회 진행을 간단히 써보자. 초반(~60min) 시프트님이 앞의 4문제 샘터님이 중간 4문제, 내가 마지막 4문제를 보기로 하고 대회를 시작했다. 끝에서부터 문제를 읽어가면서 L은 그래프 문제인가? 란 생..
백준 17955번 Max or Min 어제 처음으로 팀연습하다가 다이아 3을 풀어서 기쁜 마음에 풀이를 작성한다. 심지어 제출 한 번만에 맞췄다! 문제 요약 길이가 $N$인 원형 수열 $a$가 주어진다. $1 \le a_i \le M$ 이다. 이 때 다음과 같은 연산을 할 수 있다. $a_i$를 하나 골라서 인접한 두 수와 $a_i$의 최솟값 혹은 최댓값으로 $a_i$를 바꿔줄 수 있다. 이런 연산을 반복해서 수열 전체를 $k$로 만들기 위한 최소 연산 횟수를 계산해야 한다. $3 \le N \le 2 \cdot 10^5, 1 \le M \le 10^5$ 풀이 실제로 구해야 하는 것은 $1 \le k \le M$인 모든 $k$에 대한 답이지만 일단 이걸 $k$로 고정한 뒤에 최적의 연산 횟수를 구해보자. 일단 $k$가 존재하지 않는 수라면 ..
UCPC 2021 예선 & ABC 212 후기 오늘 오후 2시에 UCPC 예선이 있었다. 일단 E도 J도 못 풀 문제가 아니었다. 샘터님이 오늘 예선날인거를 까먹어서 참가를 못했는데 둘이서 8솔이면 셋이면 12솔이니까 된 거 아닐까 싶기도 하다. 사실 시프트님이 6솔했으니 시프트의 차력쇼라고 불러야 맞는거 아닐까? 일단 코로나가 무서워서 비대면으로 하잔 얘기가 나왔고 팀연습을 디코로 비대면 진행한지 꽤 되기 때문에 예선은 그렇게 하고 본선은 모이는 방향으로 하자고 2주 전에 결정한 뒤에 오늘 예선을 치기로 했다. 1시 좀 지나서 45분에 모이기로 정해놓고 한 50분쯤에 모였다. 샘터님이 연락이 안된다. 샘터 없는 대회라니 살짝 패닉상태에서 시작했다. 시프트님이 앞에서부터 읽기로 했고 난 뒤에서부터 읽기로 했다. 스코어보드 슬쩍슬쩍 보면서 문제를 읽고..
Atcoder Beginner Contest 210 후기 일단 초반에 인터넷이 잠깐 나가는 상황이 발생했다. 그리고 이에 맞춰 정신 못차렸는지 1번도 아니고 2번이나 A에서 2페널티 C는 멀티셋이 상수가 크니까 좀 불안하긴 하지만 그따구로 세팅하지 않았겠지란 마음으로 그냥 냈다가 시간초과를 받고 해시맵으로 바꿔서 제출했다. C까지 페널티 한번 쌓고 뒷문제를 보려니 일단 마음을 가다듬기 위해 스코어보드를 봤다. 웬일로 E까지 좀 풀려있더라. 그래서 D보고 답이 빠르게 안떠오르면 E로 넘어가기로 결정하고 문제를 열었다. D는 네제곱 풀이에서부터 줄이는 형식으로 생각했다. 한 점에 대해서 거리가 고정된 점들의 최소를 잘 전처리하면 어떻게 되나? 이러다가 이분탐색인가?란 헛생각도 하다가 이런 방식으론 줄여봤자 세제곱일거 같아서 일단 E로 넘어가기로 했다. E는 MST..
Atcoder Beginner Contest 209 후기 사실 지지난주엔가 AGC를 참가했었는데 A 하나만 13분에 풀고 남은 시간 내내 BC 붙잡고 고민하다가 지쳐서 그냥 잤었다. 그렇게 다시 민트로 간 다음 오늘 블루로 복귀했다. 팀연습 때문에 한동안 ABC를 못했는데 요즘 라운드는 비기너가 풀라고 내는 거 같지가 않다 라운드 시작은 항상 가슴이 평소보다 한참 빨리 뛰는 거 같다. 보통 시작 5분 전엔 컴퓨터 앞에 앉아서 종이도 준비하고 물도 떠오고 무슨 노래 들을지 생각하면서 준비하는데 상당히 긴장된다. 특히 ABC는 D까지는 빨리(20분 안쪽) 풀어놔야 레이팅이 유지되기 때문에 라운드 초반이 힘든 거 같다. 오늘은 다행히 10분만에 D까지 끝냈다. A도 그렇고 B도 그렇고 해석에 시간을 생각보다 많이 썼다. PS 문제를 읽을 땐 입력 출력 예제부터 슥 ..
Buffer Pool Manager - 2 Buffer Pool은 사실상 page table의 역할을 OS 대신에 하는거나 마찬가지입니다. 그리고 이런 저장장치 간의 속도 차이로 인한 캐싱 이슈는 CS에서 굉장히 고전적인 이슈입니다. OS 수업에서도 page replacement는 들어본 적이 있을 겁니다. page table에서와 같이 buffer pool도 파일 크기에 비해 작은 메모리를 잘 사용하기 위해서 replacement policy를 잘 세워야 합니다. 사실 누군가가 OS 수업에서 들었을 얘기와 겹치는 부분이 많지만 buffer pool의 replacement policy를 알아봅시다. Buffer Replacement Policies 먼저 언제 replacement가 일어나는지 알아보자. DBMS가 쿼리를 수행하면서 파일을 읽어들이..
Buffer Pool Manager - 1 DBMS는 디스크에 있는 파일에 직접 접근할 수가 없습니다. 무조건 메모리에 올린 다음에 접근이 일어나야 합니다. 디스크 I/O는 정말 느립니다. 그래서 디스크에 존재하는 파일들을 얼마나 효율적으로 메모리에 올리고 내리는지는 성능에 있어서 중요해집니다. 이런 이유 때문에 DBMS는 OS에게 이러한 작업을 맡기지 않고 직접하려고 하죠. 이러한 작업을 효율적으로 만들기 위해 신경 쓸 부분을 두 가지로 볼 수 있습니다. 먼저 같이 사용되는 비율이 높은 페이지들은 디스크 상에서 서로의 거리가 가깝게 저장하도록 하는 것입니다. 같이 사용되는 페이지들이 가깝게 위치한다면 sequential access의 이점을 늘릴 수 있는 것이죠. 이런 식으로 효율성을 늘리는 것을 spatial control이라고 합니다. 다른..
Atcoder Beginner Contest 206 후기 제 1차 블루 방어전은 성공했다. 이렇게 쳐도 레이팅이 오르네 일단 A, B, C를 5분만에 푼걸 보면 세문제는 굉장히 쉬웠던 것을 알 수 있다. C를 제출하고 D를 보자마자 좀 막막했다. 이거 성질 찾는 문제인가? 스탠딩으로 가서 D, E, F의 푼 사람 수를 봤다. 14, 1, 1인가 그랬다. A,B,C는 세자리수 단위로 풀려있었던걸로 기억한다. 그래서 D가 성질 찾는게 맞는 갑다 하고 바로 EF를 보러 갔다. E는 수 범위가 100만 밖에 안되서 조화급수 형태의 뭔가로 하거나 gcd로 가능한 모든 것을 보면서 카운팅 하면 되겠다 싶었다. 당장 자세한 풀이는 안떠올랐지만 한 10분만 고민해도 풀 수 있을 거 같아서 F로 넘어갔다. F는 게임 문제였는데 그래프 적으로 접근했다가 끝까지 못풀었다. 제일 ..

티스토리툴바