Algorithm

Algorithm #2 에라토스테네스의 체(Sieve of Eratosthenes)

* 에라토스테네스의 체는 가장 대표적인 소수(Prime Number) 판별 알고리즘 이다. 이러한 소수들을 대량으로 빠르고 정확하게 구분하는 방법이다. # 소수 : 양의 약수 두개만 가지는 자연수. 음식 만들 때나, 큰 덩어리와 그것보다 작은 덩어리를 분리 할 때 사용하는 체와 같은 원리라고 공부하였는데, 크게 와닿을 것 같아, 정리하면서 한번더 생각하려한다. * 에라토스테네스의 체 방식 - '자연수'를 체로 걸러내 소수만 추출해 내는 것. 1. 본문 첫 이미지처럼 1부터 60까지 수가 있다고 가정 해보자. 2. 모든 수의 약수인 1은 당연히 체에 걸러지게 된다. 3. 2는 약수가 1과 자기 자신뿐인 소수에 속하게 되는데 이상황에서 2를 제외하고 2의 배수를 전부 지워준다. (2가 아닌 2의 배수는 1과..

Algorithm #1 DFS / BFS 개념 정리

DFS (깊이 우선 탐색, Depth-First Search) "루트노드(혹은 다른 임의의 노드)에서 다음 분기(branch)로 넘어가기 전에, 해당 분기(branch)를 모두 탐색하는 방법. 탐색 후에는 다시 원점으로 돌아가 다른 분기를 탐색" - 트리의 순회와 같이 그래프의 모든 정점들을 특정한 순서에 따라 방문하는 알고리즘들을 그래프의 탐색(search) 알고리즘이라고 한며, 깊이 우선 탐색(DFS; depth-first search)은 그래프의 모든 정점을 발견하는 가장 단순하고 고전적인 방법. - 미로찾기를 예로 들면 최대한 한 반향으로 갈수 잇을때까지 나가다가 막다른 길이 나오면 가장 최근의 갈림길로 돌아가서 다시 한 방향으로 나가는 것을 반복하는 방식. - 특징 1) 자기 자신을 호출하는 순..