Facebook Hacker Cup 2019 Online Qualification Round

지난 주 토요일 (06/15) 부터 이번 주 화요일 (06/18) 까지, 72시간 동안 Facebook Hacker Cup 2019의 Qualification Round가 진행되었습니다. 토요일부터 당장 풀어봐야지~ 라는 안일한 생각을 갖고 있다가 주말을 귀신처럼 흘려보낸 후 월요일 퇴근하고 부랴부랴 풀기 시작했습니다. 예선은 딱 한 문제만 온전히 풀어도 다음 라운드로 진출하는 방식인데요. 비슷한 대회인 Google Code Jam 과 유사한 방식을 채택하고 있습니다.

저는 시간이 될 때마다 이런 코딩 대회에 참가해보는 편인데요. 항상 귀신같이 예선 진출 이후 본선에서 떨어지는 마법같은 경력을 가지고 있습니다. 사실 본선으로 올라가면 문제 난이도도 꽤 어려워지고 시간 제약 (다른 참가자보다 먼저 풀어내야 함) 도 있어서 본선에서 진출하기가 참 쉽지 않더라고요. 그래도 알고리즘 연습은 꾸준히 하는 거랬으니깐….

이번에도 두 문제를 풀고 예선을 통과했는데요. 맨 앞의 두 문제가 매우 쉬웠고, 또한 별다른 선행 지식 없이 생각만 하면 풀 수 있는 문제라 좋았습니다. 그럼 문제와 함께 짤막한 해설 시작해보겠습니다.

1. Leapfrog: Ch. 1

특이하게도 1번 문제와 2번 문제가 똑같은데요. 2번 문제는 1번 문제에 규칙 하나가 더 추가된 모양입니다. 1번을 풀 수 있으면 2번도 시도해볼 수 있다는 의미이니, 아주 혜자로운 문제가 아닐 수 없습니다. 문제 내용은 다음과 같습니다.

A (대장 개구리), B (부하 개구리), . (연꽃, 갈 수 있는 땅) 이 주어졌을 때, 맨 왼쪽에서 출발하는 대장 개구리가 맨 오른쪽까지 도달할 수 있는지 검사하라.
단, 다음과 같은 제약 사항이 있다.

1. 대장 개구리는 오른쪽으로만 갈 수 있으며, 부하 개구리에 인접한 빈 땅으로 이동할 수 있다. 단, 이동하려면 반드시 1마리 이상의 부하 개구리를 뛰어 넘어야한다. 또한 연속적으로 붙어있는 부하 개구리를 한 번에 뛰어넘을 수 있다.
   -> 즉, 대장 개구리가 마음대로 이동할 수 있는 게 아니고, 반드시 부하 개구리를 뛰어넘어야만 이동 가능하다는 얘기입니다.
2. 부하 개구리는 인접한 빈 땅으로 마음대로 움직일 수 있다.

그러므로 다음과 같은 입력이 주어지면, 출력은 N이 되어야 합니다.

A., ABB

그러나 다음과 같은 입력이 주어지면 출력은 Y가 됩니다.

A.B..BBB., AB.

1. A.B..BBB.: 다음과 같은 형태로 이동할 수 있습니다. AB..BBB. -> .BA.BBB. -> .BABBB.. -> .BABB.B.
2. AB.: 그냥 뛰어넘으면 됩니다.

처음에 이 문제를 접했을 때는 어떡하지? 라는 생각을 잠깐 했는데요. 실제로 A를 움직여봐야 하나? 그럼 B도 움직여야 하고 여간 복잡한게 아닌데? 이런 생각 속에 휩싸였다가 정신을 차리고 손으로 좀 해보기 시작했습니다. 그리고 다음과 같은 궁극의 무빙 (?) 을 발견하였습니다.

AB.B.B.B.

즉 B가 어떻게 주어지든 다음과 같은 형태로 구성하면 A는 무조건 오른쪽에 도달할 수 있습니다. 한마디로, B의 개수가 전체 문자열의 길이 / 2 보다 같거나 크면 됩니다. 더 정확히는, B의 개수가 .의 개수와 같거나 크면 무조건 오른쪽에 도달할 수 있습니다. 자, 이제 알아낸 사실을 정리해 볼까요?

• B가 하나도 없으면 무조건 N
• .가 하나도 없으면 무조건 N
• B의 개수가 .의 개수보다 같거나 크면 Y
• 그 외의 경우는 모두 N

끝입니다. Python으로 구현한 코드는 여기에서 보실 수 있습니다.

2. Leapfrog: Ch. 2

1번 문제와 완전히 동일한데, 딱 한가지만 다릅니다. 바로 대장 개구리가 왼쪽으로도 갈 수 있다. 는 사실입니다. 처음엔 왼쪽으로 가는 게 무슨 의미가 있을까? 라는 생각을 했습니다. 후진하는 꼴 밖에 더 되나… 하던 찰나에, 다음과 같은 용례가 떠올랐습니다.

A..BB..B -> .BBAB.. -> .BB.BA.. -> ..BBBA.. -> .ABBB... -> .ABB.B.. -> ..BB.BA. -> ...BBBA. …

감이 오시나요? 위의 예제는 3개로 예시를 들었지만, 사실은 B가 2개 이상이기만 하면 전진 -> 후진 -> 전진 을 반복하며 무한대로 앞으로 나아갈 수 있게 됩니다. 즉, 위의 1번 조건에서 B가 2개 이상일 때는 무조건 Y 조건을 하나 더 넣어주면 됩니다. 코드는 여기에서 보실 수 있습니다.

