알고리즘
[Algorithm] 소수를 찾는 방법, 에라토스테네스의 체
에라토스테네스의 체 란? 소수(Prime number)를 찾는 알고리즘 대량의 소수를 빠르고 정확하게 구할 수 있는 방법 에라토스테네스의 체 원리 소수를 판별할 범위의 배열을 할당하고, 값을 지워나가는 방법 1. 배열을 생성하여 초기화 2. 2부터 시작하여, 특정 수의 배수를 모두 지운다. (자기 자신은 지우지 않는다) 3. 2부터 남아있는 모든 수는 소수이다. 에라토스테네스의 체 구현 (C++) void Eratos(int n){ /* 인덱스 0과 1은 사용하지 않음을 고려하여 배열을 할당해야 한다 */ bool num[1000001]; /* 배열 초기화 : 모두 소수라고 가정한 true 값을 준다 */ for (int i = 2; i
[Algorithm] 브루트 포스와 BFS, DFS
브루트 포스(Brute Force) 란? Brute(무식한) + Force(힘) 브루트 포스는 완전 탐색 알고리즘으로, 가능한 모든 경우의 수를 탐색하고 조건에 충족되는 결과만을 가져온다. 무식하게 모두 탐색하기 때문에 100%의 확률로 정답을 출력합니다. 알고리즘은 기본적으로 해가 존재할 것으로 예상되는 범위를 탐색하기 때문에, 브루트 포스 알고리즘을 설계할 때, '해가 하나 이상 존재한다'는 가정을 세우고 모든 범위를 탐색합니다. 100% 정답률을 가지며 만들기 쉽다는 장점이 있지만, 실행 시간이 오래 걸린다는 단점이 있습니다. 구조에 따른 브루트 포스의 종류 브루트 포스는 모든 자료를 탐색해야하기 때문에 어떤 구조더라도 전체를 탐색할 수 있는 방법을 가진다. 선형 구조를 전체 탐색하는 방법은 순차 ..