kittae 님의 블로그

브루트포스란?Brute: 무식한Force: 힘  쉽게 설명하자면 무식한 힘을 갖는 알고리즘을 뜻한다. 완전탐색으로 답을 찾는 알고리즘이며, 해당 알고리즘은 반복문과 조건문을 사용한다!어떻게 동작하는가?가장 유명한 문제로는 자물쇠 문제가 있다.모든 수를 탐색하여 자물쇠를 푸는 비효율적이면서도 100% 정확도를 자랑하는 브루트포스의 대표적인 문제이다.// 실제 비밀번호 (예: 1234)int actualPassword = 1234;// 4중 for문을 사용하여 모든 4자리 비밀번호를 탐색for (int i = 0; i  시간 복잡도는?단일 루프: O(n)중첩 루프: O(n^2)3중 루프 이상: O(n^k) (k는 중첩된 반복문의 수)이므로 경우의 수가 많아질 수록 비효율적이다.공간 복잡도는?별도의 메모리 사..

에라토스 테네스의 체란?여러 개의 수가 소수인지 아닌지 판별할 때 사용하는 대표적인 알고리즘이다.소수를 구하는 가장 기본적이고 이해하기 쉬운 방법 중 하나이다. 어떻게 동작하는가?리스트 생성: 2부터 원하는 최대 숫자 N까지의 리스트를 만듦첫 번째 소수 선택: 가장 작은 소수인 2부터 시작배수 제거: 선택한 소수의 배수를 리스트에서 제거하거나 표시다음 소수 찾기: 리스트에서 다음으로 남아있는 수를 선택하고, 이 수의 배수를 제거반복: 이 과정을 N의 제곱근까지 반복  시간 복잡도는??에라토스테네스의 체의 시간 복잡도는 놀랍게도 O(N log log N)이다.log log N은 매우 천천히 증가하는 함수로, N이 실용적인 범위 내에서는 거의 상수에 가깝다.즉, 해당 알고리즘은 사실상 선형 시간에 가까운 ..