본문 바로가기

Algorithm/기본지식4

[Algorithm] 트라이(Trie) 트라이(Trie)" data-ke-type="html">HTML 삽입미리보기할 수 없는 소스Trie는 탐색트리의 일종으로 특정 문자열이 포함되어있는지 등을 찾는데 효과적인 자료구조다. 예를 들어 영어로 된 여러 단어가 N개 주어지고, 여러개의 접두어가 M개 주어진다.이때, M개의 접두어로 시작하는 단어가 몇 개 있는지 구하는 경우를 생각해보자. 단순하게 반복문으로 구하게 되면 (M개의 접두어)*(N개의 단어)*(접두어와 단어를 비교) 의 반복을 하게 된다.M, N, 접두어 단어의 길이가 작으면 상관없지만 조금이라도 커지면 시간복잡도가 크게 늘어나게 된다. 이러한 반복을 줄이는데 효과적인 자료구조가 Trie다. 이제 [HILL, HIGH, HELL, HELLO, HELLT] 라는 단어를 Trie 구조로 .. 2024. 5. 24.

[Algorithm/기본지식] 유클리드 호제법 HTML 삽입 미리보기할 수 없는 소스 https://terms.naver.com/entry.naver?docId=2073670&cid=47324&categoryId=47324 두 정수 a, b의 최대 공약수를 G(a,b)라고 표현한다. 이때 정수 a, b, q, r (b는 0이 아니다)에 대하여 a = bq + r 이면 G(a, b) = G(b, r)이 성립한다. HTML 삽입 미리보기할 수 없는 소스 G(a, b) = g일 때, 최대공약수의 성질에 의해 a = a′g, b = b′g이고 G(a′, b′) = 1이다. (최대공약수가 g이기 때문에 a′, b′는 서로소 이다.) a = bq + r 로부터 r = a - bq = g(a′ - b′q) 이고, g는 r의 약수이다. G(b, r) = g임을 보.. 2024. 1. 2.

[Algorithm/기본지식] 소수 판별하기 HTML 삽입 미리보기할 수 없는 소스 정수 N이 주어졌을 때, 소수인지 아닌지 판별하는 방법은 2~N의 제곱근 사이의 수들로 정수 N이 나뉘어지는지 확인하면 된다. $$a=\sqrt{N}$$ $$N=b_1\times b_2\times ...b_n\ \left(N의\ 소인수\ 분해\right)$$ 임의의 정수 N의 제곱근을 a라고 한다. 정수 N이 소인수 분해된다고 가정 했을 때, 가장 큰 소인수가 a보다 크거나 같다면 정수 N의 남은 소인수는 무조건 a보다 같거나 작을 수 밖에 없다. a가 N의 제곱근이라서 정수 N은 (a보다 큰 소인수 * a보다 작은 소인수)로 나타나기 때문이다. 이를 활용하면 1. N이 소수가 아닐 때, a보다 큰 소인수가 없는 경우 2. N이 소수가 아닐 때, a보다 크.. 2024. 1. 2.

[Algorithm/기본지식] 소수 판별하기 정수 N이 소수인지 아닌지 판별하는 방법 정수 N이 주어졌을 때, 소수인지 아닌지 판별하는 방법은 2~N의 제곱근 사이의 수들로 정수 N이 나뉘어지는지 확인하면 된다.$$a=\sqrt{N}$$$$N=b_{1}\times b_{2}\times b_{3}\times\cdots\times b_{n} $$ (N의 소인수분해)임의의 정수 N의 제곱근을 a라고 한다. 정수 N이 소인수 분해된다고 가정 했을 때, 가장 큰 소인수가 a보다 크거나 같다면 정수 N의 남은 소인수는 무조건 a보다 같거나 작을 수 밖에 없다.a가 N의 제곱근이라서 정수 N은 (a보다 큰 소인수 * a보다 작은 소인수)로 나타나기 때문이다.이를 활용하면1. N이 소수가 아닐 때, a보다 큰 소인수가 없는 경우2. N이 소수가 아닐 때.. 2023. 2. 10.

이전 1 다음

티스토리툴바