소수 판별 알고리즘 관련해서 정리를 하려고합니다. 기본적인 소수 판별 알고리즘 def get_prime_nums(n): for i in range(2,x): if x % i == 0: return False return True 에라토스테네스의 체 소수 판별 알고리즘 def get_prime_nums(n): prime = [True] * n prime[0], prime[1] = False, False for i in range(2, n+1): if prime[i] == True: j = 2 while i * j

Trie 알고리즘이란 문자열을 검색을 할때 트리 형식으로 각 단어를 하위 노드에 저장하여 시간 복잡도가 (Mlog(n)) 인 알고리즘 사용하는 이유는 문자열의 탐색을 하고자할 때 시간복잡도를 보면 알 수 있습니다. 단순하게 하나씩 비교하면서 탐색을 하는것보다 훨씬 효율적입니다. 단, 빠르게 탐색이 가능하다는 장점이 있지만 각 노드에서 자식들에 대한 포인터들을 배열로 모두 저장하고 있다는 점에서 저장 공간의 크기가 크다는 단점도 있습니다. 검색어 자동완성, 사전에서 찾기 그리고 문자열 검사 같은 부분에서 사용할 수 있다고 위키에 보면 나와있습니다. 이 알고리즘을 이용한 문제는 대표적으로 프로그래머스의 가사 검색 문제입니다. class Node: def __init__(self, key, data=None)..

이분 탐색 문제를 풀어보다가 최장증가수열 알고리즘으로 풀수있는 알고리즘이 있어 이론을 정리를 하려고 합니다. 최장증가부분수열(LIS,Longest increasing subsequence) 이란 주어진 원소 n개인 배열에서 오름차순으로 정렬된 가장 긴 부분수열을 찾는 알고리즘입니다. 즉 각 원소가 이전 원소보다 크다는 조건을 만족하고 그 길이가 최대안 부분수열을 최장 증가부분수열입니다. 예를 들어 아래와 같은 수열이 있다고 가정을 해봅시다 [3, 5, 7, 9, 2, 1, 4, 8] 여기서 증가하는 부분수열을 만든다면 했을때 졍렬이 아닌 요소를 제외하는 방법으로 한다면 아래와 같이 여러가지가 나올수 있습니다. [3,5,6,7] [1,4,8] [2,4,8] ... 등이 있지만 제일 긴 수열은 3,5,6,8..