본문 바로가기

전체 글

(17)
폴리매스 제2회 코딩 챔피언십 풀이 및 후기 PMCC는 수학동아에서 운영하는 수학 사이트인 폴리매스에서 개최하는 코딩 대회로, 2020년 8월에 1회 대회가 열렸고, 2021년 2월에 2회 대회가 열렸습니다. 2회 대회는 1회 대회 때보다 더욱 다양해진 실력의 코더들을 위해 Division 1과 2로 나눠서 운영되었습니다. 준비 과정에서 CMS 서버를 세팅해 주신 whqkrtk04님, 문제 출제를 도와 주신 azberjibiou, blackking26, gunwookim님, 그리고 촉박한 검수 기한에도 불구하고 검수에 힘써 주신 16silver, ainta, gs18115, messi, TAMREF님께 감사의 말씀을 전합니다. 아래는 풀이 ppt 파일입니다. 작성을 도와주신 azberjibiou님과 blackking26님께 다시 감사의 말씀을 전합..
KOI 2020 고등부 후기 KOI 2020 본선 문제는 다소 쉬웠지만 문제의 질은 보통 이상이었던 것 같습니다. 예선 난이도가 상당히 극단적이었기 때문에 본선이 어떻게 나올 지 도저히 감을 못 잡았는데, 나름대로 만족스러운 성적을 얻어 좋습니다. 대회 시작 전 대회 시작 전, 여유롭게 codeblocks abbreviation 몇 개를 추가하고 간단한 프로그램을 만들어 실행시켜 봤는데, 실행이 되지 않았습니다. 당황한 나머지 python을 써야 하는 건가 잠시 고민했는데, 옆 컴퓨터로 옮겨서 실행해도 마찬가지였습니다. 그때 누군가 는 비표준 헤더라 사용할 수 없다는 사실을 알려 주었고, 그 뒤로 이 대회에서는 STL 자료구조 등을 쓸 때마다 그때그때 필요한 헤더를 include 하게 되었습니다. 여러모로 불편했지만 bits/std..
NYPC 2020 예선 풀이 문제들의 난이도가 작년보다 전체적으로 높았습니다. 1회차 문제부터 쉽지 않다고 느끼는 문제들이 등장했고, 2회차부터는 모든 문제를 푸는 것도 매우 힘들어졌습니다. 특히 2회차 문제에서부터 삼분 탐색과 이분 매칭이 나오는 것은 난이도에 상당한 변화가 생겼음을 의미합니다. 문제의 퀄리티도 작년에 비해 매우 높아졌습니다. 특히 3, 4, 5회차 문제들은 한 문제 한 문제가 깊은 고민을 해야 풀 수 있는 문제였던 만큼 매우 재밌었습니다. 연습 문제 1. 최대구간합 앞에서부터의 누적 합을 구해 주면서 답을 갱신해 나가면, $O(N)$에 풀 수 있습니다. 유명한 문제이므로 간단하게 설명했습니다. #include using namespace std; typedef long long ll; int n; ll arr[1..
[초급] 그래프 이번 게시글에서는 그래프가 무엇인지에 대해서 살펴보겠습니다. 그래프 그래프는 정점들이 간선들로 연결되어 있는 형태를 말합니다. 여기서 정점은 교차로와 비슷한 개념이고, 간선은 도로와 비슷한 개념입니다. 왼쪽과 같은 그래프에서 정점은 총 6개이고, 간선은 총 8개입니다. 오른쪽 그래프에서 정점은 총 8개이고, 간선은 5개입니다. 간선에 방향이 있는 그래프를 유방향 그래프, 방향이 없는 그래프를 무방향 그래프라고 합니다. 위에 있는 그래프는 모두 무방향 그래프입니다. 아무 두 정점이나 잡았을 때, 간선을 통해 오고 갈 수 있다면 연결 그래프(connected graph)라고 합니다. 연결 그래프가 아닌 그래프(disconnected graph)에서, 간선을 통해 서로 오고 갈 수 있는 점들의 집합을 연결 성..
[초급] 비트마스크 이 글에서는 이진법의 성질을 이용해 문제 풀이를 쉽게 해 주는 기법인 비트마스크(Bitmask)에 대해 배워 보겠습니다. 이진법 대부분 아시겠지만, 먼저 이진법에 대해 간단하게 정리해 봅시다. 우리가 사용하는 수는 십진법입니다. 십진법은 0에서 9까지의 숫자를 이용해서 어떤 정수라도 표현할 수 있습니다. 컴퓨터는 이진법을 사용하는데, 이진법은 0과 1만으로 모든 수를 표현합니다. 십진법 수의 맨 오른쪽 자리는 일(1)의 자리입니다. 그 왼쪽 자리는 10의 자리이고, 한 칸 더 왼쪽으로 가면 $10^2 = 100$의 자리입니다. 이진법도 마찬가지입니다. 맨 오른쪽 자리는 1의 자리, 그 왼쪽 자리는 2의 자리이고, 계속 한 칸씩 왼쪽으로 갈수록 4의 자리, 8의 자리와 같이 커집니다. 간단한 예시로, 십진..
[초급] 백트래킹 이번에는 백트래킹에 대해 배워 보겠습니다. 백트래킹 백트래킹(Backtracking)은 모든 경우를 계산해 보는 기법을 말합니다. 비슷한 의미의 단어로 브루트 포스(Brute Force)가 있습니다. 여기서는 가장 일반적으로 사용되는, 재귀 함수를 이용한 백트래킹을 다루겠습니다. 백트래킹의 가장 중요한 개념은 막히면 되돌아간다라는 개념입니다. 이해를 돕기 위해 가장 대표적인 예시인 N-Queen 문제를 살펴봅시다. N-Queen 문제는 $N \times N$ 크기의 체스판에 $N$개의 퀸을 서로 공격할 수 없게 배치하는 문제입니다. 체스 문제 같아 보이지만, 이 문제를 여기서 설명하는 이유는 바로 이 N-Queen 문제가 유명한 NP 문제 중 하나이기 때문입니다. 아래 배경 지식은 읽으실 분만 읽고 넘어..
[초급] 정렬 이 글에서는 가장 쉬운 알고리즘인 '정렬'에 대해서 배워 보겠습니다. 정렬이란? 정렬은 여러 가지 데이터를 정해진 순서대로, 일반적으로 작은 것이 먼저, 큰 것이 나중에 오게 배열하는 것을 말합니다. 정렬을 하기 위해서는 어떤 데이터를 앞에 놓아야 할 지에 대한 비교 기준이 있어야 합니다. 예를 들어, 배열 [1, 4, 8, 7, 3]이 있고, 이 배열을 크기 순서대로 오름차순으로 정렬한다고 할 때, 정렬 결과는 [1, 3, 4, 7, 8] 이 되는 것입니다. 이렇듯 정렬의 개념을 받아들이는 것은 어렵지 않습니다. 정렬을 하고자 할 때, 데이터를 비교할 비교 기준은 중요한 성질을 만족해야 합니다. 어떤 비교 기준에 의해 비교했을 때 a가 b보다 작으면 ab라고 합시다. (같은 경우는 일단 ..
알고리즘 게시글 작성 계획 이 게시판에서는 알고리즘이나 자료구조 등을 소개할 계획입니다. solved.ac 위키에 추가하기로 예정되어 있었던 문서 목록을 조금 다듬었습니다. 초급 정렬 백트래킹 비트마스크 그래프 자료구조 DFS, BFS 이분 탐색 삼분 탐색 그리디 누적 합 DP 기초 중급 오일러 회로 트리 위상 정렬 유니온 파인드 최소 신장 트리 최단 경로 알고리즘 SCC BCC Sparse Table LCA 조합론 스위핑 분할 정복 Segment Tree Binary Indexed Tree Lazy Propagation KMP Trie Manacher Z 벡터와 CCW 볼록 껍질 Rotating Calipers Sqrt decomposition Mo's Merge Sort Tree 에라토스테네스의 체 잉여역수 확장 유클리드 알고..