전체 글 46

HLD (Heavy Light Decomposition)

https://justicehui.github.io/hard-algorithm/2020/01/24/hld/ : 이 글이 이론의 전반적인 이해에 큰 도움이 되었다. GOAT. 오일러 투어 테크닉, LCA 등의 쉬운 트리 이론은 트리 문제 하나로 전부 정리된다고 생각한다. 해당 문제를 풀 수 있으면 심화 트리 이론을 공부할 수 있는 것이고, 해당 문제를 풀 수 없다면 기초부터 다시 다지고 올라와야한다. 여기서 쉬운 트리 이론과 심화 트리 이론을 당당하게 나누어 말할 수 있는 이유는 난이도 차이가 실제로 매우 크기 때문이다. 심화 트리 이론의 첫 단계라고도 말할 수 있는 HLD는 쉬운 트리 이론은 물론이거니와 세그먼트 트리까지 완벽하게 장착하고 있어야 이해할 수 있는 이론이다. 반대로 말하면, 쉬운 트리 이론..

Graph/Tree 2024.10.08

1일 1트리 기록장

1일 1트리란?- 고등학교 2학년에서 3학년으로 넘어가는 겨울방학에 1일 1수쿼 프로젝트를 진행하여 하루에 수열과 쿼리 문제를 하나 이상 해결하거나 풀이를 정리하는 과제를 스스로에게 부여하여 1달 조금 넘게 진행하였다. 당시의 기억이 행복하게 남아있기도 하고, PS를 거의 2년간 쉰 지금 아직도 수쿼 관련된 자구들은 기억에 남아있는 것을 보아 학습효과도 상당히 좋았던 것 같다.- 이를 이어 오늘부터 1일 1트리를 진행하려고 한다!- 는 아니고... 사실 지금 학기 중이고 곧 시험기간이라 많이 바쁘다. - 아직 PS를 본격적으로 공부해보지 않은 친한 친구들과 팀을 꾸려 ICPC에 나가게 되었다. 나도 PS를 오래 쉬었으니 인터넷 예선을 통과하여 리저널을 찍먹하는 것이 목표이다.- 팀원 중 한 명이 원래 수..

기타 2024.10.02

2023 SCPC 2차 예선 후기 + 본선 진출 컷 분석

총점 : 100/200/90/180/60 = 630 [본선 진출] 1. 동아리의 아주 중요한 일정과 겹쳐 대회를 정상적으로 치지 못했다. 2. 1/2번이 쉬웠고 4/5번의 최대 서브태스크가 자명이었는데, 3번과 4번의 점수에 따라 갈릴 것 같다. 3. 본선 진출 컷은 630점 또는 585점의 상위권 어딘가 될 확률이 높다. [실제로 585에서도 본선 진출 소식이 들려왔다] 이 블로그에 게시글이 올라오는 빈도가 줄어든 것으로도 알 수 있듯이, 대학 진학 후 PS를 거의 손에서 놨다. 친구들과 많이 놀러다니기도 하고, 동아리 활동도 열심히 하면서 세상에서 제일 한가하다는 새내기의 삶을 맘껏 체험했다. 그럼에도 PS는 앞으로 과외를 위해서라도 아예 놓을 수는 없었고, SCPC와 같이 상금이 큰 대회를 위해서라..

대회 후기 2023.08.24

2022 나코더 송년대회 후기

결과 : 2위 (6솔, 시간페널티 803분) https://unorderedmap.tistory.com/9 2021 나코더 송년대회 후기 결과 : 2위 (7솔,시간페널티 922분) 나코더 송년대회는 경기과학고등학교의 PS 동아리 '나는코더다'에서 주최하는 연례 행사이다. 카카오, 넥슨 등의 후원을 받아 진행되어 상품도 푸짐하여 경기과 unorderedmap.tistory.com 작년에는 온라인으로 진행되었던 나코더 송년대회가 학교 강당에서 오프라인으로 진행되었다. 많은 친구들이 강당에 모여서 피자도 먹고 코딩도 하니 대회보다는 축제 분위기에 더 가까웠던 것 같다. 출제를 해준 mathking1021, jbkmath48128, donghwa722, ftkbrian, sciencepark은 모두 같은 기수 ..

대회 후기 2023.01.04

한국정보올림피아드(KOI 2022) 2차 시험 후기

총점: 100/100/14/34=248 (동상, 13.37%, 25위) 1. 1, 2번이 쉽지만은 않았던 시험 2. 마지막 득점 시간 "2시간 24분" 3. TC35에서 TLE 보통 KOI 2차 시험에는 1번, 2번에 조금의 노력만으로 100점을 받을 수 있는 문제가 나오고, 3번, 4번에 변별력 있는 서브태스크들을 가진 문제가 나온다. 그래서 수상권에서의 등수는 3번, 4번에서 부분점수를 얼마나 긁었느냐에 따라 결정된다. 그런데 최근 들어 1번, 2번의 문제 난이도가 심상치 않다. 물론 조금 고민하면 풀 수 있는 문제이긴 하지만, 문제를 처음 읽고 나서 조금 당황하게 되는 수준이다. 이에 따라 나는 집중력이 가장 높은 초반부에 3번, 4번 서브태스크들을 잡고, 조금 집중력이 떨어진 시기에 1번, 2번을..

대회 후기 2022.07.17

아시아 태평양 정보올림피아드(APIO 2022) 후기

