Google foobar 2022
오늘 구글 foobar 챌린지에 초대장을 받았다. 동시성 프로그래밍 관련해서 공부를 하다가 식사하러 다녀왔는데 갑자기 브라우저가 깨져보이고 초대장이 와 있었다. 처음에는 누가 피싱사이트 틀어놓은거 아닌가..? 하고 의심했지만 뭔가 구글에 이런 이스터에그가 있다는 카더라도 듣긴 했었어서 긴가민가 하는 마음으로 들어가봤다.
처음에는 갑자기 웹에서 콘솔창이 나오길레 뭐지 하면서 읽어보니 lambda 뭐라뭐라 하는 텍스트가 보였다. 그래서 속으로는 나는 람다를 검색한적이 없는데..? 하면서 자연스럽게 여기가 어딘지 pwd를 쳐보았다. 게스트 계정이라 그런가 오류만 내뱉고 나가려는 사이에.. 다행스럽게도 경고문이 눈에 들어오면서 이 페이지를 나가면 재접근을 못하니 로그인해두라는 문구를 통해 로그인을 해두었다..
그리고 조금 리서치를 해보니 구글에서 진행하는 이스터에그가 맞다고 한다..! 말로만 듣고 화면을 직접 본적이 없어서 조금 당황스러웠지만.. 어쨋든 알아보니 ps관련 문제가 주어지고 해당 문제를 제한시간 내에 푸는 방식인거 같다. 듣기로는 자바랑 파이썬만 지원한다는데… 하필 둘다 ps용으로는 사용하지 않는 언어들이라.. 그나마 익숙한 자바로 진행해야할꺼 같다..(c++의 강력한 내장함수를 직접 만들어야할 필요가 있을 듯 하다..)
어쨋든 저번주부터 릿코드 하드를 풀기 시작했으니 어느정도 만족할만한 풀이를 만들어내기 시작하면 챌린지 도전을 시작해야겠다! (챌린지 시작을 하지 않으면 제한시간은 없다고 한다)
Level1
Minion Work Assignments
레벨 1은 문제 자체는 어렵지 않았던거 같다. 다만 ps를 c++로 하다보니 자바로 푸는거에 어색함이 많이 있었던거 같다. Map Set같은 경우에도 인덱스 오퍼레이션이 지원안되고, 오퍼레이션 오버라이딩도 지원 안되다보니 c++로 ps를 주로 했던거였는데 다시끔 느끼게 된다. 그래도 이 생각은 레벨3에서 BigInteger로 문제를 쉽게 풀 수 있게 되면서 생각이 조금 바뀌게 된거같다.
Level2
Gearing Up for Destruction
이 문제는 주어진 내용을 수학적으로 해석하려던 덕분에 쉽게 접근할 수 있었다. 결국에 못의 개수가 홀수개냐 짝수개냐에 따라 분모의 값이 달라지고 나머지 작업은 똑같았다. 다만 식으로 풀어가는 과정이 시간이 좀 걸리긴 했다.
Ion Flux Relabeling
Full Binary Tree를 후위순회로 돌 때 방문하는 인덱스의 정보를 계산하는 문제였다. 처음에 트리를 그려놓고 인덱스 계산하는데 필요한 데이터인 레벨과 자식 위치 정보를 뽑아냈고, 그 다음에 레벨과 자식 위치정보를 계산하는 공식을 구현했다. 레벨과 자식 위치 정보를 계산하는 과정에서 괜시리 바텀업에 눈이 가서 이쪽으로 뚫어보려 했는데 Full Binary Tree라 탑다운으로 내려가면 쉽게 구할 수 있는 문제였다…
Level3
Doomsday Fuel
이 문제를 처음 접했을때 이 내용을 정확히 산출해내는게 가능해? 라는 생각이 들었고 관련 논문과 개념을 읽다보니 결국에 수렴하는 값에 대한 결과를 찾아내는거군 이라는걸 깨닳았다. 문제 자체에 녹아있는 개념과 이론은 어려운데, 문제는 풀어내는데에는 해당 공식을 구현하면 되는거라 다행이였다. 구현하는데 제일 어려웠던 부분은 아무래도 F = (I - Q)^-1 부분이 제일 어려웠다. det나 adj의 공식을 구현하기 위해 유투브나 수학 블로그들을 찾아가며 구현했다. 나중에 다른 레벨 3들을 다 풀고 느낀건.. 이게 레벨3가 맞아? 라는 생각이였다. 동기가 foobar challenge 유투브 링크를 던져줬는데 여기선 레벨5라는데..
Fuel Injection Perfection
앞의 문제를 새벽 4시까지 풀고 잔 다음에 다음날 아침에 일어나서 바로 풀었던 문제였다. 앞에같은 문제들이 레벨3에서 또 나올테니 설날이라서 시간이 여유있을때 풀어두고 다음 연휴때 이어가려고 했었는데 그래도 앞에 문제보단 어렵진 않았다. 아마 백준에서 비슷한 문제가 있었던거 같은데, 엘리스랑 밥이 앞으로 한칸, 뒤로 한칸, 순간이동(*2)로 워프했을때 N을 몇번만에 만들 수 있는지에 대한 문제랑 같아서 그래도 쉽게 풀었다. 일단 String으로 필요한 연산인 plus, minus, devide를 다 구현해놓고 갑자기 생각이 스친 BigInteger… 덕분에 쉽게 풀었다..^^;;
Bomb, Baby!
이 문제도 수학적으로 접근하려고 써내려가다 보니 규칙이 보여서 규칙만 구현하면 풀렸던 문제였다. 그러나 역시 또 decimal값이 string으로 들어온다.. 또 BigInteger덕분에 어렵지 않게 풀 수 있었다.
