하바나바나나

안녕하세요, 올해로 두 번째 회고를 쓰게 되었습니다. 회고라기에는 많이 늦지만 연말에 이것저것 신경 쓸 일들이 많아 미뤄지게 됐네요. 그래도 1월 안에 쓸 수 있어서 다행이라고 생각해요. 회고를 쓰려고 생각한 시점에는 이번 한 해는 별 일 없이 무난히 보냈다고 생각했는데, 쓰려고 앉아보니까 생각보다 많은 일들이 있었던 것 같습니다. 전부 쓰기에는 무리가 있을지도 모르지만 최대한 기억나는대로 써보도록 하겠습니다. 보드게임컵 1월 14일, 한 해의 시작을 과 함께했습니다. 은 저번 회고에서도 언급이 되었는데, 제가 처음으로 개최하는 개인대회였습니다. 평소에 보드게임을 굉장히 좋아하기 때문에 이를 소재로 한 문제들을 만들고 대회를 준비하였습니다. 개인 대회라고는 하지만 제가 출제한 문제는 할리갈리, 크레이지 ..

4월 1일부터 4월 2일까지, 이틀에 걸쳐 구데기컵 ✕ solved.ac 카페 『먹었습니다!!』가 진행되었습니다. 다들 재밌게 즐기셨을까요? 블로그를 오래 방치하기도 했고, 기록을 남기면 좋을 것 같아 관련 회고를 써보려고 합니다. 혹시 비슷한 행사를 기획 중이신 분이 있다면 도움이 되면 좋을 것 같고요. 지나가면서 몇 번 이야기 하기는 했지만 어쩌다 이런 콜라보 카페가 세상에 나오게 되었는지, 준비 과정은 어떻게 되는지, 진행 입장에서의 소감은 어떤지가 궁금하신 분들이라면 재밌게 읽으실 수 있을 것 같습니다. 발단 구데기컵 가장 처음으로 거슬러 올라가자면, 어쩌다보니 구데기컵 운영진으로 참가하게 되었습니다. 사실 작년에도 시프트 님의 문제에 몇 가지 아이디어를 던져주고는 했는데 올해는 대회 페이지에 들..

안녕하세요, 슬슬 2022년도 마무리가 되어가는 만큼 한 해를 돌아보는 회고를 써보았습니다. 쓰는 이유는 별 거 없고... 주변 분들이 많이들 회고를 쓰고 계셨고, 블로그에 글을 올린지도 꽤 된 것 같아서 뭔가 올리고 싶었기 때문입니다. 목차가 필요할지 모르겠는데 다음과 같습니다. 전생했더니 2022년이었던 건에 대하여 PS러인데 알고리즘 문제해결을 할 수 없는 건에 대하여 저, 학점은 평균치로 해달라고 했잖아요 개발만 하는데 너무 어려움 대학원생이 되지 못한 나는 마지못해 취직을 결심했습니다 전생했더니 2022년이었던 건에 대하여 전생은 안 했지만 눈을 떠 봤더니 2022년이 되어 있었습니다. 시간이 정말 빠르다고 느꼈어요. 2021년에 뭐했는지 생각해보려고 했는데, 회고를 쓰지 않아서인지 떠오르가 않..

ICPC Asia Seoul Regional 2022에 스태프로 참가했습니다. 너무 바쁘고 정신 없어서 사진 찍은게 없다 보니 후기에 쓸 이야기도 많이 없습니다. 기억이 사라지기 전에 간략하게 써서 남기려고 합니다. 발단 10월 18일, 자소서를 쓰며 고통받던 저는 (당시에만 해도 우아한테크코스에 지원할 생각이었습니다. 어쩌다 보니 1주차까지만 하고 포기하게 되었는데, 관련해서는 언젠가 쓸 일이 있지 않을까요?) shiftpsh님의 연락을 받게 됩니다. ICPC 서울대회 진행 도우미를 모집한다는 연락이었는데, 전에 한 번 모집 공고가 뜨면 누구보다 빠르게 알려달라고 shiftpsh 님께 말씀드린 적이 있었습니다. 역시 제 기대를 배신하지 않는 shiftpsh 님 답게 누구보다 빠른 소식을 전해주셨습니다...

