25 Jun 2022
대면 대회?
대학에 오면 꼭 해보고 싶은 게 대면 대회였다. 그런데, 코로나 때문에 모든 대회가 비대면으로 진행되서 아직 단 한 번도 대면 대회를 참여해본 적이 없다. 풍선 달아주는 게 진짜 재밌어 보였는데, 정작 나는 한 번도 그런데 참가자로 참가해본 적 없이 대회 운영을 하게 되었다.. 아무튼 회의 때 7월 10주년 대회 준비 겸 2차 내전은 대면으로 하는 게 어떠냐고 물어봐서 시작된 대회였다. 운영진 중에서 거의 아무도 제대로 된 대면 대회 경험이 없다 보니, 정말 아무것도 모르는 상태에서 시작했다.
엄청나게 비싼 헬륨
풍선 70개 분량을 채우는 데에 7만원이 들었다. 대충 계산해봐도 풍선 하나 당 천원이나 든다. 헬륨이 진짜 어마어마하게 비쌌다. 도중에 회장님이 헬륨 말고 막대로 하자고 했지만, 그렇지만.. 낭만은 포기할 수 없는걸~ 부회장님과 함께 헬륨 풍선 하자고 떼써서 헬륨 풍선을 사수했다. 그래서 알록달록한 풍선으로 대회를 장식할 수 있었다. 그리고 이 헬륨가스 조금 이슈가 있었다. 수업지원실에서 분명 택배를 맡아준다고 해서 진짜 거의 20분 넘게 거기서 헬륨 가스를 찾았는데 없었다. 경비원분도 같이 찾는 걸 도와주셨는데 도저히 아무 데도 없어서 멘탈이 살짝 나갔었다. 결국엔 찾았는데, 어디 있었냐면 3층 현관문 앞에 그대로 놓여있었다. 아니.. 택배 맡아준다고 했으면 상식적으로 안에 있어야 하는 게 아닌가? 택배를 무사히 찾아서 다행이었지 이것 때문에 조금 화난 상태로 시작하긴 했다. 그것도 잠시, 문제 출제 이슈로 너무 바빠서 택배에 관한 건 바로 잊혔다. 그렇게 대회가 시작됐고 문제 풀 때마다 풍선 달아주는 걸 보니 나도 UCPC 본선 나가서 풍선 누가 달아줬으면 좋겠다고 생각했다.. 근데 우리팀 UCPC 본선 나갈 수 있을까? 열심히 해야겠다 ㅠㅠ
바빴던 출제 일정
내전 일정이 종강한 주 토요일로 잡혀서 무려 시험기간에 출제를 했어야 했다. 나는 심지어 시험이 일찍 시작되서 늦게 끝났기 때문에 시험기간이 엄청 길었는데.. 그 기간에 출제 아이디어를 떠올려야 했다. 나는 세그먼트 트리, 분리 집합, 이분 탐색에서 문제를 내기로 했었는데, 세그먼트 트리는 다행히 1차 내전 이전에 내가 출제를 해뒀었다(근데, 이 문제가 마지막까지 날 괴롭혔다..).
분리 집합은 멘토링을 하면서 집합 개수를 같이 union 하는 아이디어에서 비슷하게 min을 union하면서 관리하는 걸 생각을 해뒀었고, 또 다른 주제로는 BOJ의 ‘공항’같은 문제처럼 union을 잘 해야하는 문제를 어떻게 내보고 싶었다. 후자는 멘토링 시간에 다루지도 않았고 동아리 중급반 수준에서 풀 수 없을 것 같다는 판단에 전자로 내야겠다고 마음을 두고 있었다. 그래서 그냥 union하면서 최소 비용을 찾는 문제로 출제했다. 그런데 알고 보니 DFS로 component 찾아서 min값 관리해도 풀리는 문제였다. 내가 보기엔 사실상 거의 유사한 풀이인 거 같아서 그냥 냅뒀다. 아마 골4~3 정도 되는 문제일 듯 하다.
이분 탐색이 제일 낼 게 없었는데.. 왜냐면 내가 거기에 자신이 없기도 했고, 뭔갈 만들어도 그거 증명을 못할 것 같아서 전형적인 걸로 낼 수 밖에 없었다. 좌표를 주고 N개 중 K개를 골라 만든 집합에서 각 좌표 간 최단거리를 maximize 하는 거로 냈다. 알면 바로 푸는 그런 전형적인 문제였다. 문제를 출제했던 날이 미친 듯이 더웠던 날이라서 문제 소재도 “여름은 싫어”로 해서 냈다. 검수진 한 명이랑 솔루션이 내놓은 답이 서로 달랐는데, 킹갓 레드분이 솔루션을 야무지게 짜오셔서 누가 맞는지 결론을 내려주셨다. 결론은 나의 승리 ㅎㅎ.. 가장 재미없게 내서 그런지 이슈가 거의 없었던 문제였다. 대충 실1~골5 정도로 추정된다.
마지막으로 가장 괴로웠던 문제가 바로 세그먼트 트리를 쓰는 문제였다. 코포 A번에서 영감을 얻었던 문제였다. A번에서 원하는 걸 정확히 반대로 풀고 WA를 N번 받고 억울해서 그걸 아이디어로 만들어버린 문제였다. 각 조각을 정렬했을 때 전체가 정렬되려면 각 조각은 어떤 조건을 가져야할까? 이 생각을 그대로 문제로 옮겼다. 정말 조금만 생각해보면 솔루션이 생각나는 문제다(애초에 A번 풀다가 생각난 아이디어니까..ㅋㅋ). (이전 조각에서 max <= 다음 조각에서 min)을 만족하면 전체가 정렬됨을 알 수 있다. 이걸 업데이트를 조금 섞어주고 로그시간에 처리하도록 하면 문제 하나를 뚝딱 만들 수 있다. 아마 요것까지 3월 초에 만들어놨었던 것 같다. 그때는 쿼리 개수를 500개만 주고 N을 작게줬다. 그랬던 이유가 MCS가 도는 속도가 너무 느려서(그냥 평범한 탑다운 세그인데..) 그랬던 건데 결국엔 이게 문제를 일으켰다.
대회가 얼마남지 않은 시간에 통과되어선 안될 솔루션들이 통과되는 참사가 발생했고, 이거를 막으려고 진짜 많은 조건을 바꿔봤다. 그래도 잘 안되길래 저격데이터를 만들려고 시도했고, 그것조차 실패해서 조금 방치 해뒀다. 그러다가 조각 개수를 로그 개수만큼 바꿔보는게 어떻냐는 학술부장님의 조언에, 그렇게 하니까 모든게 의도대로 잘되는 걸 확인할 수 있었다. 진짜 너무 다행이었고, 모든게 해결됐다고 생각했다. 그런데 ㅋㅋ 대회 당일 무려 20분 전에 TLE가 나야 할 코드가 돔저지의 너무나도 야무진 성능으로 AC를 받는걸 보고 급하게 800ms로 시간제한을 줄였다. 시작 20분 전에!!!ㅋㅋㅋㅋㅋㅋ 진짜 큰일날 뻔 했다. 혹시라도 TLE 풀이가 통과됐으면 아마 구데기 문제라고 욕을 바가지로 먹었지 않았을까? 여튼 내 문제는 우여곡절이 많았지만, 결국에 큰 문제 없이 넘어갔다. 결론적으로, 우려했던 TLE 풀이는 아무도 시도 안 했었다. 플5정도라고 생각하고 있다. 그냥 max-min seg에 간단한 아이디어++ 니까 골1보다는 높을 듯..? (오렌지님이 골1이라고 주장하지만..)
대회까지 시간이 많이 없는 상태에서 문제를 짜내려고 하니 당연히 잘 되지도 않았고, 양질의 문제보다는 그냥 전형적인 문제를 뽑아낸 것 같아서 아쉽긴 했다. 한 번 데이고 나니까 문제 출제는 미리미리 해둬야겠다는 걸 진짜 크게 느끼고 있다. 살면서 느끼는 모든 것을 출제 소재로 승화시켜보는 노력을 해야지 대회날 전에 내가 편하지 않을까? ㅋㅋ 종강한 주 거의 놀지도 못하고 혼자서 자취방에 틀어 박혀서 출제, 검수, 출제, 검수, 에디토리얼 작성, 포스터 제작 이러고 있으니까 정신 나갈 것 같았다. 대회 당일날 새벽에 문제 검수한 건(고인물들 올솔 방지로 새벽에 두 문제가 생김) 진짜 레전드 오브 레전드일듯. 그렇게 바쁜 삶을 살고 있을 때 생각하지도 못한 선물을 주는 사람이 있어서 많이 고마웠다. 진짜 미리 출제해둬야겠다 이제는.. 헤헤
문제가 바뀌는 기적
비기너 문제 하나가 대회 도중에 바뀌는 이슈가 있었다. 분명 검수할 때는 솔루션이 잘 돌아가서 문제가 없었는데(심지어 나 그 문제 공통으로 하면 어떻냐고 했었음. 문제가 좋아서..), 돔 저지가 스페셜 저지가 잘 안되는 이슈로 인해 실수 출력 대해 AC코드를 WA로 판정을 때리는.. 그런 어마어마한 이슈가 생겼다. 대회 도중에 옆에서 또 다른 학술부원님이 실시간으로 문제를 고쳤고 결국에는 실수값 내림을 하게 해 정수형으로 출력할 수 있도록 문제를 수정했다. 정말 있어서는 안될 일이었지만, 다행히 어떻게 잘 넘어가서 다행이었다. 다음부터는 스페셜 저지 절대 안 쓰는 문제들만 내도록… ㅠㅠ 또, 어드밴 C번 문제 지문이 느슨했던 관계로 조금 문제가 있었고(검수할 때는 잘 못느꼈었는데 ㅠㅜ) 결국엔 그 이슈가 있었던 문제를 낸 두 분이 해설할 때 사죄를 했다. 검수를 열심히 안한 내 잘못도 있긴 한듯. ㅈㅅ..
예비소집 문제 풀지 말아주세요..
도대체 왜인지 모르겠으나 예비소집 문제를 대회 시간에 착각하고 푸신분들이 너무 많이 계셨다. 사전에 주의하라고 미리 공지라도 해줄걸.. 너무 미안했다. 한 사람은 오프라인 대회에 와서 1시간 가까이 예비소집 문제를 풀고 있었다.. 그리고, 대회 전날에 메일이 왔는 지 확인을 해달라는 요청을 했었는데 많은 분들이 이를 확인하지 않으셔서, 등록되었는지 확인도 못하고 참여하셨다가 계정 정보가 아예 없어서 참여가 불가능해졌던 그런 몹쓸 경험을 하게 됐다. 제발 부탁이니 공지한 내용은 확인 좀 해주셨으면 ㅠㅠ
처음이라 미숙했던 대회 운영
대회 운영진 아무도 대면 대회 경험이 없다 보니 감으로 모든걸 준비했다. 대회 후원도 늦게 요청해서 기업 후원을 받기는 어려웠고, 결국 마지막으로 알로하 선배님들께 도움을 요청했다. 알로하 선배님들 진짜 멋있다. 도와달라고 하니 수십만원씩 툭툭 던져주시는게 … 캬 이게 알로하? 알로하를 만드신 전설의 ‘알창남’선배님도 이번 대회에 후원을 해주셨고 회장을 하셨던 선배님들이 많이 도와주셨다. 그렇게 대회 상금/상품 이슈를 해결할 수 있었다. 심지어 선배님들 중간에 오셔서 구경하시다가 문제도 풀어보시고 운영진들 커피도 사주시구 가셨다. 다시 한 번 감사드립니다!! 선배님들 ㅠㅠ.
대회 당일에 소통할 수단이 없었기 때문에 계속 왔다갔다 하면서 말을 했고, 이게 너무 비효율적이었다. 다음부터는 디스코드나 따로 소통할 공간을 만들어서 운영하자는 학술부장의 의견이 있었다. 진짜 너무 동의하는 부분.. 처음이라 어쩔 수 없었긴 했다. 이런 건 한 번 깨져봐야 알 수 있는 부분이 아닐까? 이게 7월 10주년 대회가 아닌게 너무 다행이었다. 이번 대회를 통해 보완해야할 점을 많이 얻은게 다행이다.
핸들과 실제 사람을 매칭하는 것도 엄청 고생이 많았고, 그걸 확인하고 풍선을 달아주러 갔던 부회장님 사무부장님 인사부장님 재무부장님 너무 고생이 많았다.. 다음에 편하게 하려면 어떤 시스템을 미리 만들어놔야 할 것 같다. 이번 대회가 온/오프라인 동시 진행이라 더 그런것도 있긴 했다. 진짜 많은 분들이 고생해줘서 겨우겨우 대회가 어찌저찌 굴러갔다. 대회 끝나기 1시간쯤 전에 “헉 수상자 발표 ppt 있어야 했지..”하고 급하게 ppt 만들고.. 특별상 기준 정하고 했었다. 정말로 너무 정신없었다. 아니 근데 그거 왜 내가 발표했는지는 좀 의문이다. 스코어보드 공개도 좀 재미없게 했고(말재주가 딸림 ㅎㅎ..), 호응 유도도 못함ㅋㅎㅋ. 다음엔 이런거 잘하는 운영진이 하는걸로 하자. 근데, 회장님의 라디오 시간 왜 안해줌 ㅎㅎ.. 그건 좀 아쉬웠다^^ 회의중에 농담삼아 한 얘기 중에 회장님 이름 넣고 “ooo인” 도장 박자는 의견은 진짜 상장에 반영되서 좀 재밌긴 했다.
그래도 재밌었다!
바빠서 정신없었지만, 풍선도 달구 사진도 찍고 너무 재밌었다. 헬륨가스 마시고 말하는 것도 해보고 ㅋㅋㅋ 낭만있는 대회였다. 엄청 고생한 우리 운영진들 너무 고맙구 7월 대회도 파이팅! 다만 조금 아쉬웠던건 개인전이라 대회 분위기가 조금 정적이었다. 난 처음부터 팀전을 제안했었는데, 팀이 많이 안생길거란 반대로 무산됐었다. 근데 팀으로 해야 아무래도 분위기가 말을 좀 하구 축제같은? 그런 분위기가 되지 않을까? 이왕 문제 풀면서 경쟁하며 즐기는 대회인데 분위기라도 좀 부드러우면 좋을것 같다. 뭐 이건 개인적인 바람이고 이번 대회도 짱 좋았다! 나도 참가자하고 싶었던건 안비밀..(꽤 진심)
12 May 2022
Disjoint-Set & Union-Find
자료구조론 시간에 재밌는 과제가 나와서 한 번 정리해보려고 한다.
보통 유니온-파인드라고 많이 부르는 알고리즘으로 미로를 만들 수가 있다.
일단 Disjoint-Set이 무엇인지부터 알아보자.
Disjoint-Set은 교집합이 없는 2개 이상의 분리되어 있는 집합(쉽게 말해서 서로소 집합)이라고 할 수 있다. 이 집합에서는 합집합 연산(Union)을 할 수 있다. 집합은 inverted(child가 parent를 가르킨다는 의미) tree 형태로 표현할 수 있다. 각 트리의 루트는 하나로 유일하기 때문에, 루트를 비교하는 것으로 같은 집합인지 확인 할 수 있다.
Find
parent[x]를 x의 부모 노드라고 정의하면, 다음과 같이 find 연산을 구현할 수 있다.
이때, 부모 노드가 없는 경우엔 parent[x] = x 가 된다.
int find(int x) {
if(x == parent[x]) return x;
else return parent[x] = find(parent[x]); //path compression
}
각 parent노드를 최상위 루트 노드에 달아버리는 path compression을 사용하면 find 연산 시간이 상당히 빨라진다.
Union
합집합 연산은, 각 집합의 루트를 찾아낸 다음 루트를 합치는 식으로 구현할 수 있다.
void uni(int x, int y) {
int x_p = find(x);
int y_p = find(y);
if(x_p == y_p) return;
if(x_p < y_p) parent[y_p] = x_p;
else parent[x_p] = y_p;
}
Union을 할때, rank를 사용해 rank가 큰 쪽에 낮은걸 합쳐주게 되면 시간복잡도가 향상된다. path-compression과 union-by-rank를 모두 사용해 최적화 해주게 되면, \(\scriptsize O(\alpha(N))\)이다. path-compression만 사용해도 상당히 빠르기 때문에, 나는 보통 path-compression만 사용한다.
N x N 미로 만들기
이런 자료구조랑 알고리즘을 사용해서 N x N크기의 미로를 생성하는 프로그램을 짤 수 있다. (와!)
모든 칸의 테두리에 벽이 있다고 가정하면, 아래와 같은 과정을 통해서 미로를 생성해낼 수 있다.
while(find(첫칸) != find(마지막칸)) {
x = 랜덤으로 선택한 벽
a = x에 붙어있는 첫번째 칸
b = x에 붙어있는 두번째 칸
if(find(a) != find(b)) {
x를 지운다.
uni(a, b)
}
}
즉, 첫칸과 마지막칸이 같은 집합이 될 때까지 벽을 없애면서 공간을 합쳐주는 식으로 미로를 만들 수 있다. 근데 막상 구현하려고 하니, 벽을 없애는 부분이 조금 까다로웠다. 나는 모든 벽을 모두 저장하지 않고 필요한 벽만 저장하는 방식으로 구현을 했다. 잘 생각해보면, 한 칸당 _| 벽만 있어도 모든 걸 다 구현할 수 있다는 사실을 깨달을 수 있다. 그렇기에 총 \(\scriptsize 2n^{2}\)개의 벽이 필요하고, 아래 그림처럼 번호를 생각해주면, 각 벽을 허물었을 때 어느 칸이 합집합이 되는 지 쉽게 알 수 있다. 요걸 가지고 잘 구현만 해주면 미로를 생성할 수 있다.
edit : 2022-08-18 01:07 1학기 끝난 지 한참 지났기 때문에 그때 짰던 과제 코드도 첨부합니다.
void createMaze(DisjointSets* sets, PrintDisjointSets* maze, int n) {
srand(time(NULL));
int s = n * n;
while(find(sets, 1) != find(sets, s)) {
int wall = rand() % (2 * s) + 1;
//horizontal merge
if(1 <= wall && wall <= s) {
int cell_a = wall;
int cell_b = cell_a + 1;
if(cell_a % n == 0) continue;
if(find(sets, cell_a) != find(sets, cell_b)) {
maze->ptr_arr[wall] = 0;
union_(sets, cell_a, cell_b);
}
}
//vertical merge
else {
int cell_a = wall % s;
if(cell_a == 0) cell_a = s;
int cell_b = cell_a + n;
if(cell_b > s) continue;
if(find(sets, cell_a) != find(sets, cell_b)) {
maze->ptr_arr[wall] = 0;
union_(sets, cell_a, cell_b);
}
}
}
}
void printMaze(PrintDisjointSets* maze, int n) {
int s = n * n;
maze->ptr_arr[s] = 0;
for(int i = 0; i < n; ++i) printf(" -");
printf("\n");
for(int i = 0; i < n; ++i) {
if(i != 0) printf("|");
else printf(" ");
for(int j = 1; j <= n; ++j) {
char x = (maze->ptr_arr[i * n + j] ? '|' : ' ');
printf(" %c", x);
}
printf("\n");
for(int j = 1; j <= n; ++j) {
char x = (maze->ptr_arr[i * n + j + s] ? '-' : ' ');
printf(" %c", x);
}
printf("\n");
}
}
createMaze함수는 말 그대로 위의 방식으로 벽을 골라 지워 미로를 만드는 함수다. printMaze함수는 만들어진 미로를 출력하는 함수다.
좌우 셀을 합칠 땐, 현재 셀 번호가 \(\scriptsize k\)일때, \(\scriptsize (k, k + 1)\)셀을 합치면 된다. 상하 셀을 합칠 땐, \(\scriptsize (k, k + n)\)셀을 합치면 된다. 셀 번호를 찾으려면 위에서 소개한 방법으로 벽을 넘버링 하면 편하기 때문에 그렇게 설계했었다.
아마 코드를 보면 쉽게 이해가 될 것 같다. 자료구조론 같이 강의 듣던 친구가 어떻게 만들었냐고 묻길래 내 방법 설명해주니까 그냥 뚝딱뚝딱 만들어 오는걸 보면.. 이 방법이 그렇게 어렵진 않은 듯? 
21 Apr 2022
(시험기간 + 약)으로 인해 아무것도 집중을 할 수 없어서 쓰는 뻘글..
디자인?
나는 디자인을 제대로 배워본 적이 없다. 사실 아무것도 모른다고 해도 무방할 정도로 잘 모른다. 초등학교 다닐 때 배운 포토샵 지식으로 느낌 꽂히는대로 그냥 슥슥 만든다. 대충 flat한 디자인 몇개 보고 “오 이런거 좋다~” 하고 그거 따라 만들어보고 그런 것만 해봐서 진짜 근본 없는 디자인만 쏟아내고 있다. 어쩌다가 학생회에 들어가서 디자인을 하고 있기도 해서 만든걸 한 번 정리해놓아 보려고 글을 쓴다.
뭔가 어색한 포토 카드
학교와서 제일 처음 만들었던 포토 카드다. 그 시기에 이런걸 만들 사람이 없어보이길래 나라도 만들어와볼까 싶어서 만들었었다(하지 말았어야 했다-). 이걸 만들고 학생회 디자인 부서로 납치 아닌 납치를 당하게 되었는데.. 음.. 뭔가 많이 비어보이는 디자인이라 썩 맘에 들진 않았다. 그런데, 뭐 다른사람은 나쁘지 않게 봐준 것 같긴 하더라..
난 심플(플랫?)하면서도 비어보이지는 않는 디자인을 선호하는데, 정작 본인은 둘 다 만족시키는 디자인은 잘 못하겠다 ㅋ;
이스터 에그(?)를 넣은 디자인
갑작스럽게 나보고 컴소 수건좀 디자인해줘요옹!!!!!!!! 하길래 뽑아낸 디자인이다. 이때 한창 뭔가 BIT의 그 구조에 꽂혀있던 시기라서 자연스럽게 그걸 뭔가 넣어보고 싶었다. 양쪽 끝에 있는 4 레벨짜리 선들이 바로 유우명한 그 자료구조를 녹여낸 것이다.
양쪽에 있는 좀 멋있는 CSE 사자 디자인은 같은 부서에 있는 분이 짱 멋지게 만든 과 로고다. 저런 디자인은 어떻게 만드는건지.. 존경스럽다. 여튼 로고가 잘 뽑혀나와서 수건 디자인도 나름 마음에 들게 나왔다. BIT도 숨겨뒀고 뭔가 깔끔하게 잘 나와서 좋았던 디자인. 근데 이거 파일이름이 towel_real_real_real_final.pdf다. 요청사항이 계속 바뀌어서 한무 수정..을 했던 그런 몹쓸 경험을 했다.
깃발도 디자인함
수건 디자인하고 나니까 깃발도 만들어 달라길래 만들어줬다. 대충 급하게 4개의 시안을 만들어서 갔는데, 최종 선택본이 저거였다. 사실 나머지 3개는 지금보니까 구리긴 한듯ㅋㅋ 나름 민트색이 학과 고유 컬러마냥 되어 있어서 디자인에 넣었는데 나름 성공적으로 들어가서 좋았다. 그 이후에도 민트색을 이용해서 디자인을 시도했는데 음 하는 것마다 다 구려서 앞으론 민트를 안쓸 생각이긴 하다. (민트색 디자인 난이도 매우 높음..)
디자인 좀 제대로 배우고 싶다
사실 위에거 말고도 만든게 많긴 한데 슬슬 쓰는게 귀찮아져서 급 마무리.. 근본 없이 배워서 만들고 있다 보니까 상당히 디자인이 중구난방이다. 시간날 때 디자인을 좀 전문적으로 배워보고 싶긴 한데, 정작 하려니 같이 할 사람도 없고 그래서 과연 할 수 있을 지 의문이다. 거의 10년째 똑같은 디자인만 구사하는게 답답하기도 하고, 무엇보다도 내가 만든게 내가 맘에 안든다. 솔브드를 만드신 shiftpsh님처럼 디자인을 해보고 싶은데 난 저런걸 언제쯤 배울 수 있을까..
03 Apr 2022
Google Code Jam Qualification Round
퀄리피케이션 라운드는 30점만 긁으면 다음 라운드로 나갈 자격이 주어진다. 이번 라운드에서는 A, B, C를 차례로 풀기만 해도 44점이라 3문제만 풀면 됐었다. 나는 A, B, C, D를 풀고 E는 상당히 어려워보이는 문제라 풀진 않고 넘어갔다.
나는 71점 전체 749등으로 마무리했다.
A. Punched Cards
지문에 쓸데 없는 내용이 가득한데, 그냥 단순한 구현 문제이다. 좌측 상단 4칸만 ‘.’으로 채워주고 나머지는 규칙에 따라 채운 뒤 출력해주면 된다.
코드 보기
#include <bits/stdc++.h>
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int T; cin >> T;
int tc = 1;
while(T --> 0) {
int R, C; cin >> R >> C;
vector<vector<char>> m(2 * R + 1, vector<char>(2 * C + 1));
for(int i = 0; i < R; ++i) {
for(int j = 0; j < C; ++j) {
int r = 2 * i, c = 2 * j;
m[r][c] = '+';
m[r + 1][c] = '|';
m[r][c + 1] = '-';
m[r + 1][c + 1] = '.';
}
}
m[0][0] = m[1][0] = m[0][1] = m[1][1] = '.';
for(int i = 0; i < C; ++i) {
m[2 * R][2 * i] = '+';
m[2 * R][2 * i + 1] = '-';
}
for(int i = 0; i < R; ++i) {
m[2 * i][2 * C] = '+';
m[2 * i + 1][2 * C] = '|';
}
m[2 * R][2 * C] = '+';
cout << "Case #" << tc++ << ":\n";
for(int i = 0; i <= 2 * R; ++i) {
for(int j = 0; j <= 2 * C; ++j) {
cout << m[i][j];
}
cout << '\n';
}
}
return 0;
}
B. 3D Printing
Cyan 색상을 세 프린터에서 쓸 수 있는 최대한으로 쓰고 싶다고 해보자. 주어지는 Cyan 용량 값들 중 최솟값이 Cyan을 최대한으로 쓸 수 있는 값이다(예를 들어, 10, 5, 3이 주어지면 3보다 더 쓸 수 없으니..). 따라서, 이와 같이 모든 컬러에 대해 최솟값을 찾아주고 “min(C) + min(M) + min(Y) + min(K) >= 1e6”이면, 가능한 케이스 이므로 실제 답을 찾아서 출력해주고, 그렇지 않으면 불가능한 케이스이니 IMPOSSIBLE을 출력하면 된다.
코드 보기
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using ppii = pair<int, pii>;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int T; cin >> T;
for(int tc = 1; tc <= T; ++tc) {
int C[3], M[3], Y[3], K[3];
for(int i = 0; i < 3; ++i) cin >> C[i] >> M[i] >> Y[i] >> K[i];
bool flag = false;
int min_C = *min_element(C, C + 3);
int min_M = *min_element(M, M + 3);
int min_Y = *min_element(Y, Y + 3);
int min_K = *min_element(K, K + 3);
if(min_C + min_M + min_Y + min_K >= int(1e6)) flag = true;
cout << "Case #" << tc << ": ";
if(!flag) cout << "IMPOSSIBLE";
else {
int s = 1e6;
int min_color[4] = {min_C, min_M, min_Y, min_K};
for(int i = 0; i < 4; ++i) {
if(s - min_color[i] < 0) {
min_color[i] = s;
s = 0;
}
else s -= min_color[i];
}
for(int i = 0; i < 4; ++i) cout << min_color[i] << ' ';
}
cout << '\n';
}
return 0;
}
C. d1000000
1부터 차례대로 증가하게 주사위를 배치할 때, 얼마까지 수가 증가할 수 있는지 묻는 문제이다. Greedy하게 생각해보면, 먼저 Si가 작은 값부터 차례대로 정렬시켜 놓자. 배치하는 수는 1부터 시작하고, 그 숫자를 x라고 해보자. 정렬되어 있는 수열에서 앞에서부터 차례로 비교하자. x <= Si이면 가능하기 때문에, x와 인덱스를 함께 증가시켜주면 되고, x > Si이면 x <= Sk를 만족하는 최초의 인덱스 k를 찾으면 된다(못찾으면 그대로 끝). 이렇게 x를 찾아주면, 마지막에는 답이 되는 수보다 1만큼 크기 때문에, -1해서 출력해주면 정답.
코드 보기
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using ppii = pair<int, pii>;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int T; cin >> T;
for(int tc = 1; tc <= T; ++tc) {
int N; cin >> N;
vector<int> d(N);
for(int& e : d) cin >> e;
sort(d.begin(), d.end());
int max_n = 1;
for(int i = 0; i < N; ++i, ++max_n) {
if(max_n > d[i]) {
while(i < N && d[i] < max_n) ++i;
if(i == N) break;
}
}
cout << "Case #" << tc << ": ";
cout << max_n - 1 << '\n';
}
return 0;
}
D. Chain Reactions
재밌는 문제였다. 신기했던 포인트가 있는데 문제에서 주어지는 그래프가 DAG임을 좀 특이한 형태로 알려주고 있다. 한 노드 a가 포인팅하는 다른 노드 b는 a > b를 만족해야한다는 성질이 그래프를 DAG로 고정시켜버린다. DAG임을 알고 나면, DAG DP를 시도해볼 수 있다. 나는 Topology Sort + DP로 문제를 해결했다.
풀이는 다음과 같다. (사진으로 대체함)
코드 보기
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using ppii = pair<int, pii>;
const ll INF = 1'000'000'000'000'000'000LL;
ll solve(vector<vector<int>>& adj, vector<ll>& F, vector<int>& in_degree, int& N) {
vector<ll> cost(N + 1, INF);
queue<int> q;
for(int i = 1; i <= N; ++i) {
if(in_degree[i] == 0) {
cost[i] = F[i];
q.push(i);
}
}
ll ret = 0;
while(!q.empty()) {
int cur_node = q.front();
q.pop();
for(int& next_node : adj[cur_node]) {
if(next_node == 0) ret += cost[cur_node];
else if(cost[next_node] == INF && in_degree[next_node] == 1) {
cost[next_node] = max(cost[cur_node], F[next_node]);
in_degree[next_node]--;
q.push(next_node);
}
else {
cost[next_node] = min(cost[next_node], cost[cur_node]);
ret += cost[cur_node];
if(--in_degree[next_node] == 0) {
ret -= cost[next_node];
cost[next_node] = max(cost[next_node], F[next_node]);
q.push(next_node);
}
}
}
}
return ret;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int T; cin >> T;
for(int tc = 1; tc <= T; ++tc) {
int N; cin >> N;
vector<ll> F(N + 1);
for(int i = 1; i <= N; ++i) cin >> F[i];
vector<int> in_degree(N + 1);
vector<vector<int>> adj(N + 1);
for(int i = 1; i <= N; ++i) {
int Pi; cin >> Pi;
adj[i].push_back(Pi);
in_degree[Pi]++;
}
cout << "Case #" << tc << ": ";
cout << solve(adj, F, in_degree, N) << '\n';
}
return 0;
}
E. Twisty Little Passages
Tourist도 5트하고 도망가길래 사실 풀 생각도 없었던 문제고.. 거기에 interactive 라는 문제 유형 덕에 진짜 그냥 읽기만 했다. 대충 랜덤으로 노드를 방문해서 통로 수를 기억해 두고 그 값의 평균 * 노드 수 해서 출력한다는 흐름의 풀이라는데… 어 음.. 짱짱 어려운 문제인것만 알 것 같다.
대략 일주일 뒤 Round 1A에서도 스무스하게 풀 수 있었으면 좋겠다. 여튼 나의 첫 구글 코드잼 퀄리피케이션 라운드였다.
16 Jan 2022
난이도
Gold V
문제 풀이
"\(\small f(idx, \space count) :\equiv\) 현재까지 만든 그룹의 수가 count일때, idx번째 숫자부터 그룹을 만들어서 얻을 수 있는 합의 최대값" 이라고 정의하자.
각 그룹은 이웃하면 안되기 때문에 최소 한칸이상은 떨어트려 놓아야 하기에, 다음처럼 함수를 전개할 수 있다.
\[\small f(idx, count) = \max_{i = idx}^{N - 1} (f(i + k, \space count + 1) + \sum_{j = idx}^{i} seq_{j}) \space , (2 \leq k < N)\]
따라서, 재귀적으로 문제를 해결할 수 있게 되고 겹치는 부분문제들이 발생하기 때문에 그 부분을 메모이제이션해주면 된다.
메모이제이션 배열을 N x M 크기로 만들어
dp[idx][count]로 값을 미리 저장해두면 된다.
기저 사례는 \(\small count = M\)인 경우와 \(\small count < M \wedge idx \geq N\) 인 경우이다.
전자는 묶어야할 그룹을 모두 묶어낸 것이니 0을 리턴해주면 된다. 반면, 후자는 불가능한 경우이기에 불가능한 값을 리턴해줘야한다.
int solve(int idx, int cnt, vector<int>& seq, vector<vector<int>>& dp) {
if(cnt == M) return 0; //base case
if(cnt < M && idx >= N) return MIN; //base case 2
int& ret = dp[idx][cnt];
if(ret != MIN) return ret;
ret = MIN - 1;
int summation = 0;
for(int i = idx; i < N; ++i) {
summation += seq[i];
for(int k = 2; k < N; ++k) {
ret = max(ret, solve(i + k, cnt + 1, seq, dp) + summation);
}
}
return ret;
}
코드에서 재밌는 점은, 캐싱되어있는 값을 리턴한 이후 ret = MIN - 1로 설정하는 부분이다.
이 라인을 작성해주지 않는다면 TLE를 받게 되는데, 그 이유는 ret = MIN일때 코드에서 값이 계산되지 않았다고 판단하기 때문이다. 불가능한 경우에 대해서도 캐싱을 해줘야하는데, 그게 안되면 계속 불필요한 연산이 발생하고 그게 지수꼴의 시간복잡도로 나타나 결국엔 시간초과가 발생하는것이다. 따라서, 나는 불가능하다는 의미로 MIN - 1을 할당해주는 방식을 택했다.
이렇게 값을 계산해주면, 답은 \(\small max_{i = 0}^{N - 1}(f(i, 0))\)이니, 이것을 찾아 출력해주면 AC.
코드 전문
2228 // 구간 나누기