leo020630의 블로그

최근에 참여한 백준 대회 3개에 대해서 간략한 후기를 작성하려 한다. Good Bye, BOJ 2021 A. 2021은 무엇이 특별할까? (1 try, 00:02) 실버 하위 난이도의 구현 문제라 가볍게 구현해주었다. B. 예쁜 케이크 (1 try, 00:08) 언뜻 보았을 때 Hard한 소인수분해 알고리즘이 필요해 보여서 당황했지만, 식을 잘 들여다보니 답이 될 수 있는 경우는 \(9k\) 또는 \(3k+2\) 꼴이라는 것을 알 수 있었다. C. 성싶당 밀키트 (1 try, 00:18) 최근에 코드포스에서 파라메트릭 문제를 많이 보아서인지, 보자마자 파라메트릭이라는 것을 떠올릴 수 있었다. 오버플로우 처리가 약간의 issue였으나, 오버플로우가 생길 만한 범위라면 어차피 답이 되지 못해 상관없는듯 하다..

첫 개최까지 사실, 내가 고등학교에 입학하던 2018년 즈음까지도 고등학교에서 교내 알고리즘 경진대회를 연다는 것은 흔한 일이 아니었다. BOJ에서 자체적으로 설정한 기준이 있다는 점에서도 알 수 있듯이, 문제를 새로 만든다는 것은 굉장한 노력과 경험을 요구한다. 고등학교 수준에서 이를 만족하는 학생 또는 졸업생이 한 학교에 몇 명 이상 있는 것은 소수의 학교를 제외하면 정말 어려운 일이라고 생각한다. 하지만 몇년 사이 교내 알고리즘 대회를 개최하는 고등학교들이 많이는 아니지만 생겨나기 시작했고, 나를 비롯한 경기북과학고등학교 알고리즘 동아리 ALPS 구성원들도 이를 의식하고 있었다. 2021년 결산 글에서 GCC를 2018년부터 시작한 대회라 한 바 있는데, 2018년~2019년에는 백준 그룹의 연습 ..

서론 사실, 이 블로그는 여름방학쯤 가볍게 시작했다 몇 달간 방치하고 있었습니다. 연말이기도 하고, 올해를 정리하는 겸 블로그도 다시 시작해보려 합니다. 결산이라는 글 취지에 맞게, 1월부터 12월까지 시간 순으로 있었던 일들을 돌아보도록 하겠습니다. 입시의 끝 저는 현재 20살, 21학번으로 COVID-19 상황 하에서 대학교 입시를 치르는 첫 학번이었습니다. 여러 사건들 탓에 저의 입시는 해가 바뀐 후에야 끝이 나게 되었고. 결과부터 말하자면 POSTECH에 입학하게 되었습니다. 합격한 다른 대학들이 있었지만, 올해 초 당시에는 PS 생각을 크게 하지 않고 있었기에 붙은 대학들 중 다방면으로 가장 괜찮다고 생각한 POSTECH을 선택했습니다. 1학기 1학기 초, POSCAT이라는 POSTECH의 알고..

A. The Miracle and the Sleeper (00:02, +) \(r%max(l,r/2+1)\)이 답이다. B. Scenes From a Memory (00:12, +) 관찰을 통해 자리수를 무조건 2이하로 만들 수 있다는 것을 알 수 있다. 이를 토대로 나이브하게 구현하면 된다. C. Rings (00:43, +1) 다음과 같은 관찰이 필요하다 : 어떤 이진수의 앞이나 뒤에 0을 붙여도 주어진 조건을 만족한다. 따라서, 주어진 문자열에 0이 하나라도 포함되어 있으면 더 긴 쪽으로 연결시켜 주면 된다. 전부 1인 경우엔 \([1,n-1]\)과 \([2,n]\)을 호출하는 방법과, \(n\)이 짝수인 경우에 길이가 \(n/2\)인 수가 약수가 된다는 점을 이용하는 방법 등 다양한 풀이가 존재한..

