ZOAC 2018 후기 및 풀이

안녕하세요 hellogaon입니다.

2018년 12월 29일, 한양대학교 에리카 알고리즘 학회 '영과일'의 첫 내부대회

Zero One Algorithm Contest 2018(이하 ZOAC 2018)가 열렸습니다!

오프라인 대회에서는 8팀, 온라인 Open Contest에서는 20여명 분들이 참여해주셨습니다.

아무래도 대회 수상자 및 알고리즘 멘토들이 대회 운영진을 맡았고

대부분 신입생들이 대회를 참가하다보니 난이도 조절에는 실패가 있었지만

Open Contest에서 많은 분들이 참여해주셔서 재밌었습니다.

공식적으로 공지하지는 않았지만 출제진들끼리 상의하여 많이 풀릴 거 같은 순으로 배치를 하였음에도 불구하고

출제진의 생각과 푸는 사람의 체감 난이도는 정말 다르다는 것을 새삼 느낄 수 있었고

아쉬운 점도 있었지만 성공적으로 마무리 되어 정말 행복하네요.

문제 출제에 힘써주신 예찬이(fromis_9), 수형이형(dreammusic23),

검수와 운영에 도와주신 재훈이형(jh9277), 재현이(TheKinGoD),

대회에 후원해주신 스타트링크, 바쁜 시간에도 참여해주시고 관심가져주신

영과일 학회원들 및 Open Contest 참가자들께 감사의 인사를 전합니다.

출제진만이 아닌 직접 대회를 개최한 적은 처음이기에

부담도 되고 미숙한 점이 많았습니다.

다음에 또 기회가 된다면 다른 대회로 찾아 뵐 수 있었으면 좋겠네요.

고생 많으셨습니다. 감사합니다.

아래는 문제와 문제의 후기, 그리고 문제의 풀이입니다.

A - 16719번: ZOAC

아쉽게도 많은 분들이 문제를 제대로 이해하지 못하여 틀린 문제이다.

검수진들과 함께 최대한 헷갈리지 않고 문제를 이해할 수 있게 스크립트를 작성하려고 노력하였고 

혹시나 하여 세번째 예제인 'STARTLINK'도 넣어놨지만 예제가 길었던 탓인지

대회 참가자들이 이해하는 데 많은 시간이 걸렸다고 하는 문제이다.

다행히도 Open Contest에서는 많은 분들이 풀어주셔서 고마웠다.

구현 문제이다.

S = abcab 를 예제로 들어보자.

이 때의 답은

a

aa

aab

abab

abcab

가 된다. 

규칙을 자세히 살펴보면은 매단계마다 선택한 문자의 인덱스를 i라 하면

재귀적으로 S[i+1:]를 사전 순으로 뽑아라! 와 같은 것을 알 수 있다.

만약 다음 단계로 넘어가기 위하여 선택할 수 있는 인덱스가 2개 이상이 있을 경우

가장 앞에 있는 인덱스(i)를 선택하여야 S[i+1:] 에서 다음 인덱스로 접근 할 수 있기에

답을 만드는 방법이 여러가지가 있을 경우 앞에서부터 순차적으로 채우면 된다는 것을 알 수 있다.

이과 같은 재귀적인 방법으로 O(N^2)만에 답을 구할 수 있지만

좀 더 문제의 난이도를 낮추기 위하여 규칙을 완벽하게 찾지 않아도 풀 수 있도록 하였다.

매 번 추가하지 않은 글자를 넣어보면서

사전 순으로 가장 앞에 오는 문자열, 같다면 인덱스가 더 작은 글자를 넣어주면서

출력해주는 과정을 계속 반복하면 풀 수 있는 문제이다.

B - 16720번: BAZE RUNNER

대회 중 데이터에 문제가 발생했던 문제이다.

나와 검수진 모두 '만약 가장 왼쪽, 오른쪽 칸의 벽이 밀렸을 경우 반대편 끝에서 나온다.'라는 조건을 잊어버렸다.

정말 다행히도 대회 등수가 바뀌는 일은 없었지만 앞으로는 이런 일이 있지 않도록 반드시 조심해야겠다.