이렇게 해서 저는 1, 2번을 풀고 예선을 통과할 수 있었습니다. 그 이후 문제부터는 풀진 않았지만, 3번 문제가 굉장히 짜임새있고 잘 만들어진 문제라, 공유만 하고 글을 마치도록 하겠습니다! 아, 완전히 마치는 건 아닙니다. 본선을 통과하면 글을 또 쓸 수 있을 테니까요. 그럼 그 날이 꼭 오기를 기원하며…

3. Mr. X

“x보다 중요한 건 없지요!” Mr. X씨는 x를 변수로 가지는 부울 식 (Boolean expression) 을 당신과 당신의 친구에게 설명하며 웃고 있었다. 그의 선형 대수 수업 시간은 5분에 한 번씩은 이런 개그로 채워지고 있었다…

Mr. X씨의 수업에서 당신은 단변수 부울 식 (Single-variable Boolean expression) 을 배웠다. 단변수 부울 식이란, 변수 x와 x의 부정 (-x) 그리고 부울 상수 (True/False) 와 이진 부울 연산자 (Binary Boolean operator) 로 구성된 식을 말한다. 올바른 부울 식을 구성하는 요소는 다음과 같다.

1) 변수와 상수의 목록은 다음과 같다.
“x” : 변수 x
“X” : 변수 X의 부정
“0” : 상수 False
“1” : 상수 True

2) 이진 연산자 (binary operator) 는 두 개의 올바른 부울 식을 연산할 수 있으며, 다음과 같은 형식 “([부울 식][연산자][부울 식])” 을 만족한다. 연산자의 목록은 다음과 같다.

“|” : OR 연산자 (두 식 중 하나라도 True면 결과가 True)
“&” : AND 연산자 (두 식 모두가 True면 결과가 True)
“^” : XOR 연산자 (두 식 중 하나만 True여야 결과가 True)

다음 부울 식은 올바른 부울 식이다.
“1” -> 상수 1, 결과는 True
“(x^0)” -> 이진 연산자를 활용한 부울 식
“((X&0)|x)” -> 이진 연산자를 활용한 부울 식

다음 부울 식은 올바르지 않은 부울 식이다.
“(1)” -> 연산자 없이 괄호가 사용됨
“x^0” -> 연산자는 있지만 괄호가 없음
“(X&0|x)” -> 괄호가 부족함

Mr. X씨는 다음 시험이 위와 같은 형식을 만족하는 유효한 부울 식 E를 주고, 변수 x에 특정 값이 주어졌을 때 그것의 결과를 연산 (True/False) 하는 형태의 시험이 될 거라고 얘기했다. 그러나 Mr. X씨와 x의 중요성에 대한 농담에 지친 당신은 시험지를 조작해서 주어진 부울 식을 x에 관계없는 부울 식으로 변경하려고 한다! 정확히는, 주어진 유효한 부울 식에서 몇 글자를 바꾸되 바꾼 결과가 x의 값에 영향이 없으면서도 여전히 유효하도록 바꾸려는 것이다. 당신은 주어진 식의 특정 글자를 바꿀 수만 있고, 새로 추가하거나 지울 수는 없다.

예를 들어, 부울 식 “(X|(0&x))” 은 x가 False일 때는 True, x가 True일 때는 false이다. 그러나 다음과 같이 바뀐다면, x에 어떤 값이 들어와도 무조건 False로 평가된다.
“((X&0)&1)” (2, 3, 4, 6, 7, 8번째 글자를 바꿈)
또한, 위의 예제에서 6글자보다 적게 사용해서 주어진 수식을 x와 관계없는 부울 식으로 바꾸는 것도 가능하다.

부울 식 E가 주어지고 그것을 x에 관계없는 부울 식으로 바꾼다고 했을 때, 해당 식을 x에 관계없는 부울 식으로 바꿀 수 있는 최소한의 글자 개수는 몇 개일까? (단, 이미 x에 관계없는 부울 식이 주어졌다면, 한 글자도 안 바꿔도 된다.)

예제
X
0
(x|1)
((1^(X&X))|x)

예제의 답
Case #1: 1 (X를 1이나 0으로 바꾸면 된다.)
Case #2: 0 (이미 x의 값에 관계 없이 False이다.)
Case #3: 0 (x의 값이 뭐든 True다.)
Case #4: 1 (“((0^(X&X))|x)” 처럼 바꾸면 x의 값에 관계 없이 True다.)

추가 : Mr. X 풀이

최근에 Mr. X 문제를 풀었는데요. 물론 이미 솔루션이 공개된 후라 굳이 길게 적을 필요는 없을 것 같습니다. 근데 홈페이지에 나온 솔루션보다 간단해서 일단 적어봅니다.

• 0, 1, x, X 등의 단변수로 구성된 식은 답이 0 혹은 1이다. (0, 1의 경우에는 바꿔줄 필요 없고, x, X인 경우에는 0이나 1로 바꿔줘야 하기 때문에)
• 변수가 여러 개더라도, 모든 변수는 0, 1, x, X 로만 구성되어 있다. 어떤 연산을 하더라도 0, 1, x, X 에 대해 닫혀있는 결과가 나온다.
• 그렇다면 문제를 축소할 수 있다. 어떤 조건일 때 0, 1을 출력해주면 될까…?