본문 바로가기

Algorithm283

[BOJ]16946번: 벽 부수고 이동하기 4 N, M 제한이 1000 이므로 벽 한 칸당 BFS를 돌아버리면 O(N^2*M^2)으로 시간초과가 납니다. 그러므로 단 한번만 O(NM)에 BFS를 돌려 모든 컴포넌트 정보를 얻어냅니다. 그 후에 벽에서 이동할 수 있는 칸 계산은 move = 1 + 4방향 컴포넌트의 갯수 합이 됩니다. 그래서 O(NM)만에 모든 벽 정보에 대해 벽에서 이동할 수 있는 칸을 계산할 수 있습니다. 단, 함정이 하나있다면, 00000 00000 00100 00000 00000 이와 같이 벽을 둘러싼 컴포넌트가 동일한 형태일 때 4방향을 다 더해주면 중복이 날 것입니다. 그러므로 컴포넌트를 구할 때 하나의 컴포넌트가 다른 컴포넌트와 구분될 수 있도록 조치를 취해야 합니다, 저 같은 경우는 pair의 second 값을 이용했고,.. 2020. 5. 8.
[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.

티스토리툴바