카카오 Code Festival 예선 참가 후기

오늘은 카카오 코드 페스티벌이 있었다. 1시부터 7시까지 6시간 동안 6문제를 푸는 온라인 예선전이었다.

문제를 푸는 방식이 탑코더와 비슷하게 함수를 구현하는 방식이었다. 채점환경도 clang이고 약간 낯선 환경이었지만 뭐 크게 상관없었다.

6문제를 A, B, C, D, E, F로 보면 난이도는 A < B < E < D < F < C 순으로 보인다. C가 의외로 생각해줘야 하는 예외가 많고 F는 비교적 풀이만 생각해내면 구현은 어렵지 않을 것 같았다.

대회 결과는 { A,B,C,D,E } 5문제를 해결하였고, 아마도 본선에 진출할듯싶다. 

간단하게 풀이를 적어보자면

A. 

2차원 맵에서 색칠된 부분이 몇 개인지 최대로 색칠된 영역은 몇 칸인지를 구하는 문제였다. 간단한 2차원 플러드필 문제이다. 

B.

2차원 격자에서 좌측 상단에서 우측 하단으로 가는 경우의 수를 구하는 문제인데, 각 칸마다 type이 있어서 지나갈수 있는 칸, 없는 칸, 방향을 바꿀 수 없는칸이 정해져있다. 3차원 dp로 해결 가능하다. 

C.

단어들로 이루어진(단어는 알파벳 대문자로 이루어진다.) 문장이있다.(문장은 단어들로 이루어져 있고 두 단어 사이는 단 하나의 공백만 존재하고 문장의 맨 앞과 맨 뒤는 공백이 아니다.)

이 문장을 특수문자(여기서는 알파뱃 소문자이다.)로 수식할 건데 2가지 방법이있다.

1. BAACTREE라는 단어가 있을 때  pBAACTREEp 와 같이 단어의 맨 앞과 맨 뒤에 특수문자를 붙이는 방법

2. BAACTREE라는 단어가 있을 때 BaAaAaCaTaRaEaE 와같이 단어의 글자 사이에 특수문자를 넣는 방법

(한 방법은 하나의 특수문자로만 수식하고, 한 단어는 최대 2가지 방법으로 수식가능하고, 한 단어에서 한 가지 방법을 2번 사용하는 건 안된다. 이미 사용된 특수문자는 다시 사용할 수 없다.)

위 2가지 방법과 공백을 제거한 수식된 문자열이 주어졌을 때 원래 문장을 복구하는 문제이다.

여러 가지 방법을 생각해 봤다가, 그리디라고 결론짓고, 케이스를 나누었다.

현재 인덱스에서 무적권 단어가 시작한다고 정하고

1. 대문자인 경우

1. 그다음 문자가 대문자인 경우

대문자끼리는 무적권 떼어놓는게 여러모로 이득이다. 현재 문자까지만 단어로 생각

2. 그다음 문자가 소문자인 경우

그 뒤로 해당 소문자가 몇 개 있는지 판단하여 정리했다.

1. 1개인 경우

AaA와 같이 두 문자사이에 하나의 특수문자로 수식된 경우이다. 

2. 2개인 경우

aBBBa나 BaBaB와 같이 한 단어를 수식하거나 한 단어가 3글자로 이루어진 경우이다.

후자의 경우가 사실 B B B 문장의 가운데 단어를 수식하는것과 동치이고 전자의 경우로 몰아서 예외처리하는것이 더 쉬움.

3. 3개 이상인경우 

무적권 한 단어 내부에서 글자사이를 수식하는 경우이다.

불가능하면 invalid임. 

2. 소문자인 경우

소문자로 시작하는 경우 현재 소문자로 다음 소문자까지 포함되는 단어가 수식되므로 다음 소문자의 위치를 찾고 가능 여부를 판단.

     

대충 위의 케이스를 잘 구현하면 된다.

D.

*++로 이루어진 문자열이 있을 때 시작값은 1이고 *는 x3 +는 +1값을 증가시킨다. (*+(*++)+) 와 같이 순서만 맞으면 모두 valid한 문자열이다.

이렇게 문자열을 만들 때 n값이 되는 문자열의 수를 구하는 문제이다. 

ex) *++ = 5, **++++ = 13, *++*++ = 17

뒤에서부터 문자를 채운다고 생각하면 *는 항상 +가 2개 이상 채워졌을 때부터 사용가능하다. 따라서 현재까지 +를 몇 개 사용했는지와 숫자 몇을 만들어야 하는지 2개를 인자로 가지고 가면 완전탐색함수를 구현 할 수 있고 map을 이용하여 메모이제이션 가능하다.

내용 추가)

백준 1로 만들기 문제와 비슷하게 생각하면 된다. 현재 n을 가지고 있고 적절한 - 연산과 / 연산으로 1을 만들고 싶은 상황이다. 하지만 문제 조건에 의해서 / 연산은 - 연산을 2스택 이상 모았을 경우에만 사용가능하다. 또한 1이 되었을 때 - 연산으로 모은 스택을 / 연산으로 다 활용하여 남은 스택이 0이 되야 한다. 따라서 - 연산을 최대 40번만 사용 가능하다. (*******++++...이 제일 작음 이때 최대로 붙이는 문자열이 20개) 이러한 제한을 두고 완전탐색 코드를 짠후 stl map을 이용하여 메모이제이션을 한다.

코드는 다음과 같다.

E. 

비교적 자명하고 쉬운문제이다. n개의 점중 2개를 뽑아 직사각형의 대각선으로 삼고 이 직사각형 내부에 점이 없는 직사각형은 총 몇 개인지 묻는 문제이다.

좌표 압축하고 n*n 누적합 테이블 만든 후 n^2으로 점 2개를 뽑고 사각형 구간합을 구해서 0인 경우만 세어주면 된다.

F.

1번 정점을 루트로 하는 2개의 다른 트리가 주어졌을 때 이 2개의 트리에서 1번을 포함하고 서로 최대한 공통된 부분 트리의 크기를 찾는 문제이다.

직접 제출 해본게 아니라 입풀이인데, f(a,b) = a를 루트로 하는 서브트리, b를 루트로 하는 서브트리 에서 최대 공통 서브트리 집합의 크기를 리턴하는 함수가 있다고 하면 a의 자식과 b의 자식을 서로 매칭하는 문제인데 이 부분에서 mcmf를 사용할 수 있고, 서로 매칭하는 가중치를 다시 f(c,d) 꼴로 구하면서 메모이제이션 하면서 찾으면 될 듯싶다.