devbelly

문제 www.acmicpc.net/problem/17365 알고리즘 트라이 + DP 풀이 문래빗어 사전에 적혀있는 단어수와 그 단어들이 주어졌을 때, 해석하려는 문자열의 가능한 경우의 수를 묻고 있습니다. 해석하려는 문자열을 $str$이라 하겠습니다. (아래에서 언급하는 $str [a:b]$ 는 $str$ a번째 인덱스부터 b번째 인덱스까지의 부분 문자열입니다) $cache [i]$= i+1번째 문자열까지 해석했을 때, 가능한 경우의 수 $cache [i+1]$은 다음 상태들의 합입니다. $cache [i]$에서 가능한 개수 * 단어들 중 $str [i+1]$와 매칭 가능한 개수 , cache [i-1] * 단어들 중 $str [i:i+1]$와 매칭 가능한 개수... (매칭이 가능하다는 것은 문래빗어 정..

문제 https://www.acmicpc.net/problem/9202 알고리즘 트라이 풀이 격자판에서 주어진 문자열을 조건에 따라 찾아야 하는 문제입니다. 최대 점수, 찾은 단어의 개수, 가장 긴 단어를 구하기를 원하고 있습니다. 단어의 개수를 찾는 과정에서 최대 점수와 가장 긴 단어 또한 해결 가능하므로 단어를 찾는 것에 집중합시다. 격자판 위에서 단어를 탐색해야 하므로 DFS를 통해 일차적인 접근이 가능합니다. DFS연산량만 어림짐작해보면 (주어지는 보글의 수) X (4x4 격자판에서 DFS시작 가능한 위치의 개수) X (DFS의 깊이에 해당하는 단어의 길이) X (각 알파벳마다 가능한 선택지의 수) 이고, 이는 대략 3천만에 가까운 숫자입니다. 즉 단어를 선형 시간 안에 찾지 않게 되면 시간 초과..

문제 https://www.acmicpc.net/problem/5446 알고리즘 트라이 풀이 제거해야 하는 문자열과 남겨야 하는 문자열이 주어지고, "문자열"+"*"을 통해 "문자열"로 시작하는 모든 문자열을 제거할 수 있다고 합니다. 접두사를 이용한다는 점에서 트라이를 착안해봅시다. 각 노드마다 $yes$,$no$,$finish$ 를 만들어서 해당 노드를 제거해야하는지(yes), 제거해서는 안되는지(no), 제거해야 하는 문자가 끝나는지(finish)를 구분합니다. 만약 노드의 $yes$와 $no$가 둘 다 True 면 해당 노드를 제거해서는 안됩니다. (노드를 제거한다는 것은 와일드 카드를 사용해서 이후 노드를 보지 않겠다는 의미입니다) 이때 유의해야할 것은, 제거해서는 안 되는 노드에 $finish..

문제 https://www.acmicpc.net/problem/3080 알고리즘 Trie 풀이 관찰이 필요한 문제입니다. 예제들을 그림으로 그려 예제 입출력을 이해하도록 합시다. 이를 통해 문제의 답은 (트라이의 자식 수 + 해당 트라이에서 끝나는 단어)의 팩토리얼들의 곱이라는 점을 알아낼 수 있습니다. 이렇게 문제를 풀게 되면 메모리 초과가 발생하게 됩니다. Trie? 선형시간에 원하는 문자열을 찾아낼 수 있는 자료구조입니다. 이를 가능케 하는 것은 각각의 트라이마다 모든 문자들을 가리키는 포인터를 저장하고 있기 때문입니다. 이 때문에 많은 메모리를 사용한다는 단점이 있는 자료구조입니다. 따라서, 필요하지 않은 문자열을 제거해야합니다. Suffix Array & LCP에서 봤듯이, 주어진 문자열을 정렬..