A. There Are Two Types Of Burgers (00:04, +) 더 비싼 버거를 최대한 많이 만들어준 후 남은 빵으로 다른 버거를 만들어주는 것이 최적이다. B. Square Filling (00:08, +) 그리디하게 칠해준 후 두 배열이 같은지 확인하면 된다. C. Gas Pipeline (00:31, +) 길이가 2이상인 0을 만날때 마다 비용이 더 적은 경로로 이어주면 된다. D. Number Of Permutations (00:50, +) 전체 경우의 수인 \(N!\)에서 첫 배열로 정렬할 수 있는 경우와 둘째 배열로 정렬할 수 있는 경우를 빼준 후, 둘 모두로 정렬 가능한 경우를 더해주면 된다. 각 경우는 연속된 같은 수의 갯수만큼 팩토리얼을 해주면 구할 수 있다. E. XOR..

A. Simply Strange Sort (00:07, +) Div2 A답지 않은 구현 문제이다. 구현이 어렵진 않기 때문에 문제에서 하라는 것을 해주면 된다. B. Charmed by the Game (00:20, +) \(|a-b|/2\)의 값을 이용해 잘 탐색해주면 된다. 나는 머리가 안돌아가서 무지성으로 구현했다.. C. Deep Down Below (00:32,+) 각 동굴마다 \(A_i-i\)의 최대값을 저장해 준 후, 이를 기준으로 정렬한 후 파라메트릭 서치를 진행하면 된다. 이분탐색을 하지 않고도 답을 구할 수 있다 한다. D1. Up the Strip (01:06, +2) \(floor(N/i)\)의 값이 \(O(sqrt(N)\)개라는 것을 이용하면 \(O(Nsqrt(n))\)에 문제를 ..

A. Creating a Character (00:06, +1) \(max(0,min(exp+1,(str-int+exp+1)/2)\)가 답이다. B. Zmei Gorynich (00:14, +) 가장 효율이 좋은 무기를 사용하다 가장 공격력이 높은 무기로 마무리하면 된다. C. The Number Of Good Substrings (00:39, +) 관찰을 해보면, leading zero의 개수에 따라 해당되는 수가 최대 2개임을 알 수 있다. 따라서, 연속되는 0의 개수를 체크하다 1을 만났을때 가능한 수를 모두 체크하면 \(O(N)\)에 문제를 해결할 수 있다.

A. Dial Up (00:18, +1) *442 제자리에서 계속 더하다 처음 다른 값이 나오면 가장 가까운 곳으로 이동하고, 이후에는 나오는 값에 따라 1이나 2를 더해주면 된다. 불가능한 경우 처리는 쉬우니 생략하도록 하겠다. B. Squares (00:54, +) *1273 \(1\)부터 \(sqrt(N)\)까지는 모든 경우가 되므로 다 더해준다. 그러면 각 \(x\)당 가능한 \(y\)의 개수가 \(O(sqrt(N))\)개가 된다. 따라서 각 경우에 대해 구간의 길이를 곱해 더해주면 된다. C. LIS to Original Sequence (01:42, +4) *1896 다음과 같은 과정을 따른다. LIS의 원소를 \(A_1..A_k\)라 했을때 (1) \(i

A~B는 따로 적지 않겠다. C. One More aab aba baa (00:05, +) *178 next_permutation() 함수를 이용하면 쉽게 구현할 수 있다. D. Coprime 2 (00:37, +3) *736 에라토스테네스의 체의 메커니즘을 이용한다. 모든 \(A_i\)에 대해 소인수를 구해준 후, 구한 소인수들로 에라토스테네스의 체 배열을 채워주면 된다. \(O(Nsqrt(N)\)에 문제를 해결할 수 있다. E. Chain Contestant (00:84, +1) *1413 비트마스크 DP이다. \(DP[i][j][k]\)를 \(i\)번째까지의 원소를 이용해 집합 \(j\)에 해당하는 색을 사용해 끝 색을 \(k\)로 하는 경우의 수로 정의하면 DP 갱신을 \(O(10 2^{10})\..

A. 2048 Game (00:03, +) 2048 이하인 수들을 모두 더했을 때 2048 이상이면 가능하다. B. Knights (00:05, +) 체크무늬로 칠한 배열을 출력하면 나이트가 갈 수 있는 칸의 색이 항상 달라지므로 최적이다. C. Perfect Team (00:18, +) \(min(c,m,(c+m+x)/3\)이 정답이다. D. Make The Fence Great Again (01:23, +3) 한 울타리에 대해 최대 2번까지만 높여주는 것이 최적임을 알 수 있다. 따라서 \(DP[i][j]\)를 \(i\)번째 펜스를 \(j\)만큼 올려줬을 때의 최소 비용으로 정의하면 \(O(N)\)에 문제를 해결할 수 있다.