총점 : 14 + 60 + 93.7 = 167.7 (한국 기준 10등, Unofficial 동상) 1. 2번과 3번은 변별력이 크지 않아서 1번 점수에 따라 시험의 성패가 갈렸다. 2. 그런데 1번이 딱히 좋은 문제인지는 모르겠다... 3. 작년보다 쉬운 난이도로 숨통은 좀 트이는 시험이었다. APIO 2021에서 5시간 동안 머리를 싸매고 얻은 결과가 40점대였기에, APIO라는 시험에 대해 그렇게 좋은 기억이 있지는 않았다. 또한 한국 6등까지만 수상이 가능한데 수많은 계절학교 모의고사 및 선발고사에서 한 셋 기준으로 6등 안에 들어본 기억이 없기에, 참가에 의의를 두고 즐겁게 참여했다. 원래는 KMO 다음 날 보려고 했는데, KMO를 생각보다 잘 봐서 머리 컨디션이 좋다고 판단하고 당일 밤에 응시하..

카테고리 없음 2022.05.30

한국수학올림피아드(KMO 2022) 고등부 가우스부 1차 시험 후기

총점 : 1교시 46 + 2교시 40 = 86 (상위 5%, 금상) 1. 문제들이 쉬워서 금컷을 90점대로 예상한다. 2. 계산 실수를 하지 않아서 준비를 안했음에도 점수가 잘 나왔다. 3. 6점은 다 맞혔지만 4점은 하나 틀렸다... unordered_map이 PS하는 블로그 이지만 나는 중학교 때까지 수올러였다. (이 블로그의 첫 글인 소개 글을 보면 알 수 있다.) 3년 동안 수올에 손을 놓고 있다가, 문득 이번이 수올을 볼 마지막 기회라는 걸 깨달았다. 그래서 준비 단 1분도 하지 않고, 오로지 참가에 의의를 두고 마지막 수올을 응시했다. 그렇게 부담 없이 봐서 그런지 계산실수도 하나도 안했고, 점수가 생각보다 잘 나와서 2차에는 갈 것 같다. 상의 색은 7월 4일에 결과가 발표하는 대로 이 글 ..

대회 후기 2022.05.30

한국정보올림피아드(KOI 2022) 1차 시험 후기

총점 : 1교시 139 + 2교시 213 = 352 (가채점 결과 3.467%, 77등, 은상) 1. 1교시가 어려웠다. 2. 2교시가 많이 망한줄 알았으나 생각만큼 망한건 아니었다. 3. 2교시 3번은 Dumae와 거의 같은 문제이다. 작년에 플5짜리 문자열 문제를 못 풀고 1차 탑골드를 놓쳐 많이 아쉬웠다. 비버챌린지는 196.xx점이어서 실수한 소문제 2개에서만 감점이 있었기에, 이번에도 2교시가 지난 해와 비슷한 난이도로 나오면 만점에 가까운 점수로 탑골드를 노릴 수 있다고 생각하고 시험에 들어갔다. 1교시. 비버챌린지형(200점) - 킬러 문제 및 배점이 큰 문제에는 굵은 글씨를 해두었다. 총평 - 단답형 12번이 어려웠고, 시뮬레이션형 문제 17, 19, 20번 난이도가 작년 기준 가장 어려운..

대회 후기 2022.05.16

solved.ac 다이아1 달성 후기

다이아2가 된지 한 달 정도 후에 다이아1에 올라왔다. 사실 학기 시작 전에 달성했는데 글 작성하는 것을 까먹어서 작성을 안하고 있었다. 학기가 시작한만큼 앞으로는 PS에 투자할 시간이 거의 없을 것 같다. 브론즈 풀면서 스트릭 유지나 해야할 것 같다. 레이팅 상승 요인은 PST + PBS + Splay Tree로 요약할 수 있겠다. 특히 스플레이 트리에 큰 흥미를 느껴 거의 10문제 정도 푼거 같은데, 스플레이 트리 기본 티어가 D3이라 레이팅이 빠르게 올랐던 것 같다. 앞으로 루5를 찍을 일이 있을지조차 모르겠다. 여름방학에 PS를 하더라도 새로운 알고리즘을 배우고 어려운 문제를 풀기 보다는 랜덤 디펜스를 할 것 같다. 곧 있을 국대 선발고사 2차 준비나 잘 해야할 것 같다.

기타 2022.03.07

Codeforces Master 달성 후기

최근 7시에 진행되었던 딥1-딥2 분리형 코포를 제외하고 방학 내내 모든 코포에 참여하였고, 그 대가로 이름표를 주황색으로 칠할 수 있게 되었다. 아마 학기 중 코포는 웬만하면 참여하지 않을 것 같고, 참여하더라도 아직 블루인 부계정으로 참여할 것 같다. 위의 표에서 알 수 있듯이 이번 방학에 레이팅의 진폭이 많이 컸다. 01.22 +210을 기록했던 Round 767은 처음으로 저렇게 높은 점수를 기록했다는 사실에 감격하여 글로 남겼었다. (https://unorderedmap.tistory.com/10 참고) 이 때까지만 해도 오렌지까지 12만 남은 상황이었고, 곧 오렌지에 갈 수 있을 줄 알았다... 01.30~31 그 희망은 산산조각 났다. 사실 30일 코포에는 그냥 내 실력보다 조금 안 나온 정..

대회 후기 2022.02.28