leo020630의 블로그

전날 있던 Div. 2에서 2095->1943이라는 기염을 (또) 토한 터라 멘탈이 좋지는 않았다. Div. 1에서 오른 적이 거의 없던 터라 좀 무섭기도 했고.. 그래도 레이팅이 엄청 낮아져 있었기 때문인지 어떻게 오르긴 한 것 같다. A. Weird Sum (00:38, +) Div. 1에서의 흥망을 가르는 요인은 A라고 생각한다. 그리고 나는 대부분의 Div. 1에서 A만 보면 뇌가 굳는다. 이번 역시 그랬다. 스코어보드는 10분만에 초록색이 쫘르륵 깔리는데 나는 감이 하나도 안 왔다. 30분을 넘게 생각한 후에야 정해도 아닌 \(O(NsqrtN)\) 시간복잡도의 풀이를 찾아서 해결할 수 있었다. 이때만 해도 엄청 망할줄 알았다. B. Integral Array (01:01, +1) 문제를 처음 봤..

방학에는 시간이 남아돌아도 코포 정도만 치고 PS를 그렇게 열심히 하지는 않았는데, 최근에 코포가 없기도 했고 개강을 하니까 갑자기 문제가 풀고 싶어졌다. 마침 solved.ac 다이아 4 + 900솔브를 동시에 달성할 수 있을 것 같아서 최근 3일정도를 투자해 티어를 올렸다. 엄청나게 열심히 푼 것은 아니고, 풀이를 알고 있던 웰노운 다이아 몇 개(1557+8464, 13310, 2803)랑 랜덤으로 돌려서 나온 플레 몇 개를 풀었더니 점수가 쭉쭉 올랐다. 말은 쭉쭉 올랐다고 하지만, 솔브드 티어 올리는거도 참 쉬운게 아닌 것 같다. 여기서 100점을 더 올리려면 다이아5 문제를 기준으로 30개정도를 더 풀어야 할텐데, 솔직히 알고리즘 날먹이 아닌 이상 (다이아는 사실 알고리즘 날먹이어도 좀 어려운거 ..

오렌지를 처음 찍은 후부터 이 라운드 전까지 총 3개의 rated 라운드를 쳤다. 결과는 -81, -9, -115로 많이 좋지 않았다. 첫 라운드에서는 A에서 크게 말렸고, Div.2 C에 세그를 두개 박는 오버오버킬을 하고 나서야 해결할 수 있었지만 그 때는 이미 대회 시작 후 1시간이 지난 시간이었기 때문에 좋지 못한 결과로 대회를 마무리해야 했다.두번째 라운드는 비교적 평이하게 진행되었으나, C를 4번 틀리고도 해결하지 못한 점이 아쉬웠다. 화룡점정은 본 글에서 다루는 라운드 바로 하루 전에 진행된 컨테스트였다. Div.2 였음에도 불구하고 2솔로 대회를 마무리했다. 퍼포먼스는 무려 민트였으며, 그런 경험은 굉장히 오랜만일 뿐더러 C가 그렇게 어려운 문제도 아니었기 때문에 멘탈이 나간 주 원인이 되..

최근에 참여한 백준 대회 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)\)에 문제를 해결할 수 있다.