-
이동하기 4 (BOJ 18796)
이 글은 BOJ 18796 (이동하기 4)의 풀이를 다룹니다. 현재 이 문제의 solved.ac 티어는 루비 5입니다. 이 문제의 흥미로운 점은 지문이 거의 똑같은 문제가 무려 22티어나 낮은 브론즈 2라는 것입니다. 두 문제의 차이는 네 글자뿐이지만, 이는 x 방향으로 이동하는 비용이 x 좌표가 아니라 y 좌표에 의존하게 된다는 매우 치명적인 차이입니다. (물론 y 방향도 마찬가지입니다.) 60 +---+---+---+ +60-+60-+60-+ | | | | 10 90 80 70 20 +---+---+---+ +20-+20-+20-+ | | | | 10 90 80 70...
-
루트로 문제 뚫기
서론 수준급의 알고리즘 문제를 풀다 보면 다양한 장벽에 가로막히곤 합니다. 어려운 문제들 중에는 특히 쿼리형1의 문제가 많은데, 이런 문제들은 단순한 방법으로 답을 도출해내는 것은 쉽지만 시간 복잡도를 줄이는 데에 복잡한 자료구조가 요구되어 난이도가 매우 높아지는 경우가 많습니다. 이러한 문제들의 의도는 주로 특수한 형태의 트리2나 이분 탐색 등을 활용하여 $O(Q\log^K{N})$ 꼴의 시간 복잡도를 만들어내도록 하는 것이지만, 일부 문제의 경우 $O((N+Q)\sqrt{N})$과 같이 루트가 시간 복잡도에 포함되는 것이 정해인 경우도 있습니다. 대표적인 것이 이전에 소개한 바 있는 Mo’s...
-
알고리즘 동아리 방학 모의고사 운영
세미나 운영에 대한 회고 알고리즘 동아리 운영에 있어 세미나를 어떻게 진행해야 할지는 정답이 없는 문제입니다. 너무 양이 많으면 기죽는 회원들이 생기지만 너무 적으면 세미나인지도 모호합니다. 난이도를 보아도 너무 어려우면 진입장벽이 생기고 너무 쉬우면 숙련자들에게 큰 의미가 없습니다. 종강이 다가올수록 줄어드는 관심 또한 문제이며, 방학 때는 정말 좋아하는 사람이 아니고서야 별도의 공부를 하지 않는 경우가 많습니다. 제가 회장으로 있는 알고리즘 동아리인 AlKor도 예외는 아니어서, 방학 때 별도의 세미나를 진행하지 않았습니다. 비록 일부 회원들이 ‘숭고한 알고리즘 캠프’에...
-
problem solving 1
문제풀이를 하면서 재미있었던 문제를 소개하고자 간단하게 문제 설명과 풀이를 작성해보았습니다. Min Max Convert (SEERC 2018) $N (N \leq 100,000)$개의 숫자를 가진 배열 $A, B$가 주어질 때, 2가지 쿼리를 이용하여 $A$ 배열을 $B$ 배열로 만들 수 있으면 해당 쿼리를 출력하고 불가능하면 -1을 출력하는 문제입니다. 그리고 가능한 경우에는 쿼리를 $2*N$ 번 이하로 사용해서 만들어야 합니다. 첫번째 쿼리는 $[a, b]$ 구간의 숫자들을 모두 해당 구간의 최대값으로 변경하는 쿼리고, 두번째 쿼리는 $[a, b]$ 구간의 숫자들을 모두 해당 구간의 최소값으로...
-
Counting the number of topologies on a finite set
Topology 수학에서, topological space란 다음 조건을 만족하는 집합 $X$와 $X$의 subset들의 collection $\tau$에 대해 ordered pair $ (X, \tau) $ 를 말한다. $ \phi, X \in \tau $ Any arbitrary union of members of $ \tau$ still belongs to $ \tau$. ($ \tau$의 원소들의 합집합은 $ \tau $의 원소이다) The intersection of any finite number of members of $ \tau$ still belongs to $ \tau$. ($ \tau$의 원소 유한개의 교집합은 $ \tau $의 원소이다) 이때...
-
PS Training 2
안녕하세요, 이번 달에도 Problem Solving 관련 글을 쓰게 되었습니다. 최근에는 참가한 대회가 없지만, 연습 과정에서 만난 문제들 중 괜찮은 문제들을 추려 모아 보았습니다. 이번에도 문제의 풀이와 소스 코드, 링크 등을 정리합니다. Circling Round Treasures Codeforces Round #221 (Div. 1)의 C번 문제입니다. $N * M$ 격자 그리드 안에 다음과 같은 것들이 놓여 있습니다. 폭탄 빈 칸 보물 장애물 주인공은 주어진 어떤 시작점에서 출발해, 상하좌우 중 빈 칸으로 이동할 수 있습니다. 이동하는 데는 1원이 듭니다. 이동을 마치고...
-
AtCoder Regular Contest 075 C Meaningful Mean 풀이
문제 요약 문제 링크 $N$개의 수가 있다. $i$번째 수를 $a_i$라 하자. 수열 $a$의 $N$개의 수에서 연속한 수들을 고르는 방법의 가지수는 $\frac{N \times (N+1)}{2}$ 개이다. $\frac{N \times (N+1)}{2}$ 개 중에서 평균이 $K$ 이상인 것이 몇개인지 구하라. $ 1 \le N \le 2 \times 10^5, 1 \le K \le 10^9, 1 \le a_i \le 10^9 $ 풀이 1. $O(N^3)$ Naive 한 방법. $\frac{N \times (N+1)}{2}$ 개의 모든 경우에 대해서, 직접 합을 구하고 평균이 $K$ 이상인지를 확인한다. 2....
-
AtCoder Grand Contest D Median Pyramid Hard 풀이
문제 요약 문제 링크 $N$층의 피라미드가 있다. $i$번째 층에는 $2i - 1$개의 칸이 있다. 피라미드의 $N$층에 $1, 2, \cdots, 2N-1$을 적절히 섞은 순열이 쓰여 있다. $1$층 부터 $N-1$층 까지의 칸에 숫자를 채우는 규칙은, 그 칸에 있는 수가 그 칸 아래쪽에 있는 $3$개의 수의 중앙값이라는 것이다. 위 방법에 따라 피라미드를 채웠을 때, $1$층에 있는 칸에 쓰인 숫자를 구해라. $ 2 \le N \le 10^5 $ 풀이 1. $O(N^2)$ 규칙에 맞춰서 모든 칸의 값을 구해본다. 공간복잡도가 $O(N^2)$라고...
-
PS Training 1
안녕하세요, 저번 달에 이어 다시 Problem Solving을 주제로 글을 쓰게 되었습니다. 최근에는 이렇다 할 연습을 따로 하지 않았는데, 한국인 problem setter가 준비한 코드포스 라운드도 있었고, SCPC 등을 이유로 조금씩 테크닉을 연습한 문제 등이 있어 모아 쓰게 되었습니다. 지난번엔 코드포스의 div1C 수준 정도의 문제를 다루었지만, 이번에는 div1B~div1C 수준의 문항에 대해 다룰 예정입니다. 각 문제의 디스크립션, 풀이, 그리고 풀어볼 수 있는 링크를 정리합니다. White Lines Codeforces Round #578 (Div.2)의 D번 문제입니다. https://codeforces.com/contest/1200/problem/D 한국의 PS 유저인 jwvg0425님과 djm03178님이...
-
프로그래밍 대회를 개최하기 위한 10가지
프로그래밍 대회를 개최하기 위한 10가지 이 글은 Ajou Programming Contest(2016-19 APC), 경인지역 6개대학 연합 프로그래밍 경시대회(2016-19 shake!), 전국 대학생 프로그래밍 대회 동아리 연합 여름 대회(2016 UCPC)를 운영했던 제 경험을 토대로 작성되었습니다. 프로그래밍 대회를 개최하려는 분들께 조금이나마 도움이 되었으면 하는 마음으로 대회를 맡으며 경험했던 시행착오를 모아 필요한 10가지를 정리해보았습니다. 어디까지나 제 개인의 경험에 기반한 내용으로 대회를 열기 위해서는 이래야 한다!가 아닌 아래 과정을 고려해보자는 의미로 읽어주시면 좋겠습니다. 일의 진행 순서로 나열하긴 했지만 모든 과정은 유기적입니다. 대회의...
-
Red Army 1
안녕하세요, 반갑습니다. 소프트웨어 멤버십 블로그에 글을 쓰는 것은 처음이네요. 서울대학교의 Problem Solving 동아리 SNUPS에서 봄학기동안 열린 스터디 red army에서 선별한 문제 풀이를 연습하던 중, 재미있는 문제가 몇 개 있어 문제와 풀이, 그리고 풀이 코드를 소개하려 합니다. 모두 코드포스(https://codeforces.com/)에 수록된 문제이며, div1 C 정도의 난이도입니다. Cutting Rectangle Thinkoff Internship Warmup Round 2018 and Codeforces Round #475 Div.1의 C번입니다. (https://codeforces.com/contest/963/problem/C) 가로 길이가 A, 세로 길이가 B인 직사각형이 하나 있습니다. 이 직사각형을 가로로 몇 번, 세로로 몇 번...
-
2019 SCPC Round 2 5번 풀이
문제 요약 $M \times M$ 격자판에 $N$ 개의 점이 찍혀 있다. 각 점에 대해서, 그 점은 왼쪽 아래로 하는 가장 큰 정사각형을 그리려 한다. 단, 정사각형은 $N$ 개의 점중 어떤 점이라도 내부에 포함시키면 안된다. 모든 점에 대해서 정사각형을 그릴 때, 모든 정사각형 변의 합을 구하시오. $2 \le M \le 10^9$, $1 \le N \le 500000$ 풀이 1. 먼저 2D Range Tree 를 써서 특정 직사각형 구간에 점의 개수를 $O(\log^2 N)$ 시간에 알 수 있다. 여기에...
-
문제 출제를 위한 플랫폼 - Polygon 사용하기
Polygon이란? Polygon이란 Codeforces에서 제공하는 Competitive Programming Contest를 위한 문제 출제를 위한 플랫폼입니다. 출제를 위해 필요한 과정 - 데이터 제작, 검증, 솔루션 검증 등에 굉장히 유용한 기능들이 많으며 그 과정을 다른 사람과 공유하며 협업할 수도 있습니다. 폴리곤에서의 작업은 각 문제 단위로 동작합니다. 문제를 등록하는 방법부터 완성된 문제를 패키지로 다운받는 방법까지, 필요한 기능들을 간략히 확인하고 언제 어떤 메뉴를 사용해야 하는지 문제 출제 단계에 따라 익혀봅시다. 아, 그 전에 회원가입은 다들 하셔야겠죠? 문제 등록하기 폴리곤에 로그인하면 아래와 같은...
-
그룹 road to grandmaster 둘러보기
어느 ELO 레이팅이 안 그러겠냐만은, grandmaster라는 칭호는 세계적인 실력자에게 주어지는 칭호입니다. 가장 유명하고 세계적인 Competitive Programming(CP) 플랫폼인 Codeforces에서는 레이팅 2400 이상일 경우 grandmaster로 인정받으며, 닉네임이 붉은 색으로 변합니다. 한국 PS계에서는 이들을 ‘레드’라고 부르기도 합니다. 레드가 어느 정도 수치인지 대략적으로 가늠하자면, 2019년 5월 7일 기준으로 최근 6개월간 rated 대회를 친 사람 중 전 세계에 352명밖에 없습니다 (한국에선 16명). 국내 수준급의 프로그래밍 경시 대회의 대략적인 최소 입상 수준이 레이팅 1900-2100 (통칭 ‘퍼플’)이라는 점을 고려하면 단순히 닉네임에서 빛나는...
-
청개구리
청개구리는 2004년 한국정보올림피아드 지역본선에서 가장 어려운 문제인 고등부 5번으로 출제된 문제이다. 일단 국내 대회의 기출 문제이고, 문제 내용도 어렵지 않고 입력되는 값의 범위도 작아서 많은 사람들이 관심을 갖고 해결을 시도해 왔다. 하지만 오랜 기간 동안 그 누구도 맞았습니다!!를 받지 못했고1, 문제나 데이터가 잘못되었다는 의문을 제기하는 사람도 적지 않았다. 그러나 2018년 4월 본인을 포함해 두 명의 맞은 사람이 나오면서 문제에는 이상이 없는 것으로 밝혀졌고 이 문제는 Baekjoon Online Judge에서 가장 신비로운 문제의 대명사가 되었다. 이 문제의...