문제 링크 1. 문제 풀이 주어진 히스토그램에서 가장 큰 직사각형의 넓이를 구하는 문제로 단조 스택을 활용해서 해결할 수 있다. 아래는 예제 그림의 히스토그램이다. 히스토그램의 첫 번째 막대부터 순서대로 탐색을 진행한다. 먼저 첫 번째 막대의 경우 기준이 될 다른 막대가 없다. 두 번째 막대의 경우 첫 번째 막대보다 ...

문제 링크 1. 문제 풀이 주어진 조건을 만족하는 이름을 출력하면 되는 문제로 건물 이름이 gwan으로 끝나야하며 맨 앞 글자와 맨 뒤 글자가 같아야해서 n으로 시작해야 한다. 중간에 k와 u를 적절히 넣어주면 된다. 2. 코드 1. 풀이 [Java] public class Main { public static void ...

문제 링크 1. 문제 풀이 시작 번호가 주어졌을 때 만들 수 있는 서로 다른 비밀번호의 개수를 구하는 문제로 DFS를 활용해서 해결할 수도 있지만 버튼이 3 by 3 크기라는 점에서 관찰을 통해서도 해결할 수 있다. 먼저 대칭성이 있으므로 코너 쪽에서 시작하는 경우, 코너 사이의 변에서 시작하는 경우, 중앙에서 시작하는 경우만 구하면 되며 ...

문제 링크 1. 문제 풀이 BaekJoon 14725번 - 개미굴 문제와 동일한 아이디어로 해결할 수 있다. 역슬래시 파싱에만 주의하면 된다. 2. 코드 1. 풀이 [Java] import java.io.*; import java.util.*; public class Main { static StringBuilder ...

문제 링크 1. 문제 풀이 지워야 하는 파일들과 지우면 안 되는 파일들이 주어졌을 때 최소한의 삭제 명령으로 지워야 하는 파일들을 모두 지워야 하는 문제다. 트라이 자료구조를 활용하면 해결할 수 있는데 먼저 지워야 하는 파일들로 트라이를 만들어준다. 이때 생성 과정에서 방문한 모든 각 노드에 매번 +1을 해줘서 각 노드가 자신까지를 접두어로...

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

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

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

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

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