출처 메두사와 전사들 접근 복잡한 문제인만큼 구현하면서 순차적으로 처리해야 할 과정이 많은데, 이에 필요한 알고리즘을 정리해보면 다음과 같습니다. 메두사의 이동경로 구현 BFS + 경로 역추적 시선 생성 배열 탐색 구현 병사 이동 및 공격 배열 탐색 구현 알고리즘 자체는 어렵지 않으나, 배열 탐색을 구현하는 과정이 복잡합니다. 메두사 이동경로 구현(BFS) 메두사가 이동하는 과정에 장애물이 있기 때문에, BFS를 통해 미로를 탐색하는 최단경로를 구해야 합니다. 또한, 이동경로를 다시 돌면서 병사들과의 상호작용을 확인하기 위해 이러한 경로를 별도 배열에 저장해야 합니다. ...
출처 수식 최대화(2020 KAKAO Internship) 접근 완전탐색(DFS) 각 연산자의 우선순위를 변경하면서 전체 탐색을 하고, 변경된 우선순위마다 수식을 계산해서 최댓값을 갱신합니다. 연산자 순서에 따라 결과가 달라지므로, 순열(Permutation)에 해당합니다. 다양한 구현방법이 있지만, 개인적으로 다양한 조건을 만족하는 순열(조합)을 빠르게 구현할 수 있는 DFS를 선호합니다. 3가지 연산자만 있으므로, 모든 경우의 수를 구해도 6가지이기 때문에 시간복잡도는 충분합니다. 후위 표기 변환(InFix to PostFix) 보통 사람이 계산을 할 때는 A + B * C의 형태로 수식을 써서 계산을 합니다. 이 때, A와 B 사이에 연산자가 있는 형태를 중위 표기(InFix)라고 합니다. ...
출처 백준 1005 ACM Craft 접근 완전탐색(BFS) 특정 건물이 나올때까지 각 건물들을 탐색하는 과정을 BFS로 구현할 수 있습니다. 건물 사이의 관계(간선)의 개수가 100,000이므로, 각 간선을 한번씩만 방문한다면 시간복잡도 내 풀이가 가능합니다. 위상 정렬 각 건물은 해당 건물이 지어지기 전에 특정 건물을 지어야 하는 선행조건이 있습니다. 이를 구현하기 위해 위상정렬을 활용할 수 있습니다. 위상정렬은 다음과 같이 해당 건물을 짓기 전에 선행되어야 하는 건물이 모두 지어졌는지(선행 건물의 개수가 0인지) 확인하는 과정을 통해 구현할 수 있습니다. ...
출처 백준 9202 Boggle 접근 Backtracking 특정 단어를 한 글자씩 찾아들어가면서 단어 사전에 존재하는지 확인하는 방식은 전형적인 DFS의 형태입니다. 주어진 단어의 개수가 w < 300,000 이지만 탐색해야 하는 전체 Boggle 보드의 크기가 4X4이고, 이러한 Boggle의 개수가 b < 30이기 때문에 DFS 자체는 많은 시간복잡도가 필요하지 않습니다. DFS 탐색 과정에서 다음 글자를 추가했을 때, 단어 사전에 포함된 단어를 만들 수 있는지를 빠르게 확인하여 불가능한 경우를 가지치기(pruning)한다면, 시간복잡도를 더욱 줄일 수 있습니다. 이러한 기법을 Backtracking이라고 합니다. ...
출처 2021 KAKAO BLIND RECRUITMENT 순위 검색 접근 와일드카드 검색 와일드카드(-) 없이 검색을 구현하는 것은 각 지원자의 속성에 코딩테스트 점수를 저장하면, 속성별로 검색이 가능하기 때문에 큰 어려움이 없습니다. 와일드카드가 없는 상황은 다음과 같이 트리 구조로 데이터를 저장할 수 있습니다. 트리 구조로 지원자 정보를 저장합니다. 리프 노드에는 리스트로 코딩테스트 점수를 저장합니다. 하지만, 문제에서 주어진 것처럼 쿼리 시 와일드카드가 나오면 모든 정보를 포함하도록 탐색을 해야 하기 때문에 이를 구현하기 위해 별도의 공간에 와일드카드 속성들을 저장해야 합니다. ...