둠선생 연구실

소수는 약수가 1과 자기 자신밖에 없는 수이다. 따라서 소수 판정은 2부터 n-1까지의 숫자로 나눠봄으로써 알 수 있다. 하지만 연산량을 조금 줄이기 위해서 한 가지 수학적인 사실을 이용할 수 있다. - 소수는 2부터 $\sqrt{n}$까지의 정수로 나눠보면 알 수있다. 간단하게 증명하자면, 만약 n이 1을 제외한 $\sqrt{n}$ 이하의 정수로 나누어 떨어지지 않는다고 가정하면, $\sqrt{n}$보다 큰 정수 a로 나누어 떨어진다. 하지만 a로 나누어떨어진다면 n/a로도 나누어 떨어진다는 뜻이고, ($a * \frac{n}{a} = n$ 이므로) 하지만 n/a는 $\sqrt{n}$보다 작은 정수이므로 가정에 모순이 발생한다. 따라서 1을 제외한 $\sqrt{n}$이하의 정수로 나누어떨어지지 않는다면..

만약 정렬이 되어있지 않은 1~n까지의 숫자가 들어있는 (중복없이) 크기 n의 배열이 있다고 가정했을 때, 우리가 원하는 임의의 숫자 k의 위치를 찾기 위해선 앞쪽부터 하나씩 탐색해야한다. 만약 최악의 경우는 k가 맨 뒤에 있을 경우인데, 그 경우 우리는 크기의 n의 배열에서 n번 (모두) 확인해야한다. n의 크기가 크지 않거나, 한번만 수행하면 될 경우에는 나쁘지않은 방법일 수도 있다. 하지만 반대로, n의 크기가 매우 크고, k, m, n, l 등 여러 개의 숫자의 위치를 찾아야 한다면, 배열을 정렬한 뒤에 O(logn)의 시간 내에 탐색이 가능하다. 여기에선 배열을 정렬하는 방법 자체에는 집중하지 않는다. 방식은 간단하다 크기 10000인 배열에서 내가 찾고 싶은 수가 100번 째에 있다고 가정하면..

#include #include using namespace std; int main() { map dic; dic["a"] = 1; dic["b"] = 2; dic["c"] = 3; dic["d"] = 4; int a = dic["e"]; map::iterator it; for (it= dic.begin(); it != dic.end(); it++) { cout first

확률에서 이런 경우가 많이 있다. 예를들어, 4명의 후보자가 있다. 그 중에 원하는 사람을 우리 팀에 뽑을 수 있다. 4명을 다 고를 수도 있고, 아무도 안 고를 수 있다면, 우리 팀에 후보자를 데려올 수 있는 경우의 수는 몇 가지인가? 풀이는 간단하다. 각 한명씩 뽑을 경우, 뽑지 않을 경우 두 가지 선택지만 존재하므로, 곱의 법칙을 이용해 2 * 2 * 2 * 2 총 16가지의 경우의 수가 존재한다. 이런식으로 각각의 선택지를 포함하고, 포함하지 않고 모두 탐색해야한다면 어떤식으로 풀어야할까? 아이디어는 간단하다. 0 ~ 15 (선택지가 4개 일 경우) 까지의 숫자를 이진수로 변환하여 각각의 경우에 대응하는 것이다. 모두 다 뽑지 않는 경우는 0 (0000)이 될 것이고, 모두 다 선택하는 경우는 1..

C++의 자료형(타입)을 확인하거나 크기가 궁금할 때는 어떻게 확인할 수 있는 지 알아보자. 결론부터 말하자면, 먼저 자료형은 헤더의 typeid()를 이용한다. 타입의 크기는 sizeof() 함수를 이용하면 구할 수 있다. 아래의 예제 코드를 보자 #include #include using namespace std; int main() { int a = 5; bool b = false; short int c = 15; double d = 25.12; cout

C++이 지원하는 cout과 cin 함수가 C의 scanf, printf 보다 느리다는 사실은 많은 사람들이 알고 있다. 알고리즘 문제를 풀면서 입출력 시간이 크게 중요하지 않은 경우에는 C++의 입출력 함수가 쉽기 때문에 주로 사용을 했는 데, 많은 사람들이 속도를 위해서 C의 입출력 함수를 사용한다. 과연 속도가 얼마나 차이가 날지 궁금했다. 실험은 알고리즘 문제 풀이 과정에서 입출력 부분만 바꿔서 실험해보았다. 일반적으로 입출력의 병목현상이 심할 경우에 혹은, 입출력 함수의 비중이 큰 경우 일수록 크게 차이가 날 것이다. 다만 이 몇 가지 실험이 모든 일반적인 경우를 포함하지는 못하므로 참고용으로만 보면 좋을 것 같다. SWexpert 아카데미에 있는 문제들로 테스트를 해보았다. 다른 코드는 동일하..

이전에 포스팅한 재귀 알고리즘을 이용한 부분 집합 생성 알고리즘과 유사한 방식이다. 참고: 재귀함수를 이용한 부분 집합 생성 알고리즘 재귀 함수를 이용한 부분 집합 생성 알고리즘 #define _CRT_SECURE_NO_WARNINGS #include #include using namespace std; vector subset; int n = 4; void search(int k) { if (k == n + 1) { // 부분 집합 출력 for (int i = 0; i < subset.size(); i++) cout.. doomed-lab.tistory.com 아래는 n = 7 , r = 4 라고 가정하고 7C4의 경우를 모두 출력하는 코드이다. #include #include using namespa..

먼저 아래와 같은 test 코드를 보자. #include using namespace std; void func(int** map, int* ptr) { map[0][1] = 100; int b = 99; ptr = &b; } int main() { int a = 100; int* ptr = &a; int** map = new int* [2]; map[0] = new int[2]; map[1] = new int[2]; map[0][0] = 0; map[0][1] = 0; map[1][0] = 0; map[1][1] = 0; func(map, ptr); cout