예년 본선 후기가 별로 없길래 저라도 적어봅니다. 대회 전 https://heejayaa.tistory.com/165 올해는 제가 옥 선생님(utilforever)께 얻어먹었습니다 😋 등심? 스테이크, 리코타 치즈? 샐러드, 뇨끼를 먹었습니다. 뇨끼를 처음 먹어봤는데 쫄깃하고 맛있었습니다. 스테이크는 두툼하니 야무졌습니다. 잘 먹고 들어가서 끝까지 잘 버틸 수 있었던 것 같네요 :) 감사합니다! 한편, NYPC의 시간대를 부분집합으로 갖는 춘배컵이 BOJ에서 진행 중이었습니다. 저는 N. 고양이 리그 문제를 출제했습니다. xiaowuc1님이 퍼솔하는 걸 확인할 수 있었으나 뭔가 스코어보드 구경이 이제는 그닥 재밌지는 않네요. 역시 문제를 만들어내는 순간이 제일 즐거운 것 같습니다. 넥슨에 도착한 뒤 드디..

A에서는 디버깅에, B에서는 코딩에 시간을 쓰는 바람에 C를 대회 중에 해결하지 못해 아쉽습니다. 하지만 991등으로 마무리하여 티셔츠는 받게 되었습니다. 대회를 잘 봤는지와 무관하게, C번 문제가 꽤 흥미로워서 풀이를 남겨 놓고자 합니다. 우선, 문제 상황은 다음과 같습니다. 정점이 $N$개인 트리가 주어집니다. 각 정점 $v$에는 $M_v$개의 문자열이 주어집니다. 트리를 여러 개의 경로로 분할하되, 각 경로에 문자열 $s$가 포함되게 할 수 있다면 $s$는 mutually-learned 합니다. mutually-learned 한 문자열의 개수를 세는 것이 문제입니다. 모든 TC에 대해 $N$의 합은 $3\cdot 10^6$을 넘지 않습니다. 모든 TC에 대해 $\sum M_v$의 합은 $8\cdot..

KOI는 Korean Olympiad in Informatics의 약자로, 한국 정보 올림피아드를 말합니다. 이 대회는 1차 대회와 2차 대회로 이루어져 있고, 1차 대회는 이산 수학을 바탕으로 하는 수학 문제들로 이루어진 1교시와 알고리즘 문제들로 이루어진 2교시로 나누어 진행됩니다. 자세한 정보는 koi.or.kr에서 확인하실 수 있습니다. koi.or.kr에 2교시 문제들의 풀이는 공개되어 있지만 1교시 문제들의 풀이는 제공하지 않아서 풀이를 작성했습니다. 팀원 찾기: 엄밀한 증명 고민 중... 1교시 풀이 문제의 지문은 링크에서 확인하실 수 있습니다. 또한, biko.kr에서 문제를 채점받을 수 있습니다. 다음은 각 문제에 대해 개인적으로 부여한 난이도와 실제 배점입니다. 1. 그래프의 지름 2...

개인적으로 백준에서 보는 것보다 pdf로 보는 게 더 편한 것 같다. 선발고사 문제 치고는 꽤 쉽다. 하지만 구현이 만만치 않다... 예제 속 그림을 보면 중요한 관찰이 눈에 쉽게 보인다. 바로 두 경로는 수직 구간 혹은 수평 구간을 정확히 하나 공유한다는 것이다. 이를 바탕으로 수평에 대해서 한 번 풀어주고, 수직에 대해서 같은 방식으로 한 번 풀어준다고 생각하고 한쪽만 고려해보자. 수직 구간을 공유한다면 수직 구간의 양 끝점을 기준으로 경로가 정확히 나뉜다. 이를 구간합 배열을 잘 이용하여 합쳐주면 된다. 솔직히 좋은 문제는 아니라고 생각한다... #include #define rep(i,a,b) for (auto i = (a); i = (a); --i) #define siz(x) int((x).si..

개인적으로 백준에서 보는 것보다 pdf로 보는 게 더 편한 것 같다. 한 자릿수 서브태스크 배점들을 보고 왜 이렇게 짜게 주나 했는데, 하나씩 풀다 보니까 기가 막힌 점수 배분인 것 같다. 부분 문제 1 ~ 4 풀이는 노드의 번호를 1-base 기준으로 작성했고, 부분 문제 5 풀이는 0-base 기준으로 작성했습니다. 궁금하신 점은 댓글로 남겨주시면 답변해 드리겠습니다! 문제 요약 "모든 $[i,j]$꼴의 정점 집합에 대해 만들어진 각 virtual tree의 가중치의 합을 구하라." 정도이다. 부분 문제 1 (5점) $N\le 300$이다. $O(N^3)$이 넉넉하게 돌아갈 수준이다. 모든 $[i,j]$를 직접 돌면서 dfs를 돌리면 된다. 웬만해서는 코드를 짜보려고 했는데, 점수 대비 구현량의 가성..

KAKAO BLIND RECRUITMENT는 문제의 지문 / 테스트케이스 / 풀이를 비상업적, 비영리적 용도로 게시할 수 있다. 광고가 노출되지 않는 블로그에 문제 풀이를 게시하는 것은 비상업적, 비영리적 용도이다. 출처: 프로그래머스 코딩 테스트 연습, https://school.programmers.co.kr/learn/challenges 2022년 09월 24일 14:00 ~ 09월 24일 19:00동안 테스트가 진행되었습니다. 이 글에 나와있는 문제 제목들은 실제 제목이 없어서, 제가 문제가 요구하는 요점에 맞춰 지은 제목입니다. 질문은 언제나 환영입니다. 그... 좀 귀찮아서 마지막 두 문제만 풀었습니다. UPD - 마지막 두 개만 풀었는데도 통과했네요.. 미로 탈출(300점) 예상 난이도: 골..