나름 개발자의 IT블로그

(알고리즘보단 수학에 가까운 내용인데 백준문제 풀다가 나와서 알고리즘 카테고리에 정리하겠습니다.) 백준 문제 풀다가 재밌고 신기한 정리가 있어서 정리하고자 한다. 문제는 여기 https://www.acmicpc.net/problem/2710 2710번: 삼각형 정원 각각의 테스트에 대해 한 줄에 fx1, fy1, fx2, fy2, rl(fx1

오랜만에 코드포스 컨테스트 글을 올려보려고 한다. rated대회는 무서워서 못치겠고 버추얼을 돌리면서 실력을 키우고 도전하려고 한다.(그리고 파란색이 너무 예뻐서 유지하고 싶다.) Codeforces Round #811 (Div. 3) A - Everyone Loves to Sleep [Solved!] 현재 시간이 주어지고 $n$개의 시간이 주어질 때 현재 시간 이후의 시간 중 가장 빠른 시간과의 차이를 구하는 문제이다. 시간을 분으로 고쳐서 정렬한 후 완전탐색 해서 구하면 된다. 다만 현재 시간이 주어진 시간보다 뒤일 수 있으므로 주어진 시간중 가장 빠른 시간에서 $24 \times 60 = 1440$을 더해 맨 뒤에 추가한 후 탐색한다. B - Remove Prefix [Solved!] 앞에서부터 몇..

인생에서 마지막 UCPC를 후회없게 마무리했다. 최근 3개년 UCPC본선 문제를 확인해보니 한문제가 골드급이고 나머지는 플래급 이상이어서 한문제만 풀자라는 느낌으로 참가했는데 생각보다 쉬운 문제가 꽤 있어서 재미있게 풀었던 것 같다. 대회는 삼성 스페이스쉐어에서 진행됐고 티셔츠와 식사, 간식거리가 무한제공 되었다. 또한 많은 후원사의 기념품도 받아왔다. Before Contest 자리배치가 왼쪽같을 줄 알았는데 오른쪽모양 배치여서 살짝 부담스러웠다. 11시 시작이었지만 모종의 이유로 5분이 미뤄졌고 뭔가 앞에서 통제를 해야할 것 같은 분위기였는데 4분까지 아무 통제가 없어 어수선하다가 5분에 시작됐다. During Contest 00:00 문제가 12문제여서 각각 4문제씩 보기로 하고 내가 A~D를 읽기..

지난 UCPC 2022에 PBDS가 나왔다. 몰랐던 자료구조니까 공부하긴 했는데 이게 생각보다 강력한 것 같다. C++에서 지원하는데 이게 있으면 세그트리를 안짜도 된다.(근데 짜는게 맘편하긴 하다.) 감사한 곳 https://codeforces.com/blog/entry/11080 C++ STL: Policy based data structures - Codeforces codeforces.com 일단 g++에서만 가능하다고 한다.(unfortunately only for the GNU C++) 개념적으로는 set(map)인데 순서를 기록한다고 한다. 특정 수가 몇번째로 큰지, 특정 수보다 작은 수가 몇개 있는지를 구할 수 있는 내장 자료구조이다. 사용하려면 헤더를 따로 인클루드 하고 네임스페이스도 쓰..

건국대학교에서 만난 훌륭한 실력을 가진 팀원들과 함께 UCPC를 참가하였다. 다들 실력이 좋으셔서 5솔이라는 좋은 성적을 거두었다. 팀원 : riroan, aru0504, kth990303 Before Contest 예비소집 문제에서 최근 UCPC에서 A번이 가장 쉽다는 힌트를 주었다. 그래서 올해도 A가 가장 쉬울 것으로 예상해서 누가 A를 풀지 정해야 했는데 kth990303님이 풀겠다고 했다. 어려운 문제도 붙잡고 있는 스타일이어서 확실하게 풀 수 있는 A를 빠르게 풀고 그동안 나와 aru0504님이 다른 문제를 보기로 했다. 나는 대회에서 문제를 딱 보고 10초 안에 풀이가 떠오르지 않으면 넘기는 성격이라 모든 문제 파악하는게 더 좋았는데 잘 된것같다. 00:01 A solve! 대회 시작 후 몇..