물론 데이터가 문제가 있다는 공지의 영향도 있겠지만 생각보다 이 문제가 많이 풀리지 않아서 놀랐다. 

탐욕법 문제이다.

두가지 행동 중 하나를 할 수 있을 때 몇 번의 행동으로 도착할 수 있는 지를 묻는 문제이다.

언뜻보면 BFS인가?라는 생각을 할 수 있는 문제지만

각 줄마다 오직 하나의 길만을 존재하기 때문에 쉽게 문제에 접근 할 수 있다.

C - 16721번: Structure of Balanced Networks

한번씩 틀리게 하여 당황하게 하자!!라는 역할을 잘 수행한 문제이다.

언뜻보면 복잡해보이는 문제이나 읽어보면 쉬운 문제이기에 바로 제출을 시도해보지만

유의 깊게 보지 않으면 놓칠 수 있는 메모리를 제한 시켜

좀 더 다른 방법을 찾도록 유도하는 문제이다.

완전 그래프가 입력으로 들어오기에 어쩔 수 없이 입력의 크기가 커지게 되었고

데이터를 생성 및 검증하는 과정이 너무 오래 걸려 어쩔 수 없이 메모리를 많이 줄이게 되었다. 

N의 제한을 10,000으로 하고 싶었지만 데이터 파일의 크기가 너무 커서 슬펐다.

탐욕법 문제이다.

특정한 조건을 만족하는 완전 그래프가 주어질 때 노드 B, C의 관계의 부호를 묻는 문제이다.

물론 입력을 다 저장해놓고 출력하는 방식으로 풀 경우 '메모리 초과'를 받도록 메모리를 설정해놨다.

이 문제는 그래프의 조건을 이용하여 좀 더 문제를 간단하게 풀 수 있다.

약간의 힌트는 A, B가 아닌 B, C의 관계를 묻는 것이다.

이 때 Structure of Balanced Networks(이하 SBN)는 노드 3개를 골랐을 때 간선이 + + +, + - - 로

이루어져야함을 이용하여,

A와의 관계가 +인 노드, -인 노드를 따로 저장해놓는다.

A와 B의 관계가 +, A와 C의 관계가 +라고 가정하자. 그러면 SBN의 성질 상 B와 C의 관계는 +이다.

위와 같은 방법으로 모든 경우에 대하여 생각해보면

A와 B의 관계, A와 C의 관계가 같을 경우 B과 C의 관계는 +, 아닐 경우 B의 C의 관계는 -라는 결론이 나온다.

그러므로 아무 정점에 대하여 그 정점에 대한 연결관계만 저장해놓으면 풀 수 있는 문제이다.

D - 16722번: 결! 합!

더지니어스에서 나왔던 결합게임을 이용한 문제이다.

이 게임을 아는 사람은 지문을 자세히 읽지 않고도 쉽게 풀 수 있지만

모르는 사람들에게는 지문의 길이가 긴 편이라 그런지 구현문제임에도 불구하고

많이들 시도하지 않았던 것 같다.

구현 문제이다.

문제에 적혀 있는 '합'의 조건을 코드로 구현한 뒤 나올 수 있는 모든 '합'을 미리 구해 놓는다.

이후 문제에 적혀있는 점수 환산 방법을 이용하여

잘 구현해주면 풀 수 있는 문제이다.

E - 16723번: 원영이는 ZOAC과 영원하고 싶다

오히려 이 문제가 많이 풀려서 신기했다.

아무래도 수학문제이고 한번에 이해하기는 힘든 문제이기에

풀지 않고 넘어가지 않을까라고 생각했지만 많은 팀들이 도전하였다.

정말 많은 스크립트의 변경이 있었던 문제라 무사히 내용이 전달이 제대로 되길 바랐는데

많은 분들이 잘 이해하고 풀어줘서 고마웠다. 

수학 문제이다.

많은 풀이 방법이 존재하지만 출제자의 풀이는 아래와 같다!

아래 이미지를 참고하자.

F - 16724번: 피리부는 사나이

많은 풀이를 가지고 있는 문제이다.

좀 더 편하게 푸는 풀이가 존재하지만 만약 그 풀이를 모른다고 하더라도

