구글 푸바 챌린지(Google Foobar Challenge) Level 5까지 끝낸 후기!

푸바 챌린지 (Foobar Challenge)란?

구글의 Secret hiring process로, 구글에 검색하다 보면 재미있는 invitation을 주어 문제를 풀면 비공식 hiring process를 진행할 수 있는 챌린지입니다. 챌린지에 대한 자세한 내용은 이전 포스팅을 참고해주시길 바랍니다. 😊

이전 포스팅 : 2020/12/06 - [🌱] - 구글 푸바 챌린지에 참가하고 있습니당 - Google Foobar Challenge

구글 푸바 챌린지에 참가하고 있습니당 - Google Foobar Challenge

저는 이 푸바챌린지를 한 달가량 진행했는데, 사실 더 빠르게 진행할 수 있었지만 조금 쉬엄쉬엄하기도 하고.. 뒤로 갈수록 문제를 받는 게 무서워서 겨우 끝마쳤네요 😅

마지막까지 완수를 했기에, 이렇게 다시 글을 쓰기 위해 찾아왔습니다!

---

푸바 챌린지의 문제는 어떻게 되나요?

Foobar Challenge에 입장하면 보이는 화면! 

푸바챌린지는 총 5단계의 Level이 있고, 각 레벨마다 문제의 수는 다릅니다. 1단계는 1문제, 2단계는 2문제, 3단계는 3문제, 4단계는 2문제, 5단계는 다시 한 문제입니다. 당연히 뒤로 갈수록 문제는 어려워지고, 그만큼 주어지는 시간도 길어집니다.

제가 생각했을 때 푸바챌린지는 비교적 시간은 넉넉하게 주어진 것 같았습니다. 문제를 request 하기 전에는 계속 대기(?) 상태로 있을 수 있고... 문제 하나하나에 걸리는 시간도 정말 충분히 고려해주었던 것 같습니다. 나중에는 약 3주 정도의 시간을 주기도 했었으니까요! (공부하면서 풀어라 이런 의미인 건지..?!)

 

Level 1 

Level 1에서는 한 문제 나오고, 매우 쉬운 문제가 나옵니다. 10분에서 20분 정도면 넉넉하게 풀만한 수준으로 나왔던 것 같습니다. 

레벨 1을 끝내면 뛰어다니는 토끼 한마리가 나옵니다. 이때부터 본격적으로 토끼와의 인연이..!!!

 

Level 2

레벨 2는 프로그래머스 기준으로는 레벨 3~4 수준, 백준으로는 실버 수준의 문제들이 나옵니다. 트리나 그래프의 구조를 모르더라도 그냥 풀 수 있는 문제들입니다. 크게 어렵지는 않았고, 그냥 문제 해석하고 그냥 막.. 브루트포스로 풀면 되는 문제들이었던 것 같습니다. 

Please Pass the Coded Messages

주어진 숫자 배열에서 가장 큰 3의 배수를 만드는 문제였습니다. 3의 배수의 경우에는 자릿수의 합이 3의 배수면 3의 배수라는 성질이 있습니다. 그것을 간단하게 이용하면 되었던 문제였습니다. 푸는데 한 30분 정도 걸렸던 것 같네요.

Hey I already did that

이 문제는 진수의 뺄셈과 관련된 문제였습니다. n진수의 수가 주어졌을 때 n진수를 오름차순 한 x, 내림차순 한 y를 빼고.. 그래서 순환되는 숫자인지 아닌지를 확인하는 그런 문제였습니다. 참고로 이때 영어로 base가 진수를 의미하는 건지 몰라서.... 진짜 이상한 걸로 한참 헤맸던 기억이 납니다. 아니 왜 뺄셈을 하는데 이렇게 되는 거지 계속 이랬던 ^^;

 

Level 3

Level 3부터는 확 어려워졌던 것 같습니다. 그래서 문제도 다 잘 기억하고 있네요!! 제 생각에는 Level 3은 숫자에 대한 센스 + 알고리즘 정도를 보는 것 같습니다. 제가 받았던 문제는 아래와 같습니다.

• Doomsday Fuel
• Find the Access Code
• Bomb, baby!

여기서 가장 첫 번째로 받았던 Doomsday Fuel 문제가 가장 어려웠습니다. (그래서 그 뒤에 문제를 보는 것이 두려웠던..ㅠㅠ)

Doomsday Fuel

