SY DevLog

9202번: Boggle 각각의 Boggle에 대해, 얻을 수 있는 최대 점수, 가장 긴 단어, 찾은 단어의 개수를 출력한다. 한 Boggle에서 같은 단어를 여러 번 찾은 경우에는 한 번만 찾은 것으로 센다. 가장 긴 단어가 여러 개 www.acmicpc.net DFS와 트라이 알고리즘을 통해 문제를 해결하였다. 게임 사전에 등재된 단어들을 트라이에 넣는다. 각 보드마다 DFS방식으로 접근하면서 여태까지 지나온 알파벳들로 이루어진 단어가 트라이에 포함되어 있는지를 확인한다. 문제에서 같은 단어를 여러 번 찾은 경우는 하나로 간주한다고 했으므로 중복을 피하기 위해 찾은 단어를 HashSet에 넣어주었다. 기존의 트라이의 contains() 메서드는 true 혹은 false를 반환하였다.특정 단어에 트라이..

14725번: 개미굴 첫 번째 줄은 로봇 개미가 각 층을 따라 내려오면서 알게 된 먹이의 정보 개수 N개가 주어진다. (1 ≤ N ≤ 1000) 두 번째 줄부터 N+1 번째 줄까지, 각 줄의 시작은 로봇 개미 한마리가 보내준 먹이 www.acmicpc.net 트라이를 사용하여 문제를 해결하였다. 보통은 트라이노드의 Key값에 char형을 넣지만, 이 문제에서는 두 번째 예제의 경우 문자열이 하나의 노드에 들어가야 하므로 char형이 아닌 String형으로 변경하였다. 또한, 문제에서 알파벳 순서대로 출력해야 하므로 자식 노드들 중 알파벳 순서상 앞에 위치한 노드부터 탐색해야 한다. 따라서 TreeMap을 사용하여서 자동으로 알파벳 순으로 정렬되도록 했다. Map childNodes = new TreeMa..

5670번: 휴대폰 자판 휴대폰에서 길이가 P인 영단어를 입력하려면 버튼을 P번 눌러야 한다. 그러나 시스템프로그래밍 연구실에 근무하는 승혁연구원은 사전을 사용해 이 입력을 더 빨리 할 수 있는 자판 모듈을 개발 www.acmicpc.net 이번 문제를 트라이를 이용하여 풀 수 있는 문제이다. Trie 의 insert, contain, delete 함수외에 검색횟수를 반환하는 별도의 getCount() 함수를 만들어서 문제를 해결하였다. 트라이 알고리즘에 대해 잘 모른다면 아래 링크를 참조하길 바란다. lotuslee.tistory.com/53?category=965898 트라이(Trie) - 1. 트라이 개념 및 노드 특징 트라이(Trie) 문자열들의 집합을 N진 트리 형태로 표현한 자료구조로, 문자열..

www.acmicpc.net/problem/4358 4358번: 생태학 프로그램은 여러 줄로 이루어져 있으며, 한 줄에 하나의 나무 종 이름이 주어진다. 어떤 종 이름도 30글자를 넘지 않으며, 입력에는 최대 10,000개의 종이 주어지고 최대 1,000,000그루의 나무가 주어 www.acmicpc.net HashMap을 사용하여서 쉽게 풀었다. 맵의 Key에는 종 이름을, Value에는 종의 개수를 새어서 증가시켜준다. 소스코드 :

5052번: 전화번호 목록 첫째 줄에 테스트 케이스의 개수 t가 주어진다. (1 ≤ t ≤ 50) 각 테스트 케이스의 첫째 줄에는 전화번호의 수 n이 주어진다. (1 ≤ n ≤ 10000) 다음 n개의 줄에는 목록에 포함되어 있는 전화번호가 www.acmicpc.net 트라이(Trie)를 이용하여 문제를 해결하였다. 트라이(Trie) 자료구조에 대한 기본적인 이해가 선행되어야 한다. 트라이(Trie) - 1. 트라이 개념 및 노드 특징 트라이(Trie) 문자열들의 집합을 N진 트리 형태로 표현한 자료구조로, 문자열 검색에 주로 사용된다. 하나의 노드는 하나의 문자를 나타낸다. 단, 루트노드는 아무런 문자도 의미하지 않는다. 트 lotuslee.tistory.com 전화번호에 일관성이 없는 경우는 트라이에..

트라이(Trie) - 1. 트라이 개념 및 노드 특징 트라이(Trie) 문자열들의 집합을 N진 트리 형태로 표현한 자료구조로, 문자열 검색에 주로 사용된다. 하나의 노드는 하나의 문자를 나타낸다. 단, 루트노드는 아무런 문자도 의미하지 않는다. 트 lotuslee.tistory.com 위의 글에서는 트라이 개념, 트라이 노드 특징(Map, isLastChar)에 대해 설명했었다. 이번에는 트라이(Trie)의 동작 1. 단어 삽입 2. 단어 포함 여부 3. 단어 삭제 에 대해서 자세하게 다룰 것이다. 트라이 위의 트라이 그림에서 포함되어 있는 단어는 "bird", "big", "beer", "girl", "god", "grow" 여섯 가지이다. 트라이노드(TrieNode)의 클래스는 아래와 같이 구현할 수..

트라이(Trie) 문자열들의 집합을 N진 트리 형태로 표현한 자료구조로, 문자열 검색에 주로 사용된다. 하나의 노드는 하나의 문자를 나타낸다. 단, 루트노드는 아무런 문자도 의미하지 않는다. 시간복잡도 : O(m) (m은 문자열 길이) 트라이 예 트라이(Trie) 특징 트라이(Trie) 노드 특징 1. 트라이의 각 노드는 문자와 자식 노드를 맵 형태로 가지고 있다. -> Map 예를 들어, 루트노드의 경우, 자식노드가 2개이므로 Key가 'b' 이고, Value에 왼쪽 자식 노드를 가지고 있으며, Key가 'g' 이고, Value에는 오른쪽 자식 노드를 가지고 있다. 루트의 왼쪽 자식 노드도 마찬가지이다. 이 노드는 그림에서 보면 'b'를 가지고 있는 것처럼 보이지만, 사실은 특정 문자를 가지고 있는 것..