https://www.acmicpc.net/problem/15224 15224번: EvenOdd Consider the following function f(X), which takes a single positive integer as argument, and returns an integer. function f(X): iterations := 0 while X is not 1: if X is even: divide X by 2 else: add 1 to X add 1 to iterations return iterations It can be s www.acmicpc.net 어떤 정수 $x$에 특정한 연산을 반복해서 취할 때, $x$가 1일 될 때까지 취해야 하는 연산의 갯수를 $f(x)$라고 정의해..

https://www.acmicpc.net/problem/11562 11562번: 백양로 브레이크 서울 소재 Y모 대학교에서 대규모 공사를 진행하면서, 학교가 마치 미로처럼 변해버리고 말았다. 공사 이전까지는 어떤 건물에서 출발하더라도 다른 모든 건물로 갈 수 있는 길이 있었으나, 공 www.acmicpc.net 단방향 그래프가 주어지고 $M$개의 $u, v$가 주어질 때, 몇 개의 단방향 길을 양방향 길로 바꿔야 $u$에서 $v$로 갈 수 있는지 출력하는 문제입니다. 플로이드-워셜을 응용하면 해결할 수 있습니다. 단방향 간선의 경우 해당 방향으로 이동할 때는 바꿔야 하는 길이 없으므로 코스트가 0이라고 할 수 있습니다. 단방향 간선의 반대 방향의 경우 해당 방향으로 이동하려면 길을 하나 바꿔야 함으로 ..

https://www.acmicpc.net/problem/9567 9567번: Empty Stalls Farmer John's new barn consists of a huge circle of N stalls (2

https://www.acmicpc.net/problem/17299 17299번: 오등큰수 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다. www.acmicpc.net 어떠한 수보다 보다 등장 횟수가 많으면서 오른쪽에 등장하는 수를 구하는 문제입니다. 오른쪽에 등장하는 수라는 점에서 감을 잡을 수도 있는데, stack을 사용하여 등장 횟수의 내림차순으로 인덱스들을 관리해주면 됩니다. 스택의 위에 있는 인덱스보다 등장 횟수가 많은 수를 현재 보고 있을 경우, 현재 보고 있는 수가 해당 인덱스의 오등큰수가 됩니다. 이를 배열을 돌면서 실행해주면 각 수의 오큰수를 구할 수 있습니..

https://www.acmicpc.net/problem/1613 1613번: 역사 첫째 줄에 첫 줄에 사건의 개수 n(400 이하의 자연수)과 알고 있는 사건의 전후 관계의 개수 k(50,000 이하의 자연수)가 주어진다. 다음 k줄에는 전후 관계를 알고 있는 두 사건의 번호가 주어진다. www.acmicpc.net 딱 보면 위상정렬로 착각하기 쉬운 문제입니다. 위상정렬보다는 훨씬 쉬운 방법으로 풀립니다. 위상정렬을 하듯이 생각해보면, 어떠한 사건 $a$가 사건 $b$보다 먼저 일어났다는 것은, $a$에서 $b$로 가는 단방향 간선이 존재한다고도 생각할 수 있습니다. 모순되는 사건이 존재하지 않는다고 했으므로, 그렇게 구성된 그래프는 항상 DAG의 형태를 띄게 됩니다. 그래프를 구성한 후 해당 그래프에..

https://www.acmicpc.net/problem/16929 16929번: Two Dots 첫째 줄에 게임판의 크기 N, M이 주어진다. 둘째 줄부터 N개의 줄에 게임판의 상태가 주어진다. 게임판은 모두 점으로 가득차 있고, 게임판의 상태는 점의 색을 의미한다. 점의 색은 알파벳 대문 www.acmicpc.net 여러 알파벳으로 이루어진 2차원 격자가 주어졌을 때, 해당 격자에서 같은 알파벳으로 이루어진 길이 4 이상의 사이클이 존재하는지 판단하는 문제입니다. dfs로 cycle을 찾듯이 풀면 되는데, 한 번 방문한 점은 시작 지점이 아닌 이상 다시 방문하지 않도록 해야 합니다. 이를 구현하기 위해 시작 위치와 현재 위치, 그리고 몇 개의 점을 지났는지 기록하고 4개 이상의 점을 지났고 시작 위치..