Computer Science/Algorithm
[Algorithm] 빅오 표기법과 시간 복잡도의 개념 및 예제
알고리즘에서 중요한 속성 1. 정확성 : 주어진 입력을 모두 처리하며 올바르게 출력해야 한다. 2. 효율성 : 문제를 효율적으로 해결해야 한다. 두 가지 변수로 측정 - 시간 복잡도 : 알고리즘이 얼마나 빠르게 결과를 출력하는지 측정, 입력 크기 n에 대한 시간 함수 T(n)으로 표현 - 공간 복잡도 : 원하는 결과를 얻기 위해 알고리즘이 얼마나 메모리를 사용하는지 측정, 입력 크기 n에 대한 메모리 사용 함수 S(n)으로 표현 빅오 표기법 (big-O) - 점근적 분석의 한 방법 - 수학적 정의 - cg(n)은 모든 n >= n0에 대해 f(n)의 상한이다. - 최고차항의 차수로 표현하고 계수와 낮은 차수의 항은 무시한다. (예시) n^2 + n = O(n^2) 시간 복잡도 알고리즘에 주로 나오는 시간..
[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% 정답률을 가지며 만들기 쉽다는 장점이 있지만, 실행 시간이 오래 걸린다는 단점이 있습니다. 구조에 따른 브루트 포스의 종류 브루트 포스는 모든 자료를 탐색해야하기 때문에 어떤 구조더라도 전체를 탐색할 수 있는 방법을 가진다. 선형 구조를 전체 탐색하는 방법은 순차 ..