문제 링크 1. 문제 풀이 전화번호 목록의 일관성 여부를 판단하는 문제로 일관성이 없는 목록은 한 번호가 다른 번호의 접두어가 되는 경우다. 접두어를 통해 판단한다는 점에서 트라이 자료구조를 활용했는데 삽입 과정에서 다음 노드로 이동할 때 이미 삽입한 번호의 마지막 노드를 방문하면 새로 삽입하는 번호가 해당 번호의 접두어가 되므로 삽입에 실...

문제 링크 1. 문제 풀이 집합 $S$ 에 포함된 $N$ 개의 문자열이 주어지고 이후 $M$ 개의 검사해야 하는 문자열이 주어진다. 검사해야 하는 각 문자열은 해당 문자열이 집합 $S$ 에 포함된 문자열 중 하나의 접두사가 되는지 카운팅을 해줘야 한다. 간단하게는 집합 $S$ 에 포함되는 $N$ 개의 문자열에 대해 각 문자열의 모든 접두사...

문제 링크 1. 아이디어 콰트로치즈피자는 서로 다른 네 종류의 치즈 토핑이 들어가야 하며 치즈 토핑은 이름이 Cheese로 끝난다. 서로 다른 네 종류 이상의 치즈 토핑이 있는지 판단해야 하므로 집합 자료구조를 활용해서 이름이 Cheese로 끝나는 토핑들을 담은 후 집합의 크기가 4 이상인지 구하면 해결할 수 있다. 2. 코드 1...

문제 링크 1. 문제 풀이 단어 사전에 들어있는 단어들이 주어진 후 여러 개의 Boggle 보드들이 주어진다. 각 보드에서 얻을 수 있는 최대 점수, 가장 긴 단어, 찾은 단어의 개수를 구해야 하는데 트라이 자료구조를 활용하면 해결할 수 있다. 먼저 단어 사전의 단어들로 트라이를 생성한다. 이때 Boggle에서 단어 사전에 등재되었는지 여...

문제 링크 1. 문제 풀이 자동 입력 기능을 구현할 때 전체 단어에 대한 평균 입력 횟수를 구해야 하는 문제로 트라이 자료구조를 활용하면 해결할 수 있다. 단어의 끝 여부와 자식 노드의 수를 저장하는 트라이에 각 단어들을 삽입한 후 DFS를 돌면 되는데 버튼을 눌러야 하는 순간은 현재 노드가 루트일 때나 현재 노드가 단어의 끝일 때, 또는 ...

문제 링크 1. 문제 풀이 각 유저의 별칭을 찾는 문제로 별칭은 이전에 가입한 닉네임의 접두사가 아니면서 가장 짧아야하며 가능한 별칭이 없으면 같은 닉네임으로 가입한 사람의 수를 기반으로 지어야 한다. 트라이 자료구조를 활용해 해당 닉네임에 대해 검색 후 삽입으로 처리하면 되며 검색에서는 다음 노드가 존재하지 않는 순간 지금까지 방문한 노드...

문제 링크 1. 문제 풀이 주어진 단어들로 욱제어 단어를 모두 만들 수 있으면 욱제어 단어를 순서대로 출력하는 문제로 욱제어는 서로 접두어가 되는 관계가 없는 단어들이어야 한다. 트라이 자료구조를 활용하면 해결할 수 있는데 트라이에 해당 DFS로 해당 길이의 단어가 들어갈 수 있는 곳을 탐색하면 되며 한번이라도 새로운 노드를 만들었으면 접두...

문제 링크 1. 문제 풀이 로봇 개미로 개미굴을 탐사한 결과를 출력하는 문제로 탐사는 문자열의 사전순으로 DFS 스타일로 탐사를 해야한다. 주어진 개미굴을 트라이 자료구조를 활용해서 저장하면 해결할 수 있는데 각 노드가 문자 하나가 아닌 단어를 저장하는 방식으로 하면 된다. 이를 위해 트리맵 배열을 활용해서 배열 인덱스에 노드 번호, 트리맵...

1. 후기 전날 2026 KSA Automata Winter Contest에 이어서 월간 향유회 2026. 01-02. Open Contest에 참여했다. 역시나 Solved.ac 뱃지나 배경을 받을 수 있지 않을까 했고 Java를 쓰기로 마음먹고 참여했다. 이전 월간 향유회 문제들을 보니 플래티넘부터 시작하는 대회도 있어서 A번 문제가 너무 어...

문제 링크 1. 문제 풀이 BaekJoon 2631번 - 줄세우기 문제에서 이제 옮길 때 가장 앞이나 뒤로만 옮길 수 있는 문제로 이전처럼 단순한 LIS로는 해결할 수 없다. 중간에 배치하는 것이 불가능하므로 LIS를 구하되 번호가 1씩 증가하는 LIS를 구하면 해당 LIS에 포함되지 않은 아이들을 적절하게 맨 앞이나 맨 뒤로 이동시켜서 최...