반응형 전체 썸네일형 리스트형 [BOJ 7812] 중앙 트리 [문제] www.acmicpc.net/problem/7812 7812번: 중앙 트리 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫 줄에는 트리의 정점의 수 n이 주어진다. (1 ≤ n ≤ 10,000) 각 정점은 0번부터 n-1번까지 번호가 붙여져 있다. 다음 n-1개 줄 www.acmicpc.net [난이도] - Platinum III (20.12.14 기준) [필요 개념] - Tree DP - DFS [풀이] 설명에서 나오는 S(u)는 'u를 루트로 하는 서브트리'를 뜻한다. 한 점에 대해서 다른 모든 점까지의 거리의 합을 구한다면 단순 Tree DP를 이용하여 노드의 개수만큼 탐색하면 된다. 하지만, 이 문제는 모든 정점에 대해서 고려를 해야하기 때문에 $O(n^2)$이고.. Atcoder Beginner Contest 185 (ABC 185) 풀이 [문제 링크] atcoder.jp/contests/abc185 AtCoder Beginner Contest 185 - AtCoder AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online. atcoder.jp [풀이] A. ABC Preparation 각 점수별로 문제 수가 나와있고, 하나의 문제 set을 만들기 위해서는 점수별로 하나씩 문제가 필요하다. 따라서 네 정수 중 최솟값을 출력하면 된다. #include using namespace std; int main(void) { ios::sync_with_stdio(false); cin.tie(n.. [BOJ 9202] Boggle [문제] www.acmicpc.net/problem/9202 9202번: Boggle 각각의 Boggle에 대해, 얻을 수 있는 최대 점수, 가장 긴 단어, 찾은 단어의 개수를 출력한다. 한 Boggle에서 같은 단어를 여러 번 찾은 경우에는 한 번만 찾은 것으로 센다. 가장 긴 단어가 여러 개 www.acmicpc.net [난이도] - Platinum IV (solved.ac 20.12.13 기준) [필요 개념] - 트라이 (Trie) - 완전탐색 (Brute-force) - 그래프 탐색 [풀이] 사전에 있는 단어를 모두 트라이에 넣어두고, 그래프 탐색을 통해서 Boggle에서 만들어질 수 있는 모든 문자열들을 다 트라이에서 찾아본다. 트라이는 처음에 한번만 만들어도 충분하다는 점을 유의하자. [소스 .. [BOJ 5670] 휴대폰 자판 [문제] www.acmicpc.net/problem/5670 5670번: 휴대폰 자판 휴대폰에서 길이가 P인 영단어를 입력하려면 버튼을 P번 눌러야 한다. 그러나 시스템프로그래밍 연구실에 근무하는 승혁연구원은 사전을 사용해 이 입력을 더 빨리 할 수 있는 자판 모듈을 개발 www.acmicpc.net [난이도] - Platinum III (solved.ac 20.12.13 기준) [필요 개념] - 트라이 (Trie) [풀이] 자동 입력이 되는 순간은 현재 노드에서 끝나는 문자열이 없으면서, 자식 노드가 하나밖에 없는 경우이다. 따라서 트라이를 생성할 때 자식의 수를 저장해두고, 문자열을 탐색할 때 자식의 수가 둘 이상이거나, 현재 노드에서 끝나는 다른 문자열이 있고 자식의 수가 1이면 버튼을 눌러줘야 하.. [자료구조] 트라이(Trie) 자료구조 [목차] 1. 트라이(Trie) 자료구조란? 2. 트라이(Trie)의 작동 원리 3. 트라이(Trie) 자료구조의 장/단점 4. 트라이(Trie) 자료구조의 구현 5. 트라이(Trie) 예제 문제 1. 트라이(Trie) 자료구조란? 트라이(Trie)는 문자열의 집합을 표현하는 '트리 자료구조'이다. 원하는 원소를 찾기 위해 자주 이용되는 이진 검색 트리 (STL set, map) 등에서는 원소를 찾는데 O(logN)의 시간이 걸리게 된다. 하지만, 문자열의 경우 두 문자열을 비교하기 위해서는 문자열의 길이만큼의 시간이 걸리기 때문에 원하는 문자열을 찾기 위해서는 O(MlogN)의 시간이 걸리게 된다. 따라서 여러 번 이 작업을 수행한다면 시간이 오래 걸릴 것이다. 이 단점을 해결하기 위한 문자열 특화 자.. [BOJ 2809] 아스키 거리 [문제] www.acmicpc.net/problem/2809 2809번: 아스키 거리 첫째 줄에 거리의 길이 N이 주어진다. 다음 줄에는 거리에 원래 적혀져있는 알파벳이 주어진다. 셋째 줄에는 묶음 타일의 종류의 개수 M이 주어진다. 다음 M개 줄에는 각 묶음 타일에 적혀져있는 www.acmicpc.net [난이도] - Platinum 2 (20.12.11 solved.ac 기준) [필요 개념] - 아호코라식 (Aho-corasick) [풀이] 아호코라식 문자열 판별 알고리즘의 응용문제이다. 타일과 일치하는 부분을 제외한 문자의 개수를 구하는 문제인데, 단순하게 아스키 거리의 각 위치(index) 별로 끝에 일치하는 타일들을 모두 고려한다면 시간 초과가 발생할 것 같다....? (정확하게는 모르겠다) 따.. [BOJ 10256] 돌연변이 [문제] www.acmicpc.net/problem/10256 10256번: 돌연변이 인간의 DNA 구조는 A, C, G, T로 이루어진 하나의 긴 문자열로 표현할 수 있다. 이때, 몇 몇 질병은 DNA 구조를 나타낸 문자열의 어떤 연속된 부분 문자열과 관련이 있다는 것이 밝혀져 있다. 만일 DNA www.acmicpc.net [난이도] - Platinum 3 (solved.ac 20.12.11 기준) [필요 개념] - 아호코라식 (Aho-corasick) [풀이] 마커(marker)의 돌연변이의 경우의 수는 최대 $m^2$이다. m이 100이하이므로 모든 돌연변이를 직접 다 만들어도 무리가 없다. 그리고, 만들어진 돌연변이들을 트라이에 넣어두고, DNA문자열을 탐색한다. 이때, 모든 돌연변이들의 길이가.. [BOJ 9250] 문자열 집합 판별 [문제] www.acmicpc.net/problem/9250 9250번: 문자열 집합 판별 집합 S는 크기가 N이고, 원소가 문자열인 집합이다. Q개의 문자열이 주어졌을 때, 각 문자열의 부분 문자열이 집합 S에 있는지 판별하는 프로그램을 작성하시오. 문자열의 여러 부분 문자열 중 하 www.acmicpc.net [난이도] - Platinum 2 (solved.ac 20.12.11 기준) [필요 개념] - 아호코라식 (Aho-corasick) [풀이] 아호코라식 알고리즘의 가장 기본 문제이다. 집합에 주어지는 모든 단어들을 트라이에 넣고, 판별해야하는 문자열별로 체크하면 된다. #include using namespace std; struct Trie { Trie* ch[26]; Trie* fail; b.. 이전 1 ··· 11 12 13 14 15 16 17 ··· 23 다음
