티스토리 뷰


오늘은 9월 15일~

2019 KAKAO BLIND RECRUITMENT 온라인 코딩테스트에 참가했다.


올해 있었던 카카오 코드페스티벌 본선에 참가해서 코딩테스트가 면제이지만 한 번 참가해 보고 싶었고 

문제들을 풀어본 뒤 접근방법을 포스팅을 해서 다른 참가자들에게 도움이 되고자 했다.


어제 작년 블라인드 문제들을 풀어보았다. 7문제 5시간에 문자열 파싱문제가 꽤나 나오는 걸 느꼈고 오늘 있을 테스트도 

그럴것이라 생각했다.


1시반 쯤에 꾸물꾸물 일어나 2시 정각부터 테스트를 시작했다. 목표는 2시간 안에 다 푸는것이였는데 3시간 좀 넘게 걸렸다.

4, 5, 6 번에서 자주 안풀어보던 유형이다보니 어떻게 구현할지 설계하는 부분에서 너무 머리쓰기 싫어서 집중을 못했던 것 같다.

PS 안 하다보니 집중력이 떨어진드드으읏


대충 생각한 난이도는 1,2<3,7<<<6<5<4 정도인것 같고 걍 내 뇌피셜 커트는 4문제이다. (전혀 근거 없음)


1,2,3번은 난이도가 매우 쉬웠고 각각 해결하는데 10분씩 걸렸던 것 같다.


1번 문제는 c++ map 자료구조를 이용해서 각 유저 아이디마다 가장 마지막으로 변경한 닉네임을 저장하였고

다시 이 record를 순회하면서 Enter Leave 명령어에 대해서만 최종 닉네임으로 출력해주면 해결가능하다.


2번 문제는 문제에서 정의한 바와 같이 실패율을 구하고 n개의 (실패율,스테이지 번호) 원소를 소팅하는 문제이고 적절히 잘 구한뒤에

O(nlogn) 소팅을 이용하면 해결 할 수 있다.


3번 문제는 가능한 속성조합 2^c-1 개에 대해서 이 속성조합으로 만든 튜플들이 모두 독립적이고 다른 속성조합의 부분집합이 아닌 경우를 세면 된다.

속성 조합 튜플은 해당하는 속성의 string 원소를 일렬로 붙히는 것으로 간단하게 만들 수 있고 c++ stl set을 이용해서 집합의 크기를 쉽게 셀 수 있다.

모든 조합을 순회 하는 것은 for(int i=1;i<(1<<c);i++) 비트마스킹으로 원소를 표현하는 기법으로 쉽게 순회 가능하다.


4번 문제는 효율성 테스트를 통과하기 위해선 조금 까다로운 문제인데 무적권 처음 음식부터 마지막 음식까지 한 번씩 먹는걸 한 사이클이라고 생각하면

그리고 이 한 사이클당 먹게되는 음식 수를 length라고 정의 했을 때, length가 바뀌지 않는 동안은 계속해서 사이클을 돌리면서 음식을 먹고 다시 첫번째 음식앞에 서게 되는것이고

이번 사이클에서 이제 음식을 다 먹어서 사라지면 length가 감소하고 다음 사이클부터는 감소된 length씩 k가 감소한다는 구조를 이해하면 문제에 접근 가능하다. 코딩량은 적은 문제이다.


5번 문제는 주어진 자료를 이용해서 트리를 복원한 뒤 전위, 후위 순회를 리턴해주면 되는 문제이고 현재 높이가 있으면 다음 높이가 항상 정해져 있으므로

다음 높이 층에 대해서 현재 노드가 가질 수 있는 왼쪽 자식의 x범위 내에 임의의 노드가 존재하는지, 오른쪽 자식의 x범위 내에 임의의 노드가 존재하는지를 이분탐색으로 찾아서 노드를 리프노드까지 연결해주면 된다.


6번 문제는 잘 읽고 그대로 구현하면 된다. 예외도 없고 ( 주석도 없고 다른 태그도 없다) 현재 페이지 url 구하고 body 태그에서 링크된 모든 url 구하고 나머지 부분에서 찾아야 되는 word를 모두 찾아 개수를 세어주면 된다.

아마 테케가 약한듯?(글 쓰는 와중에 <a></a>태그 사이에 적힌 문장에 대해서는 단어 탐색을 안했는데 정답으로 인정됐다는걸 알아챔, 사실 단어를 찾아야 되는 영역이 불분명하긴 하다.) 노오오오력으로 푸는 문제라고 생각한다.


7번 문제는 2x3 또는 3x2 인 영역에서 4칸이 같은 숫자이고 2칸이 0이면서 0인칸 위쪽으로는 모두 0임을 만족하는 영역이 있다면 해당영역을 삭제하는 과정을 더이상 불가능할 때 까지 반복해주면 된다. 삼성 역테에 나올만한 유형.


전체적으로 특정한 알고리즘을 사용하는 문제는 없었던 것 같고 그렇기에 문자열 파싱문제가 비교적 많이 나오지 않았나 싶다. 

개인적으로 아쉬운 부분은 4번 문제 같은 경우에는 코포에 자주 등장하는 유형인데 빠르게 못푼게 아쉽다.


어느정도로 접근방법을 자세히 적을지 감이 안와서 일단 간략하게 적어보았고 코드를 보아도 이해가 안되는 부분은 댓글로 편하게 질문 주십숑


https://github.com/baactree/PS/tree/master/kakaoblind2019

'etc. > 코딩테스트 후기' 카테고리의 다른 글

TOPCIT 알고리즘평가 후기  (4) 2017.11.18
댓글
공지사항
최근에 올라온 글
최근에 달린 댓글
Total
Today
Yesterday
«   2024/03   »
1 2
3 4 5 6 7 8 9
10 11 12 13 14 15 16
17 18 19 20 21 22 23
24 25 26 27 28 29 30
31
글 보관함