BFS, DFS를 이용해서도 충분히 풀 수 있게,

제대로 BFS, DFS에 대해서 모를 경우 오히려 틀릴 수도 있는 문제로 만들었다.

많은 친구들이 DFS로 접근하다가 구현이 꼬인 거 같아 아쉬웠다.

DFS, BFS로도 풀 수 있지만 정해는 상호베타적 집합(유니온 파인드)이다.

N x M 지도가 주어졌을 때 이 지도의 사이클의 개수를 찾는 문제이다.

물론 사이클의 개수, 즉 SCC로도 이 문제를 풀 수 있겠지만

지도 한 칸이 오직 한 칸만을 가르키기에 상호베타적 집합 자료구조를 이용하면 더 쉽게 구할 수 있다.

자신의 칸과 자신의 칸에 왔을 때 이동해야할 칸을 같은 집합으로 묶어주는 과정을

모든 칸에 대하여 처리하게 되면은 집합의 개수로 답을 구할 수 있다.

아래 이미지에는 DFS로 컴포넌트의 개수를 찾는 과정만 하였을 때의 예외도 나타내고 있다.

DFS, BFS를 자주자재로 구사할 정도가 아니라면 구현 상에 실수가 있을 수도 있으니 조심하자!

G - 16725번: 다항 계수

아마 여러가지 풀이 방법이 있을거라 생각한다.

문제 하단에 있는 노트를 참고하여 손으로 직접 써보다보면

이렇게 하면 되겠구나! 하는 풀이가 정해였지만

일반화된 공식이 있을까봐 약간 걱정된 문제였다.

정해는 DP이다.

구현해보지는 않았지만 아마 빠른 거듭제곱처럼 분할정복으로도 풀릴 거라 생각한다.

모든 항의 계수가 1인 다항식의 거듭제곱을 전개하였을 때의 계수를 구하는 문제이다.

이게 설명하기는 정말 어렵지만 문제 하단에 있는 노트와 같이

여러 예제를 그리다보면 쉽게 이해할 수 있을 거라 생각한다.

대략적인 풀이는 아래와 같은 그림처럼 구할 때 한 칸씩 밀려가면서 작성한 뒤

열마다 더해주게 되는데 이 과정을 다하지 않고 점점 더해가면서 빼줄 건 빼주는..인데

정말 설명하기가 어려운 거 같다.

수식은 아래 이미지에 첨부한다.

H - 16726번: 영과일 학회방

어느정도 PS를 하신 분이라면 거의 웰노운의 문제일 것이다.

나의 경우 이와 같은 유형을 처음 접했을 때 굉장히 신기했기에

이와 관련된 유형은 꼭 한 번 알려주고 싶어서 낸 문제이다.

뭔가 어디서 많이 본 문제 같기는 했는데 내가 못찾은 것인지는 모르겠지만

아무리 찾아봐도 같은 문제는 없기에 낸 문제이다.

이분 매칭 문제이다.

학회방 바닥 도면이 주어졌을 때 이를 1 x 2, 1 x 1 타일을 최소 몇개를 이용하여

덮을 수 있는 지 묻는 문제이다.

넓이는 일정하기에 최대한 많은 1 x 2타일을 깔아야한다는 것이 첫번째 아이디어이다.

그다음에는 이제 1 x 2를 어떻게 깔면 될 것인가?인데

이는 이런 격자판에서 자주 응용되어 나오는 형태로 격자판을 체스판으로 생각하여

이분 그래프로 변환한다.

이렇게 진행하였을 때 1 x 2타일은 무조건 하나의 흰색 칸과 하나의 검은색 칸만을

차지해야한다는 것을 알 수 있다.

이를 이용하여 1 x 2 타일을 놓을 수 있는 바닥을 서로 이어 준 뒤

이 때의 최대 매칭을 찾아주면 이 값이 가장 많이 1 x 2 타일을 놓을 수 있는 수이다.

1 x 1 타일은 '덮어야 하는 넓이 - 2 × 최대 매칭의 크기'이 되며

정답은 이 둘을 합한 '덮어야 하는 넓이 - 최대 매칭의 크기'이 된다는 것을 알 수 있다.