본문 바로가기

알고리즘261

[2018 카카오 기출] 자동완성 트라이 자료 구조로 해결할 수 있는 문제입니다. 탐색을 O(L)에 할 수 있습니다. 먼저 입력받은 문자열에 대해 트라이를 만들고, 다시 한 번 더 순회하면서 정답을 구하면 됩니다. 트라이는 상태정보로 child를 가지고 있습니다. 특정 노드에 있는 알파벳이 insert 메서드에 호출될 때 마다 child += 1을 해줍니다. 즉, 자신이 완성된 뒤에도 누군가 자신을 호출했다면 그 단어는 자신과 자식관계가 되는 셈입니다. 자동완성 기능을 통해 더 이상 탐색을 안해도 되는 경우는 현재 탐색하는 알파벳에서 남은 문자열이 하나밖에 없는 경우이고, 그 때 child 값은 1입니다. 그래서 그 높이까지 탐색하도록 find 함수를 작성하면 됩니다. 2020. 5. 8.
[2019 카카오 기출] 징검다리 건너기 스톤 배열 크기를 N이라 했을 때 정렬을 수행하고 선형탐색을 통해 건너려고 하면 O(N^2)이 되어 시간초과가 나게 됩니다. 결국 특정 높이에 대한 탐색을 O(N)이 아닌, O(logN)에 해야하므로 이분 탐색으로 접근해볼수 있습니다. 통과한 니니즈 친구들의 수를 F라고 했을 때, 각 돌은 F만큼 높이가 감소합니다. 이 감소한 높이로 인해 연속으로 0이 되는 돌의 개수가 K이상이면 더 이상 친구들은 지나갈 수 없습니다. 그래서 특정 인원 수 M명이 지나간 후에 디딤돌을 더 지날 수 있는지 없는지를 파악해서 이 M값의 상한선을 구하면 그게 답이 됩니다. 2020. 5. 6.
[2019 카카오 기출] 불량 사용자 배열 크기 제한이 크지 않으므로 팩토리얼로 경우의 수를 생성해도 시간초과가 나지 않습니다. user_id 목록을 next_permutation을 통해 모든 경우의 수를 생성해주고, 이를 banned_id 와 비교해줍니다. 포함되는 경우의 수는 비트연산자 & set을 통해 특정 상태 나타내는 하나의 수를 set에 저장하였습니다. set에 들어있는 수는 banned_id 리스트와 일치하는 user_id의 유일한 목록을 나타내므로 set에 들어가있는 원소의 수가 정답이 됩니다. 2020. 5. 6.
[2019 카카오 기출] 호텔 방 배정 [문제 해설: https://tech.kakao.com/2020/04/01/2019-internship-test/] 문제 해설을 보고 해결한 문제입니다. 구현 시 중요한 부분은 두 가지 입니다. 1. 링크드 리스트와 비슷한 자료구조로, 노드가 생성될 때 자신의 번호 + 1를 부모노드로 가지도록 만들어줍니다. 2. 자신의 부모 노드 번호를 찾기 위해 find 함수를 구현 시 O(K)가 아닌 O(log(K))만에 탐색하도록 구현해줘야 합니다. 2020. 5. 6.

티스토리툴바