Markcov chain이라는 듣도 보도 못한(...) 개념이 적용된 문제였습니다. 문제를 이해하는 것부터가 조금 시간이 오래 걸렸고... 사실 지금도 완전히 이해했다고는 생각하지 않습니다. 대신 여러 가지 소스들을 참고해가며 공부하고 겨우겨우 코드로 작성했네요.

참고한 링크들은 아래와 같습니다.

• MLWiki - Markov Chain
• StackExchange - Markov Chain Help
• 유튜브 설레는 수학 - 마르코프 체인 | 고급수학2 | 행렬 세특 (설명이 짱짱!!👍👍)

정말 겨우겨우 이해하고 겨우겨우 풀었던 기억이 납니다. 너무 어려워서 식은땀이 났던 문제였습니다. 그리고 이 문제부터 시작해서 본격적으로 level 4와 level 5는 수학 파티가 펼쳐집니다.. 앞으로 계속 생각지도 않았던 수학 개념들이 나오기 시작합니다.

Find the Access Code

level 3의 첫 문제가 너무너무 어려워서, 진짜 며칠 쉬고 다시 도전했던 두 번째 문제는 생각보다 어렵지 않았습니다.

x, y, z 세 숫자가 있을 때 x는 y의 약수, 또 y는 z의 약수가 되면 이 (x, y, z)를 lucky triple이라 부르고, 주어진 배열에서 총 몇 개의 lucky triple이 있는지를 찾는 문제였습니다.

여기에는 간단한 아이디어 하나만 생각하면 쉬웠는데, y를 중심으로 생각을 하고 계산하면 되는 문제였습니다. 즉, y를 배열의 처음부터 끝까지 확인하면서 y의 앞에는 x가 오겠고, y의 뒤에는 z들이 올 것입니다. 그러면 한 y에 몇개의 x가 올 수 있고 몇개의 z가 올 수 있는지 경우의 수를 구하는? 비교적 간단한 문제였습니다.

Bomb, Baby!

이 문제는 길게 설명되어있긴 했지만, 한마디로 요약하자면 두 수가 주어졌을 때 값의 차만으로 1, 1을 만들 수 있는지에 관한 문제였습니다.

뺄셈 연산을 계속하게 되면 메모리 초과 에러가 나서 그것을 잘 이용해야 했던 문제였는데, 해답은 나눗셈 연산에 있었습니다. 다행히도 비교적 최근에 비슷한 문제를 Leetcode에서 풀었어서 생각보다 쉽게 해결할 수 있었습니다. (참고 링크 : leetcode.com/problems/broken-calculator )

구글 리쿠르터한테 resume보내볼래????? 웅..

레벨 3을 끝내면 구글 리쿠르터에게 resume를 보내볼래?라는 커맨드 창이 뜹니다.

이때 이름, 메일, cv 링크, 국적 등등을 알아갑니다. 그리고 연락이 오는 경우도 있고 오지 않는 경우도 있다고 해요. 그리고 레벨 3이 끝났다고 모든 챌린지가 끝난 것이 아닙니다. 아직 레벨 4와 레벨 5가 남아있죠.

Level 4

이때부터는 본격적으로 수학 파티가 시작됩니다. 사실, 솔직히 말하자면 level 4의 첫 문제는 넘사벽으로 어렵고, 두 번째 문제는 나쁘진 않았었습니다.

Distract the guards

이 문제를 풀면서 정말 감탄했던 게, 간단한 문제라 생각했는데 알고 보면 엄청나게 복잡한 문제였다는 것입니다. 수학적인 센스와 더불어 약간의 알고리즘? 이 필요했던 문제였습니다. 문제를 크게 생각하자면

1. 두 숫자가 주어졌을 때 큰 수에서 작은 수를 빼는 게 계속 무한루프가 되는지 확인 (예: 1,4 -> 2, 3- > 4, 1 -> 3, 2 -> 1, 4 이렇게 되니 1, 4는 무한루프가 되는 쌍!)
2. 주어진 숫자들을 (1)로 확인해 무한루프면 선을 연결해(?) 그래프를 그리고, 해당 그래프가 최대 매칭을 구하는 문제!

이렇게 되었습니다. 여기서 그래프의 최대 매칭이라는 것이 머리로는 쉬운데 알고리즘으로 구현하는 것이 매우 매우 어려웠습니다.

• 삼성 소프트웨어 멤버십 블로그 - Maximum matching algorithm of “General graph”
• (비슷한 문제) 백준 - 그래프 최대 매칭

