안녕하세요 hellogaon입니다.
2019년 12월 28일, 작년에 이어 한양대학교 에리카 알고리즘 학회 '영과일'의 내부 대회
Zero One Algorithm Contest 2019(이하 ZOAC 2019)가 개최되었습니다.
대회가 열리기 한 달 전, 대회 개최 조건이 변경되어 3명 이상의 검수진이 필요하였고
자칫하면 대회가 열리지 못할 뻔도 하였으나 영과일 회장님의 대회를 개최하겠다는 열정에 감동하여
검수진을 구할 수 있었다는 후문이 있습니다.
출제자로는 저와 재현이(TheKinGoD)와 병서(bsyun0571)가 참여하였고
정말 훌륭하신 cheetose님, functionx님, h0ngjun7님, jh05013님, oree2113님, rdd6584님께서
검수진으로 참여해주셔서 더욱 높은 퀄리티의 대회를 개최할 수 있었습니다.
완벽하게 문제를 만들어서 검수진을 고생시키지 말자!라는 목적이 있었으나
수십 번을 읽어봐도 찾지 못했던 스크립트의 오류 뿐만 아니라, 직접 데이터도 만들어주시고,
문제 이미지도 만들어주시고, 다양한 방법으로 풀이를 진행해주셔서
저 또한 새로운 해법에 대해서 알 수 있었고 많은 도움을 받을 수 있었습니다. 다시 한 번 감사드립니다.
작년에는 본대회 8팀, Open Contest에서는 20여명이 참가해주셨었는데 올라간 대회 퀄리티 만큼이나
올해에는 본대회 18팀, Open Conest에서는 30명이나 참여를 해주셔서 더욱 재밌게 대회를 즐길 수 있었습니다.
또한 올해에는 작년과는 다르게 난이도 순으로 배치하지 않았음에도 불구하고
출제진이 의도한대로의 마음에 드는 스코어보드를 얻을 수 있어 뿌듯하였습니다.
마지막으로 대회에 후원해주신 스타트링크, 바쁜 시간에도 참여해주시고 관심가져주신
영과일 학회원들 및 Open Contest 참가자들께 감사의 인사를 전합니다.
고생 많으셨습니다. 감사합니다.
아래는 문제와 문제의 후기, 그리고 문제의 풀이입니다. 많이 풀린 순서대로 배치하였습니다.
A - 18238번: ZOAC 2
작년에 이어 첫번째 문제에 위치하게 된 ZOAC문제입니다.
올해에는 모든 팀이 최소한 한 문제는 풀었으면 하는 목적으로 제작되었으며 본대회에서 모든 팀이 풀어준 문제입니다.
작년과 올해에 이어 내년에도 ZOAC의 A번 문제는 문자열 문제라는 역사가 생길 지 궁금합니다.
알파벳이 쓰여있는 원판을 시계방향 또는 반시계방향으로 한 칸씩 움직일 수 있을 때
원하는 문자열을 출력하는 데 걸리는 최소 시간을 출력하는 문제입니다.
현재 놓여있는 상태가 x번째 알파벳, 내가 출력하고 싶은 문자가 y번째 알파벳일 때,
최소 min(abs(y-x), 26 - abs(y-x)) 시간에 옮겨갈 수 있습니다.
입력받은 문자열을 S라 할 때, 'A' → S[0] → S[1] → S[2] ... 로 옮겨 가는 것이 최선이므로
문자열의 길이만큼 탐색하여 값을 더해주면 풀 수 있는 문제입니다.
더 자세한 출제자의 풀이는 여기에서 확인하실 수 있습니다.
H - 18245번: 이상한 나라의 암호
이 문제 또한 많은 팀들이 풀도록 만든 문제입니다.
그러나 맨 마지막에서 2번째에 배치하여 먼저 전체적으로 문제를 보는 사람이 맞출 수 있도록 하였다보니
본대회에서는 25분만에 퍼솔이 등장하였고 이후 많은 팀들이 이 문제를 풀어주었습니다.
문제에서 제시되어 있는 조건에 따라 암호문을 해독하면 되는 문제입니다.
문자열을 입력받아 반복문을 잘 돌려주면서 출력하면 풀 수 있습니다.
자세한 코드는 아래 슬라이드를 참고해주세요.
E - 18242번: 네모네모 시력검사
이 문제를 출제할 때 답을 구하는 것이 가능한 지 불가능 한 지 또한 물어볼까 생각하였는데
이는 너무 참가자를 귀찮게 하는 것 같아 문제에서 제시한 조건에 맞는 입력만 들어오는 것으로 수정하였습니다.
쉽게 풀 수 있는 방법을 바로 생각한다면 쉽게, 아니라면 조금 오래 걸릴 수도 있게 하는 것이 출제의도입니다.
조건에 맞는 시력검사표가 들어올 때 어느 변이 뚫려 있는 지 맞추는 문제입니다.
색칠한 부분의 가장 작은 y좌표, 가장 작은 x좌표, 가장 큰 y좌표, 가장 작은 x좌표 네 개를 구하게 되면
이 네 개의 좌표로 정사각형의 네 꼭지점을 표현할 수 있습니다.
어느 방향의 꼭지점의 중점이 비어 있는 지에 따라 정답을 출력하면 되는 문제입니다.
F - 18243번: Small World Network
BOJ내에서 3500여명 이상 푼 케빈 베이컨의 6단계 법칙과 유사한 문제입니다.
유명한 그래프 문제로 다양한 방법으로 풀 수 있는 문제입니다.
모든 노드들이 6단계 이하로 연결되어 있는 지 확인하는 문제입니다.
저의 경우 플로이드 와샬 알고리즘을 사용하여 해결하였습니다.
플로이드 와샬을 돌리고 나면 dist[i][j]는 i 정점에서 j 정점까지의 최단거리를 뜻하므로
dist배열 내부에서 하나라도 6보다 큰 값이 있다면,
6단계 보다 큰 단계로 이루어져있다는 뜻이므로 "Big Worid!"를,
아니라면 "Small World!"를 출력하면 되는 문제입니다.
더 자세한 출제자의 풀이는 여기에서 확인하실 수 있습니다.
G - 18244번: 변형 계단 수
BOJ에서 '계단 수'를 검색하게 되면 계단 수, 쉬운 계단 수, 어려운 계단 수, 더 어려운 계단 수와 같이 시리즈가 존재합니다.
이 문제 또한 계단 수를 약간 변형한 문제입니다.
계단 수 중 연속으로 3번 이상 증가하거나, 연속으로 3번 이상 감소하지 않도록 하는
변형 계단 수의 개수가 몇 개일 지 출력하는 문제입니다.
다차원 DP문제로 저의 경우 4차원 DP을 아래와 같이 정의하였습니다.
dp[n][bef][cnt][ty] = 현재 n번째 계단 수를 채울 차례이고
바로 앞의 수는 bef이며, 현재 cnt개 연속으로 진행되고 있다는 의미입니다
ty = 0은 초기값, ty = 1일 경우 증가, ty = 2일 경우 감소하고 있다는 것을 뜻합니다.
더 자세한 출제자의 풀이는 여기에서 확인하실 수 있습니다.
C - 18240번: 이진 탐색 트리 복원하기
2년 전, 처음 풀었을 때 굉장히 인상깊었던 이진 탐색 트리 문제를 보다가 생각난 문제입니다.
이진 탐색 트리 문제는 수열이 주어지고 이들을 넣었을 때 깊이를 출력해야하는 문제라면
이 문제는 깊이가 주어지고 가능한 수열을 출력하는 문제입니다.
이 문제를 채점하는 스폐셜 저지가 이진 탐색 트리 문제와 동일하였습니다.
노드를 넣었을 때의 깊이가 순서대로 주어질 때 가능한 수열을 출력하는 문제입니다.
예제의 정답에 휘둘리지 말고 높이마다의 노드들을 최대한 앞으로 당겨서 생각할 수 있습니다.
또한 불가능한 경우는 위의 높이의 노드들이 모두 자식이 2개가 꽉차있을 경우라는 것을 알 수 있지요.
이제 나머지 경우에는 노드에 수만 잘 적어주면 됩니다!
이 때 이진 탐색 트리의 특성에 맞게 수를 적는 방법은 inorder 방법이 있습니다.
inorder방식으로 수를 적은 뒤 입력된 순서에 맞게 출력해주면 되는 문제입니다.
B - 18239번: 편안한 수열 만들기
B번 문제이기에 많은 팀들이 풀어주셨으나 본대회에서 아쉽게도 정답이 없었던 문제입니다.
이 문제의 아이디어는 배열 문제에서 얻었으며 정확히 5번이라는 조건을 걸 경우
생각보다 재미있는 부분이 많아 출제하게 된 문제입니다.
고통 받으셨을 많은 분들에게 죄송하다는 말씀 드립니다ㅠㅠ
시프트 되어 있는 수열을 swap, reverse 연산을 정확히 5번 이용하여
원래의 편안한 수열로 되돌리는 문제입니다.
일반적인 경우 3번의 연산으로 수열을 원래대로 만들 수 있습니다.
이때의 경우 남는 연산 2번을 같은 연산으로 진행하게 되면 다시 원래대로 만들 수 있지요.
그러나 이 방법에는 예외 케이스가 있습니다.
또한 놀랍게도 'NO'를 출력해야할 경우가 존재합니다.
자세한 설명은 아래 슬라이드를 참고해주세요.
D - 18241번: 문자열 게임
개인적으로 정해를 떠올리는데에 굉장히 오랜 시간이 걸렸던 문제입니다.
처음에 보았을 때 문자열 폭발 문제와 비슷하다고 생각이 들었지만 반례가 존재하였습니다.
주어진 문자열 S에서 N번의 명령에 따라 문자열 W를 앞에서, 또는 뒤에서 제거하는 문제입니다.
문자열 폭발 문제와 비슷하게 앞 뒤에서 스택을 관리하는 방법으로 접근할 수 있습니다.
앞에서부터 문자를 담는 스택을 LS, 뒤에서부터 문자를 담는 스택을 RS라 정의합시다.
L연산일 경우 문자를 하나씩 LS에 push하며 스택의 위에 있는 부분과 문자열 W를 비교하여 같을 경우 pop을 진행합니다.
R연산일 경우는 반대로 뒤에서부터 RS에 push하면서 진행합니다.
이를 각각 현재까지 넣은 문자열 인덱스가 만날 때까지 진행합니다.
모든 연산에 대해 스택의 위를 W의 크기만큼 확인하므로 이 때의 시간복잡도는 O(WN)가 되어집니다.
문자열 인덱스가 만나면 더이상 지울수가 없는 것일까요?
하단의 반례를 예시로 들어 설명할 수 있습니다.
이때 S = aaaaaabbbbb, W = ab 에 대해서 L, R 연산을 진행한다고 가정합시다.
LS에 aaaaaab에 들어가게 되고 위에 있는 ab가 지워지며 aaaaa만 남게 되어집니다.
여기서 R연산을 진행하면 LR에는 bbbb가 들어가고 끝나게 됩니다.
그러나 아직 지워야할 ab는 있는 상태이지요.
이 때 알 수 있는 정보는 지워야할 문자열 W는 LS와 LR에 모두 속해있으며 이는 같아진 문자열 인덱스를 기준으로
나누어져있다는 것을 알 수 있습니다.
즉 이제는 연산이 L, R인 지 상관없이 LS의 문자를 하나씩 pop한 뒤 RS에 push하여
RS 스택의 위에 있는 부분과 문자열 W를 비교하여 같을 경우 pop을 진행합니다.
이렇게 진행한 뒤 문제에서 원하는 것을 출력한다면 맞았습니다!를 받을 수 있습니다.
I - 18246번: 색종이와 쿼리
1년 전, 얼룩말 아트 문제를 풀기 위해 BOJ Slack에 질문하여 관련 알고리즘에 대해 알게 되었고
단순하지만 처음에 생각하기 어려웠기에 인상 깊었습니다.
이 아이디어를 사용한 문제를 내고 싶었고 여기에 쿼리를 더하면 어떤 문제를 만들 수 있을 지 생각하다가
2차원 배열에 대하여 max 구간 쿼리를 구할 수 있을 것 같아 출제하게 되었습니다.
어려운 개념이지만 알면은 빠르게 풀 수 있도록 하는 것이 출제 의도입니다.
색종이 N장이 좌표평면 상에 놓여있을 때
직사각형 영역에서 가장 많이 겹쳐 있는 영역에 놓여 있는 색종이의 장 수를 구하는 문제입니다.
총 2단계로 나누어져 있으며 각 칸마다 몇 장의 색종이가 겹쳐 있는 지 구하는 부분과
직사각형 영역의 최대값을 구하는 부분으로 나누어집니다.
1단계의 경우 부분합을 이용하여, 2단계의 경우 2D Segment tree를 이용하여 구현할 수 있습니다.
Update 질의가 없기에 Segment tree 개념과 비슷하게 구현이 가능합니다.
자세한 설명은 아래 슬라이드를 참고해주세요.
또한 검수진에서 다른 풀이로 이 문제를 해결해주셨는데,
RMQ에 Sparse Table를 적용하여 O(NlogN) 전처리로 O(1)만에 구하는 자료구조와
평방분할을 적용하여 O(N + P^2logP + MP^1/2) 라는 시간복잡도로 문제를 풀어주셨습니다!
감사의 말씀을 드립니다.
