분류 전체보기8 백준 5446번 : 용량 부족 - 트라이, Java https://www.acmicpc.net/problem/5446 5446번: 용량 부족 팀포2 덕후 연수는 팀포2를 다운받던 도중 하드 용량이 부족하다는 것을 알았다. 이때는 침착하게 팀포2를 하지 말거나 하드를 새로 사면 되지만 불가능했고, 결국 하드에서 쓸모없는 파일을 지 www.acmicpc.net 1.문제설명 주어지는 문자열을 바탕으로 트라이를 만들고 각 분기점에 대해 파일들을 한번에 지울 수 있는지 없는지 판별하여 모든 파일을 지우는 최소 횟수를 구해야 하는 문제이다. 우선 주어지는 N1개의 단어를 바탕으로 트라이를 구현한 후 지울 수 없는 단어 N2개에 대해서 이미 구현된 트라이에 해당 단어는 지울 수 없음을 마킹한다. 마킹이 완료되면 전체 트라이를 순회하면서 해당 분기를 지울 수 있으면 1.. 2023. 1. 2. 백준 3080번 : 아름다운 이름 - 트라이 , Java https://www.acmicpc.net/problem/3080 3080번: 아름다운 이름 상근 선생님은 학생들에게 번호를 붙여주려고 한다. 상근이는 미술 선생님이기 때문에, 이름의 순서도 아름다워야 한다고 생각한다. 따라서, 다음과 같은 규칙을 지켜서 번호를 정하려고 한다. www.acmicpc.net 1.문제설명 입력받는 이름들로 트라이 구조를 만들고 분기점과 문자열이 끝나는 점을 바탕으로 순열 계산을 하면 학생들을 배치할 수 있는 경우의 수를 구해낼 수 있다. 2.문제풀이코드 C++ 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 4.. 2022. 12. 31. 백준 4358번 : 생태학 - hash, Java https://www.acmicpc.net/problem/4358 4358번: 생태학 프로그램은 여러 줄로 이루어져 있으며, 한 줄에 하나의 나무 종 이름이 주어진다. 어떤 종 이름도 30글자를 넘지 않으며, 입력에는 최대 10,000개의 종이 주어지고 최대 1,000,000그루의 나무가 주어 www.acmicpc.net 트라이를 구현해서 해결할 수 있고, 그냥 단순히 hash 자료 구조를 활용하여 문제를 해결할 수 있다. //package org.example; import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.*; public class Main { public void solution() throws E.. 2022. 12. 31. 백준 9202번 : Boggle - 트라이 Java https://www.acmicpc.net/problem/9202 9202번: Boggle 각각의 Boggle에 대해, 얻을 수 있는 최대 점수, 가장 긴 단어, 찾은 단어의 개수를 출력한다. 한 Boggle에서 같은 단어를 여러 번 찾은 경우에는 한 번만 찾은 것으로 센다. 가장 긴 단어가 여러 개 www.acmicpc.net 1. 문제 설명 300,000개의 word를 트라이로 만든 후 주어지는 4x4 그리드에 대해서 DFS를 수행하며 해당 문자열이 트라이 내에 존재하는지 확인하여 문제를 해결할 수 있다. 2. 문제풀이코드 Java //package org.example; import java.io.BufferedReader; import java.io.InputStreamReader; import .. 2022. 12. 31. 이전 1 2 다음