우리는 문제를 풀거나 프로그래밍을 할 때 map(unorderd_map), dict을 쓰곤 한다. 키에 무엇이든 넣을 수 있어 편리한 자료구조이지만 사용 시 조심해야 할 부분이 있는 것 같아 포스팅하게 되었다. 감사한 곳 https://codeforces.com/blog/entry/101817 Anti-hash-table test in Python - Codeforces codeforces.com 시간복잡도 기반 python dict(defaultdict) $O(1)$ 해시 C++ map $O(\log{n})$ RB Tree C++ unordered_map $O(1)$ 해시 우선 차이는 위와 같다. dict이랑 unordered_map은 같은 해시 기반이다. 위 표만 보면 $O(1)$이기 때문에 dict..

지금까지 고속푸리에변환(이하 FFT)의 원리를 잘 모르고 썼는데 오늘 각잡고 공부해서 깨달았다. 아직 완벽히 이해한건 아닌것 같지만 잊어버리기 전에 남겨놓고자 한다. (쓰다보니 길어져서 파트를 나누었다. part1은 필요한 지식, part2에 FFT 원리에 대해 포스팅한다.) 감사한 곳 https://codeforces.com/blog/entry/43499 https://codeforces.com/blog/entry/43499 codeforces.com FFT는 다항식을 빠르게 계산하는 알고리즘이다. $A(x) = \sum_{i=0}^{n-1} a_ix^i, B(x) = \sum_{i=0}^{n-1} b_ix^i$일 때 $C(x)=A(x)B(x)$를 빠르게 구하는 알고리즘이다. 그냥 단순 알고리즘으로 구..

전설로만 존재하는 줄 알았던 div. 4가 열린다길래 다른 일 다 뒤로 하고 보러 왔다. 난이도는 백준 기준으로 브론즈 4 ~ 실버 2? 정도 되는 거 같다. 가장 비슷한 사람의 퍼포를 보니 1800 정도 나오는 거 같다. A - Division? [Solved!] 레이팅에 따라서 조건에 해당하는 Division을 출력하는 문제이다. if문을 빠르고 정확하게 타이핑하자! B - Triple [Solved!] 주어진 배열에서 같은 수가 3개 이상 나오는 수가 있는지 출력하는 문제이다. 파이썬 기준으로 Counter, dict, list 등을 사용해 배열에 존재하는 숫자의 개수를 세고 3개 이상이 있다면 출력하면 된다. C - Odd/Even Increments [Solved!] 배열이 주어질 때 다음 연산..

C까지 30~40분 안에 풀면 블루 갈 수 있을거 같다. (최대한 틀리지 않고) D부터는 너무 벽이 느껴진다.. A - Game [Solved!] 1인 땅은 밟을 수 있고 0인 땅은 밟을 수 없다. 인접한 땅은 무료로 여러번 이동할 수 있고 그렇지 않은 경우 1회에 한해 $x$코인을 소비하여 $x$만큼 건너 뛸 수 있다. 이때 처음부터 끝까지 가는데 드는 코인의 최솟값을 구하는 문제이다. 0이 없으면 0원, 아니면 가장 왼쪽에서 처음나오는 0의 위치를 가장 오른쪽에서 처음 나오는 0의 위치에서 빼고 1을 더한값이 답이된다. (여론이 안좋은 문제) B - Game of Ball Passing [Solved!] $a_i$를 $i$번째 선수가 패스를 하는 횟수라고 할 때 모든 선수가 패스를 하려면 몇번의 경기..

요즘 빠른 3솔을 목표로 하고 있는데 이번은 C에서 너무 막혔다. A - Square Counting [Solved!] $n+1$개의 수 $a_1, a_2, ..., a_n, a_{n+1}$이 주어질 때 $0\le a_i < n$이거나 $a_i = n^2$을 만족한다. 그리고 $\sum_{i=1}^{n+1} a_i = s$를 만족하는 $a_i = n^2$의 개수를 구하는 문제이다. $s$에 $n^2$을 최대한 많이 넣으면 된다. 이를 구하려면 $\lfloor \frac{s}{n^2} \rfloor$을 계산하면 된다. B - Quality vs Quantity [Solved!] 수열 $a_1, a_2, \dots, a_n$이 주어지고 각 수를 빨간색, 파란색, 색칠하지 않음 중 하나의 상태로 만들 때 빨간..