분류 전체보기20 Narayana number Dyck path는 $n \times n$ 격자에서 $(0, 0)$에서 출발해 $y = x$ 직선 위로 넘어가지 않고 $(n, n)$에 도달하는 경로를 의미한다. 이는 올바른 괄호 문자열, 정다각형의 삼각 분할 등과 일대일 대응되며, Dyck path의 경우의 수는 카탈랑 수로 잘 알려져 있다. 이때, Dyck path에서 $2k - 1$번 이동 방향이 바뀌는 경우에 대해서 생각해 보자. 시작은 R로, 끝은 U로 고정되어 있기 때문에 R에서 U로 바뀌는 경우가 $k$번이라 하면, U에서 R로 바뀌는 경우는 $k-1$번이다. R에서 U로 바뀌는 지점을 peak라 하겠다. 우리는 peak가 $k$개인 Dyck path의 개수를 세는 방법을 알아볼 것이다. 어떤 올바른 괄호 문자열 $s = s_1 \cdots.. 2026. 1. 6. 2025년을 보내며 보호되어 있는 글 입니다. 2025. 12. 27. 2025 ICPC Seoul Regional 본선 후기 11월 22일 BEXCO에서 열린 ICPC Seoul Regional에 참여하였다. 대회 전부터 여러 우여곡절이 많았지만 전체 17위, 국내 12위를 기록하여 장려상을 수상했다. Asia Pacific Championship 진출도 확정했다! 1. 팀 구성팀원은 jsj0412, gubshig으로 그대로다. 달라진 점은 jsj0412가 특이점에 도달해 코드포스 오렌지를 달성했다는 것 정도.이번 대회를 준비하면서 정했던 역할은 다음과 같다.gmroh06 - 애드혹, 구성적, DP, 그리디, 수학(?)jsj0412 - 기하, 문자열gubshig - 자료구조, 웰노운이러한 역할이 정해지는 것은 초반이 지나고 난 이후이다. 3명 모두 플래티넘 하위 이하는 막힘없이 풀기 때문에, 1시간 정도까지는 스코어보드를 보.. 2025. 11. 26. BOJ 14435 링크 내가 지금까지 풀었던 문제 중에 단연코 세 손가락 안에 들 정도로 정말 정말 좋은 문제라고 생각한다. 어떻게 이런 문제가 고등학교 교내 대회에 나왔는지 의문이다. 완전히 내가 푼 것은 아니고 업데이트 횟수를 줄이는 것이 핵심 아이디어라는 힌트를 보고 문제를 해결하였다. 이 문제는 자라는 키를 변화시켜서 온라인 처리를 강제했다. 따라서 나이브한 풀이를 생각해 본 후 최적화를 고민할 것이다. 모든 날짜에 모든 질문을 확인한다면 $O(KQ)$에 문제를 해결할 수 있다. 모든 질문을 확인하는 것이 비효율적이므로 가능한 후보들을 줄이는 방법을 고민해 보자. 두 아이의 키의 합이 $k$이상이려면 어떤 조건이 필요할지 생각해 보자. 둘 중 하나의 키는 $k \over 2$ 이상이어야 한다. 어쩌면 당연하게 보.. 2025. 9. 5. BOJ 11027 링크 5월에 gggkik와 랜덤으로 뽑은 문제를 풀다가 나온 문제이다. 장장 3일 동안 고민했을 만큼 매우 어려운 문제라고 생각한다. 여담으로 gggkik는 잠깐 고민하더니 모르겠다고 도망갔다.. 꽤 좋은 문제라고 생각해서 블로그 글을 작성하려고 했는데, 풀이를 설명할 엄두가 나지 않아서 이제서야 작성한다. 문제는 매우 간단하다. $swap$ 연산으로 선택 정렬을 구현한 의사 코드가 주어지고, $N$개의 수에 대해 $M$번째 원소까지 선택 정렬을 수행했을 때의 $swap$ 연산 횟수를 출력하면 된다. 먼저, 몇 번의 시뮬레이션을 통해 어떤 규칙이나 패턴이 있는지 파악해 보자. 어떤 $i$에 대한 연산이 일어나기 전 처음 수열과 마지막 수열을 비교해 보자. 전체 수열을 $A$, 연산에 참여한 수로만 .. 2025. 9. 4. 2025 숭고한 연합 알고리즘 경진대회 후기 ICPC 팀에서 팀원 1명은 운영진으로 참여했기 때문에 3인팀 대회지만 남은 1명인 준호(gubshig)와 참여했다. 어려운 자료구조나 웰노운 트릭들에 능통하다. 대회 중에 솔브 수가 적은 다이아 문제의 풀이를 다수 낸 적이 있고, 실제로 맞는 풀이였지만 항상 2% 모자란 구현 때문에 고생한다. 내가 DP나 애드혹, 구성적 같은 문제들을 주로 담당하고 준호가 자료구조, 웰노운, 그래프 같은 문제들을 주로 담당한다. 다만 문자열이나 기하학 문제들은 둘 다 싫어해서 팀노트 없이는 코딩도 못하는 수준이다. 팀명은 도피성 군휴학인데, 누구를 저격한다거나 하는 건 당연히 아니다. 다만 개인 닉네임을 제출했는데 스코어보드에 반영되지 않아서 아쉬웠다. 대회 전날, 당장 작성된 팀노트가 없어서 팀노트를 어떡할 거냐고 .. 2025. 9. 2. 이전 1 2 3 4 다음
