Level 2. 주식가격 가장 간단한 방식이지만 효율은 좋지 않다. #include #include using namespace std; vector solution(vector prices) { size_t n = prices.size(); vector answer(n, 0); for (int i = 0; i < n; ++i) for (int j = i; (j < n - 1) && (prices[i]

이득우의 게임 수학 사원수(Quarternion)란 4개의 독립된 체계로 구성된 4차원의 수집합으로서, 복소평면을 4차원 공간으로 확장한 개념이다. 복소수와 동일하게 허수를 사용하는 수의 집합으로서, 하나의 실수부와 세 개의 허수부로 구성된다. 사원수를 구성하는 3개의 허수부 i, j, k는 모두 복소수의 허수 단위 i와 같은 성질을 가진다. 세 허수 중 두 허수의 곱은 나머지 하나에 대응되는데, 이들은 회전의 순환 순서 x - y - z - x와 유사하게 i - j - k - i 순서로 대응된다. ij = k이고 kk = -1이므로, ijk = -1이 성립한다. 세 허수의 곱은 -1이 된다. 사원수의 덧셈도 복소수와 유사하게 다음의 성질들을 만족한다. 결합법칙 교환법칙 항등원과 역원이 존재 사원수의 곱..

Level 2. [3차] 압축 문제가 길어서 뭔가 번거로운 문제인 줄 알았는데 이해하고 나니 그렇게 어려운 문제는 아니었다. 문제에 나와 있는대로 차근차근 구현하니 잘 풀 수 있었다. #include #include #include #include using namespace std; vector solution(string msg) { vector answer; int cur = 1; unordered_map dict; deque Msg(msg.begin(), msg.end()); for (char c = 'A'; c

이득우의 게임 수학 오일러 공식에 필요한 자연 지수 함수, sin 함수, cos 함수에 대응하는 매클로린 급수 식은 다음과 같다. sin 함수는 홀수항 부분이 0이 되고, cos 함수는 짝수항 부분이 0이 되다보니, sin과 cos 함수를 더하면 서로에게 부족한 부분이 채워진다. 자연 지수 함수의 매클로린 급수와 유사한 형태가 되었지만, 부호에서 차이가 있다. 부호를 일치시키려면 크기가 1이고 제곱하면 -1이 되는 허수 단위 i를 사용해야 한다. cosx + sinx 와 자연 지수 함수의 매클로린 급수 식의 차이는 짝수 항에 허수 단위 i가 붙어 있다는 것 뿐이다. sinx가 짝수 항을 담당하므로, sin 함수에 허수 단위 i를 곱하면 자연 지수 함수의 매클로린 급수와 같아진다. 이 식에 x 대신 각 θ..

Level 2. k진수에서 소수 개수 구하기 진수 변환, 소수 확인, 파싱이 복합적으로 구성된 문제였다. 에라토스테네스의 체 방법으로 소수를 찾았더니, 배열의 크기가 100만을 넘어가게 되어 메모리 초과가 발생했다. 매번 같은 계산을 하지 않기 위해 최댓값을 찾아 static으로 선언한 배열에 1번 계산해준 후 사용했다. // 이 풀이는 메모리 초과가 발생한다. #include #include #include #include #include #include using namespace std; string to_base(int n, int num) { deque deq; const char numbers[] = {'0', '1', '2', '3', '4', '5', '6', '7', '8', '9'}; ..

이득우의 게임 수학 멱급수가 수렴하기 위한 조건을 알아봤으니, 이제 무한번 미분 가능한 함수를 멱급수 형태로 바꾸는 방법에 대해 알아본다. 이러한 멱급수를 매클로린 급수 혹은 테일러 급수(Taylor series)라고 한다. 수렴하는 멱급수에서 공비 r을 x로 바꿔 f(x)로 정의한다. 어떤 함수가 무한번 미분 가능하다면, 멱급수의 도함수는 다음과 같이 전개될 것이다. x에 0을 대입하면, 멱급수를 구성하는 각 항의 계수 a.n과 일정한 규칙을 가지는 상수만 남는다. 위 식들은 계승(Factorial)을 사용해 다음과 같이 간단히 표기할 수 있다. 멱급수의 n번째 계수 a.n은 다음과 같이 나타낼 수 있다. 멱급수 전개는 다음과 같이 n번 미분한 도함수에 0을 대입한 형태로 일반화할 수 있고, 이를 매클..