생각하는 아이들

보호되어 있는 글입니다.

보호되어 있는 글입니다.

보호되어 있는 글입니다.

Meet in the middle Meet in the middle 은 브루트포스 알고리즘을 사용해야 하지만 경우의 수가 브루트포스 알고리즘을 사용하기에 조금 클 때 사용 된다. 즉 브루트포스 알고리즘을 사용하되 이를 분할 해서 연산의 수를 최소화 하는 것이다. 예를 들면 N크기 배열 원소의 모든 조합을 고려해야 하는 문제가 있다고 하자. 이때 N이 20이라면 2^20(약 100만)개의 연산을 하면 된다. 하지만 만약 N이 40이라면 2^40 개의 연산을 수행하므로 초당 연산 수 1억번 이내에서 해결이 어렵다. 이때 MITM 알고리즘을 사용하게 되는데~ MITM 은 분할 정복과 비슷한 형태를 취하지만 분할정복은 작은 문제 해결을 통해 커다란 하나의 문제를 해결하는 반면~ MITM은 작은 문제 해결 + 알..

컴퓨터 과학에서 접미사 배열(Suffix Array)란 어떤 문자열의 접미사를 사전식 순서대로 나열한 배열을 말한다. S = S[0]S[1]...S[n-1] 이라는 문자열이 있다고 하자. 이때 S[i,j] 는 i번째 문자부터 j번째 문자 까지 S의 부분 문자열이라고 하자. 문자열 S에 대한 접미사 배열 A는 S의 접미사들을 사전식 순서로 정렬 했을 때 접미사의 시작 위치를 저장한 정수 배열이다. 즉 A[i] 에 저장 된 내용은 사전순으로 i 번째인 S의 접미사의 시작 위치이다. 다시 말하면 문자열 S의 길이를 n이라고 할 때 , 0

LCA(Lowest Common Ancestor) 란? LCA 란 최소 공통 조상을 찾는 알고리즘 - 두 정점 u,v 에서 가장 가까운 공통조상을 찾는 과정을 말한다. LCA(Lowest Common Ancestor) 구현 방법 위의 그래프에서 LCA((4,8)=1 이 됩니다. 가장 단순한 방법은 한번에 하나씩 자신의 조상을 찾아 올라가는 방법입니다. 4의 조상은 2,8의 조상은 7,2의 조상은 1,7의 조상은 3,1의 조상은 루트이므로 대기,3의 조상은 1 에서 순차적으로 하나씩 찾아가다가 누군가가 먼저 지나간 자리에 도착하면 그곳이 공통조상이 됩니다. 하지만 이 알고리즘은 최대 O(N) 의 시간이 걸립니다. https://www.acmicpc.net/problem/11438 11438번: LCA 2 ..

트라이의 정의를 위키백과의 내용을 인용하면 다음과 같습니다. 트라이(trie)는 컴퓨터 과학에서 탐색트리의 일종이다. 노드의 모든 자손은 노드에 연관된 문자열의 공통 접두사를 공유한다. 트라이 알고리즘이란? 문자열 변수를 비교하는데는 최악의 경우 문자열의 길이에 비례하는 시간이 걸릴 수 있습니다. N개의 원소를 갖는 이진검색 트리에서 원하는 원소를 찾으려면 O(lgN)번의 비교만으로 찾을 수 있습니다. 이러한 이진 검색 트리에서 착안을 하여 고안된 문자열 특화 자료구조가 바로 트라이(trie) 로 집합 내에서 원소를 찾는 작업을 O(M) 시간만에 할 수 있습니다. 그렇다면 어떻게 가능한지 다음을 살펴 보시죠~ 출처:위키백과 그림은 문자열집합 S={"A","to","tea","ted","ten","inn"..

보호되어 있는 글입니다.

보호되어 있는 글입니다.

보호되어 있는 글입니다.