그래서... exposed vertex.. alternating path 등등.. 을 생각해서 구현해야 했던 문제였습니다. 코드도 꽤 길게 나왔던 것 같습니다. 어려워서 시간도 며칠 걸렸던 문제였습니다.

 

Free the Bunny Prisoners

level 3과 마찬가지로 첫 문제 때문에 많이 쫄았지만 생각만큼 어렵지는 않았던 문제였습니다.

주어진 숫자 배열의 조합을 구하고 각 조합들의 index를 구합니다. 주어진 숫자가 몇 번째 조합에서 나타나는지를 리스트로 나타내면 되었던 문제로,  원래 조합을 구하던 방식에서 살짝 반대로 생각하면 되었던 문제였습니다. (사실 반대라고 생각할 것도 없긴 합니다..)

영어 해석만 쫄지 않고 풀면 되었던 문제! 

 

Level 5

레벨 5는....... 여러모로 현타가 많이 왔던 문제였습니다.

수학 개념 중에서 번사이드 보조 정리를 이용해야 했던 문제로, 제가 자세히 설명드리기는 어렵고 한마디로 요약하자면

이 식을 구현하면 되는 문제였습니다 ㅎㅎ

참고로 번사이드 보조 정리에 관해서 설명한 글에는 몇 가지 인상 깊었던 글들이 있습니다.

• 수학하는 블로그 - 번사이드 보조정리
• AlgoShitPo Blog - 번사이드 보조정리
• 삼성 소프트웨어 멤버쉽 블로그 - 번사이드 보조정리(Burnside Lemma)

특히나 두 번째 블로그는 설명이 너무 친절하게 잘 되어있어서 놀랐던 기억이 납니다. 

 

---

드디어 끝!!

뛰어다니는 토끼~

마지막 레벨의 문제까지 풀면 보이는 화면입니다. 토끼가 뛰어다니고, 그 밑에 encrypted 된 글자들이 있습니다. 이것은 간단한 코드로 decode 할 수 있습니다.

Success great, Colleague esteemed, Efforts incredible, Achievement unlocked, Rabbits Safe, Foo Win!

감덩... 말을 잇지 못하는..

 

후기

그래서 짧게나마 후기를 드리자면..

수학 지옥....

이 말밖에 떠오르지 않네요...

수학 개념도 약간 고등학생 때나 학부시절에 배우는 수학과는 동떨어져서 정말 삐질삐질했던 것 같습니다. 사실 위의 문제들을 보시면 아시겠지만 gcd(최대공약수), 조합, 팩토리얼, 행렬 등등의 기초 개념들이 많이 나옵니다. 이런 기초~기초~들을 잘~  잘~ 써서 으쌰 으쌰 문제를 해결하면 되는 문제들이었습니다. 그리고 다행히도, 이미 푸바 챌린지를 끝낸 수많은 유저들의 스택오버플로우를 보면서 든든하게 풀 수 있었던 것 같습니다. 하하 

어쨌거나 저쨌거나 구글의 푸바 챌린지는 매우 즐겁고 유쾌한 경험이고! 꿈나무 개발자로서 매우 매우 즐거웠던 시간이었습니다ㅎㅎ!! 그리고 확실히 구글이 어떤 인재를 원하는지 체감할 수 있었던 시간이었던 것 같습니다.(=수학 똑똑이) 예전에 제가 블로그에 구글 인턴 도전기를 썼었는데 (딱 지난해 이맘때네요!!) 그때에도 정말 모든 채용과정이 알고리즘뿐이었던 게 기억이 나네요.. 그런 의미에서 리쿠르터에게 연락은 오지 않을 것 같은 느낌적인 느낌이 강하게 들지만 그래도 정말 정말 재미있었고!! 알고리즘 문제 푸는 게 매우 새로웠던 경험이었습니다. 

올해 초에 jenia님 블로그를 보면서 나도 푸바 챌린지 해보고 싶다~라고 생각했는데 이렇게 기회가 닿아 하게되어 정말 신기하네요ㅎㅎ. 사실 이전까지만 해도 푸바 챌린지가 도시전설인가 했었는데.. 다행히(?) 아니었던걸로😅 ~~ 한 한 달가량 쉬엄쉬엄 하긴 했지만 계속 신경 쓰였던 챌린지를 끝내고 나니 시원합니다.

 

그럼 지금까지 읽어주셔서 감사합니다. 😆