서론
Apple Developer Academy @ POSTECH에서의 생활, 포항에서의 생활이 막바지에 이르고 있다.
나는 올해가 지나고 내년이 되면 다시 복학을 할 예정이고, 졸업까진 4학기 정도가 남아 있으며, 군 문제가 아직 해결되지 않은 상태이기 때문에, 당장 취업을 할 생각은 크지 않았지만, - (그것과는 별개로 이런 상황의 대학생을 누가 채용하겠는가.)
평소에 알고리즘 문제들을 꾸준히 조금씩은 풀어 오기도 했고, 백준 티어도 곧 플래티넘을 찍을 것 같고, 알고리즘(코테) 스터디도 계속 열고, 운영하고 있었는데.. 정작 코딩테스트는 한 번도 본 적이 없었던 것이다.
뭐 그런 것도 있고, 카카오의 코딩 테스트가 다른 회사들에 비해 어려운 편이기도 하다고 들었으며, 슬슬 주변에서 동기들과 지인들은 취업 준비에 박차를 가하고 있고, .. 나도 자소서나 포트폴리오를 정리해야 할 때가 되기도 했고,
무엇보다 그냥 코딩 테스트 한 번 경험해보고 싶었다.
그래서 한 번 지원해 봤다.
코딩 테스트 준비를 좀 하고 시험을 치르고 싶었는데.. 애플 아카데미 프로젝트가 너무 바쁜 탓에, 전날 21년 기출문제 3문제 정도를 푼 것 밖에 하지 못했다.
문제별 풀이 회고
문제를 유출하면 안 된다는 사항이 있었던 것 같아.. 혹시 몰라서 문제의 전체 내용과 풀이는 자세히 적지 못할 것 같고, 체감 난이도나, 내가 풀었던 방식, 걸린 시간 등을 기억을 되짚어 써내려가 본다.
코딩 테스트를 응시했던 사람이면 적당히 기억날 만큼...
프로그래머스에 문제가 공개되면, 그 때 못다 풀었던 문제들도 솔브업 하고 블로그에 풀이를 다시 기록할 것!
아니 어짜피 프로그래머스에 기출문제 다 공개할거면서 왜지?
그래도 카카오는 기출문제 다 공개해줘서 너무 좋다.
1번 문제 (solved)
1번 문제는, 정말 단순한 구현 문제가 나올 것으로 예상했는데, 의외로 '정말 단순' 보단 '조금 단순' 한 구현 문제가 나왔던 것 같다. ㅋㅋㅋㅋ
그래도 뭐 충분히 빠르게 구현해내고 넘어갈 수 있던 문제였다.
대충 2차원 배열로 A가 B에게 선물을 준 횟수를 저장하고, 1차원 배열로 선물지수를 저장해 조건에 맞게 답을 냈다.
이 문제를 풀고 2시 12분즈음이였던 것 같다.
13분 정도 걸렸고, 정답이였다.
2번 문제 (solved)
2번 문제는, 처음 보고는 굉장히 당황했다.
생성된 정점, 그리고 3종류의 그래프 각각의 개수를 구하는 문제였는데, 바로 떠오른 것은 DFS나 Union-Find로 cycle의 개수를 구해서 푸는 것.
그런데 아마 정점이였나..? 최대 개수가 100만개였던 걸로 기억한다.
2번이라고 대충 풀었다가는 금방 시간초과가 뜰 것 같았다. 그래서 그래프 모양마다의 규칙을 좀 찾다 보니.. 대충 규칙이 금방 보였다.
최근에 위상 정렬(Topological Sort) 문제를 몇 번 풀었던 기억이 있는데, 그게 굉장히 도움이 되었던 것 같다. 정점마다의 진입 차수와 진출 차수(in-degree / out-degree)를 잘 째려보면 됐던 문제였음.
모든 정점의 진입 차수, 진출 차수를 세어 저장해 놓고, 이를 이용해 규칙에 따라 그래프의 개수를 구하면 문제가 쉽게 풀렸다.
이 문제를 풀고 나선 2시 43분즈음이였다.
30분 정도 걸렸고, 정답이였다.
1, 2번을 1시간 이내에 풀어내는 것이 1차 목표였는데, 성공했다!
3번 문제 (0.5 solved)
6개의 숫자가 쓰인 주사위를 반씩 나누어 갖고, 주사위를 던져 눈의 합이 높은 쪽이 이기는 게임에서, 어떤 주사위를 가져가야 제일 높은 확률로 이길 수 있는 지 구하는 문제.
주사위의 최대 갯수가 10개였고,
Brute-Force로 푼다면, 6^10 * 10C5 의 경우의 수가 존재하기 때문에..
당연히 Brute-Force로는 풀리지 않을 것 같았다.
그래서 일단 패스하고 4번으로 넘어갔다.
이후 2시간 정도를 남기고 돌아왔을 땐, 일단 Brute-Force로 구현해서 부분점수라도 받자- 하고, Brute-Force로 구현하여 절반 정도를 맞췄다.
그 이후엔 DFS로 기저 조건을 이런저런 방법으로 걸어 시간복잡도를 줄여 보고자 했지만, 잘 풀리지 않았다.
4번 문제 (0.5 solved)
얘는 부분 점수가 있었는 지 잘 기억이 안 난다.
카드 뽑기 게임을 하는 데, 한 라운드에 두 장을 뽑고, 뽑은 카드를 가지려면 코인을 소모하고, 라운드를 마칠 때 합이 정해진 숫자(카드수+1)가 되는 2장의 카드를 버려야 계속 진행할 수 있는 게임을 최대 몇 라운드까지 진행할 수 있는 지 구하는 문제였다.
카드를 뽑는 순서는 정해져 있었고, 결국 문제가 되는 것은 라운드마다 어떤 카드를 버리고 가질 것인가 였는데, 이 모든 경우의 수를 다 고려해야 한다고 생각해, 재귀를 이용한 Top-Down DP로 풀이했다.
테스트케이스 절반 정도를 맞췄고, 끝날 즈음 다시 생각해 보니 그리디로 풀면 어떨까 싶긴 했는데, 단순히 그리디로 구현만 하기엔 딱 봐도 오답이고.. 해서 생각이 안 나 그냥 접고 5번으로 넘어갔다.
5번 문제 (solved)
삼각형으로 그득그득한 도형을 1개짜리 삼각형으로 채우거나, 두 개를 이은 마름모 모양으로 채우거나 - 둘 중 하나를 택해 전체 큰 도형을 채울 때, 가능한 경우의 수를 구하는 문제였다.
한 10분정도 생각해 보니, 딱 봐도 DP일 것 같아, 메모지에 그림을 그려가며 규칙을 잘 찾아봤다.
아이디어는 꽤나 간단했으나, 생각해내기는 꽤 쉽지 않았다.
대충 말해보자면, 한 큰 삼각형/마름모 (삼각형 3개, 4개) 단위의 맨 오른쪽 마지막 삼각형을 1개짜리로 채워 둘 것인지, 2개짜리 마름모로 채워둘 것인지의 케이스를 나누어 Bottom-Up DP로 접근해, 2차원 배열을 채워 나가면 풀렸다.
풀고 보니 코드가 30줄도 안 됐던가.. 그랬던 것 같다.
약 40분 정도가 걸렸고, 풀었다.
후기
재밌었다.
처음 보는 코딩 테스트였는데, 테이크아웃 해온 아아 한 잔 때려부으면서 긴장하며 풀어 봤다.
대충 3.5~4솔정도를 했는데, 아마 졸업도 많이 남고 병역 문제도 있어서, 채용 연계형 인턴인 만큼 서류 탈락하지 않을까 생각한다. (그래도 면접 보러 오라고 하면 가보고.. 인턴 시켜주면 무조건 하고 싶다 ㅎㅅㅎ)
일단 애플 아카데미 프로젝트가 짱 바빠서 이거부터 잘 마무리해야겠다.
정직원 하게 해 주면 자퇴하고 싶다.