그냥 게임개발자

에라토스테네스의 체 이분은 아주 대단하신 분이에요. 지구의 크기를 처음으로 계산하신 분이며 소수를 걸러내는 에라토스테네스의 체를 고안한 사람이기도 합니다. 그래서 우리는 에라토스테네스의 체를 배울 건데 소수가 아닌 값들에 대한 bool 배열을 만들어서 소수만을 걸러낼 수 있는 방법이 있습니다. 어우 저게 뭔소리냐. 우리가 아는 소수는 3.141592 뭐 이런거지만 소수 2를 나누었을 때 1과 2밖에 없죠? 3의 약수는요? 3도 똑같죠 1과 3 53의 약수는요? 똑같습니다 1과 53 이런 것들을 소수라고 합니다. #include #include using namespace std; const int MAX = 40; bool che[MAX + 1]; vector Eratosthenes(int max) { ..

모듈러 연산이란 a랑 b라는 숫자가 있을 때 a를 b로 나누었을 때 나머지만 필요할 때가 있습니다. 이러한 경우를 위해 우리는 % 즉 modular를 사용하게 되져 이것을 줄여서mod라고 불리는 연산자인데 a ≡ b mod n과 b ≡ c mod n은 a ≡ c mod n을 의미한다. ≡는 합동관계는 똑같다라는 소리입니다. a mod n 과 b mod n이 같다면 a ≡ b mod n이라는 소리죠. 그렇다면 아래와 같이 설명할 수 있겠죠. [ (a mod n) + (b mod n) ] mod n = (a+b) mod n과 같다라는 이야기입니다. [ (a mod n) - (b mod n) ] mod n = (a-b) mod n [ (a mod n) * (b mod n) ] mod n = (a*b) mod ..

이제 순열을 배웠기 때문에 조합을 알아봅시다. 순열은 "순서"가 있었죠? 조합은 "순서가 없습니다! 그저 n개에서 r개를 뽑는게 다입니다. 순서를 지킬 필요가 없죠. 순서를 지킨다면 nPr(Permutation) 즉 순열을 사용하면 되며, 그게 아니라면 nCr(Combination)을 사용하면됩니다. n개중에 순서없이 r을 뽑는다. 할 때, 예를 들어 3개중에 2개를 뽑는다라고 하면 n은 3이되며 r은 2가됩니다. 3! / 2!(3-2)!가 되며 3 * 2 * 1 / 2 * 1(1)이 됩니다. 그러면 분자에 2 * 1과 분모의 2 * 1은 나뉘어지어 사라지고 3 / 1 이되어 3개가 나온다라는 소리입니다. 쉽네요. 코드로 해볼까요? #include #include using namespace std; i..

요새 바빠가지구 포스팅을 잘 못했네요 호호.. 피곤에 쪄들었어요. 그래도 다시 마음잡고 열심히 공부해야죠! 사람이 12명씩 서로 2명씩 인사하면 몇 가지의 경우의 수가 나오나요? 바로 66가지의 경우의 수가 나옵니다. 경우의 수를 구할 때 보통 순열과 조합을 이용합니다. 먼저 순열부터 알아보시죠. 순열(Permutation)이란 순서가 정해진 임의의 집합을 다른 순서로 섞는 연산을 말합니다. 예를 들어 1, 2, 3이 있으면 1, 3, 2 2, 1, 3 뭐 이런식으로 말이죠. 그리고 n개의 집합 중에서 n개를 고르는 순열의 개수는 n!(팩토리얼)이라는 특징을 가지고 있습니다. 그러면 위에 예시처럼 1, 2, 3을 통해 만들 수 있는 3자리는 과연 몇 개 일까요? 123, 132, 213, 231, 312..

#include using namespace std; int number; void solve(int n) { int sum = 0, i = n; while (i > 0) { sum += i; i /= 2; } cout number; solve(number); return 0; } 이것을 보면 시간복잡도만 결론으로 이야기하면 O(logN)입니다. log는 알 거라고 생각하고 이야기 할게요. 만약 number가 32라고 칩시다. 그러면 solve에서 더해주는 게 32 + 16 + 8 + 4 + 2 + 1입니다. 그러면 총 5번을 하게 되죠? 그러면 이 log를 써봅시다. 밑이 2인 log2(32)는? 5죠 지수는 32인거구요. 그래서 log2(N)인데 상수또한 빼주어서 총 시간 복잡도는 logN이 되는겁니..

#include using namespace std; int arr[100]; int cnt; int SumAdd(int l, int r) { cnt++; if (l == r) return arr[l]; int mid = (l + r) / 2; int sum = SumAdd(l, mid) + SumAdd(mid + 1, r); return sum; } void main() { int number; cin >> number; for (int i = 0; i < number; ++i) { arr[i] = i + 1; } int sum = SumAdd(0, number - 1); cout

Array요소 수정할 때 크기를 정하지 않은 int arr[], 또는 배열의크기인 int arr[3], 배열의 포인터인 int* arr를 넘겨서 수정이 가능하다. #include using namespace std; int arr[3] = { 1, 2, 3 }; void Check1(int a[]) { a[2] = 100; } void Check2(int a[3]) { a[2] = 1000; } void Check3(int* a) { a[2] = 10000; } int main() { Check1(arr); cout

재귀함수란 3가지 특징을 가집니다. 재귀함수(Recursion)는 정의 단계에서 자신을 재참조하는 함수 전달되는 상태인 매개변수가 달라질 뿐 똑같은 일을 하는 함수 큰 문제를 작은 부분문제로 나누어서 풀 때 사용합니다. 예를 들어 팩토리얼(factorial)이 있습니다. 팩토리얼(factorial)은 1부터 해당 항까지 곱하는 함수입니다. 이를 재귀함수로 구현하면 다음과 같습니다. 근데 이거 고등학교인가 중학교인가 그 때 배웠던 것 같은데요. 코드로 활용해봅시다. #include using namespace std; // 재귀함수 int FactRec(int n) { if (n == 1 || n == 0) return 1; return n * fact_rec(n - 1); } int FactFor(int..