그냥 하는 노트와 메모장

BOJ 1128 피보나치 냅색 [분류 - 브루트포스, 수학] 어렵다ㅏㅏ [풀이] [표현식] 제켄도르프의 정리(https://en.wikipedia.org/wiki/Zeckendorf%27s_theorem)에 의하면 1보다 크거나 같은 자연수는 모든 계수는 0또는 1이고 인접한 피보나치 수에 대한 계수 ei × ei-1 = 0인 피보나치 수열로 표기할 수 있다. 또 이 수열은 유일(unique)하다. [전파] 가변량 ei를 i번째 피보나치 수에 대응되는 물건을 몇 개 쓸 수 있는지를 나타낸다고 정의하자. 주어진 무게 C에 대해 ei = 1인 가장 큰 피보나치 수 Fi에 대해 생각해보자. Fi 무게를 가지는 물건을 가방에 넣지 않으면 이 계수 ei는 이전 피보나치 Fi-1, Fi-2에 전파된다. 따라서 ei..

BOJ 1555 소수 만들기 [분류 : 다이나믹 프로그래밍, 수학] [풀이] [순열] N개의 수에 대해서 각 자리수에 어떤 수를 둬도 상관없으므로 최대 N!은 먹고 들어간다. (C++에서 next_permutation 사용) [연산 규칙] +,-,*,/ 모두 사칙연산에도 쓸 수 있지만 특히 -는 사칙연산뿐만 아니라 단항 연산에 사용될 수 있다. 즉, 값을 음수면 양수로, 양수면 음수로 바꿀 수 있다. 단순히 두 피연산자 e1과 e2(e1가 왼쪽에 있을 때)가 있을 때 나올 수 잇는 방법은 아래가 있다 e1 + e2 e1 - e2 e1 * e2 e1 / e2 하지만 음수를 붙여주면 경우의 수는 배로 늘어난다. -e1 - e2 -e1 + e2 -e1 * e2 -e1 / e2 보면 1.~4.에 음수를 붙힌 것..

* Algospot - 어린이날 (CHILDRENDAY, https://algospot.com/judge/problem/read/CHILDRENDAY) [ 분류 - BFS/ Mathematics ] 접근 방식이 다소 까다롭다. N명 중 M이 하나씩 더 받기 위해선 N%ans = M이며 이 나머지에 대해 사이클이 존재함을 알아야 한다. 또한 이를 증명하는 페르마의 소정리에 대해 알고 있어야 한다. * 접근 방법 1. 찾고자 하는 ans에 대해 N%ans = M이기 위해선 기저(시작 지점)은 숫자(한자리 수)부터 시작한다. 여기에 하나씩 이어붙이며 진행하는 BFS를 구성한다. 2. 나머지이기 때문에 후보를 [0, N]으로 줄일 순 없다. 적어도 하나 이상의 장남감을 줘야하기 때문에 [0, 2*N]가 후보가 ..

* BOJ 3964 - 팩토리얼과 거듭제곱 (https://www.acmicpc.net/problem/3964) [분류 - Mathematics/ GCD/ Sieve of eratosthenes ] 으음.. 생각해야할 부분이 굉장히 많은 문제다. 사실 어떻게 풀어야하겠다는 접근 자체는 다소 간단하다. 하지만 이 과정에서 발생할 수 있는 Overflow를 까다롭게 다뤄야 풀 수 있다. * 접근 방식 1. n!이 k^i에 나누어 떨어지기 위해서는 k^i = GCD(n!, k^i)이어야 한다. 2. 최대 공약수의 후보를 산출하기 위해서 k^i는 lg(k)의 시간이 걸리는 반면 n!은 lg(n!)이 걸린다. k^i가 lg(k)인 이유는 i제곱꼴은 k의 약수의 승수에 i를 곱하면 되기 때문. 따라서 후보를 추출하..

* BOJ 2981 - 검문 (https://www.acmicpc.net/problem/2981) [ 분류 - GCD ] 수학 개념이 필요한 문제다. 주어지는 N개의 수를 정렬한 수열의 결과를 a1, a2, ..., an 이라 하자. 임의의 정수 M으로 나눴을 때 수열의 나머지를 m라고 할 때, 수식을 아래처럼 나타낼 수 있다. 이에 대해 근접한 원소끼리 차이를 정리해보면, ... 서로 다른 두 원소 차이에 대해 "약수"로 M이 들어가 있는 것을 확인할 수 있다. 따라서 이 차이에 대해 최대공약수를 구하여 그것의 약수를 모두 출력하면 된다. - 코드 #include #include #include using namespace std; int gcd(int p, int q) { if (q == 0) ret..

[ 분류 - GCD ] 재밌는 문제다. 이 문제는 팩토리얼과의 GCD를 구하는 문제다. GCD에 요소가 될 수 있는 후보를 먼저 생각해보자. n!은 우선 냅두고.. k를 생각하자. n!은 너무 값이 클 수 있기 때문이다. 그렇다면 GCD 후보는 k의 약수로 요약할 수 있다. 또한 k를 소인수 분해하여 정리하면 아래와 같이 표현할 수 있다. 따라서 후보는 1부터 n을 곱했을 때, 그 값에서 소수 p1부터 px까지로 포함된 최대의 수로 나타낼 수 있다. 즉, 로 표현할 수 있다. 따라서 를 아래 수식처럼 표현할 수 있다. 접근법을 알았으니, 이제 n!에 대해 gx 값을 구하는 방법을 알아보자. 간단하게 나누기로 특정 소수의 px의 승수를 쉽게 알아낼 수 있다. 만약 px=2이라면 아래처럼 표현할 수 있다. ..

* 이분법(Bisection method) 1차원 데이터에 대해 [low, high] 구간을 지정하고, 원하는 데이터를 이분적으로 찾아가는 방식을 말한다. 여기서 low와 high는 사용자 정의 f()함수에 대해 f(low) > f(high)인 경우 low와 high를 swap 해주는 것이 더욱 깔끔하게 소스를 짤 수 있다. 즉, low = 10, high = 15, f(low) = 2, f(high) = 1 인 경우, 결과적으로 f(low)가 f(high)보다 크기 때문에 구간 [low, high]를 [15, 10]로 잡는 것이다. 방식은 iteration(순차 접근, for문)을 이용하는 방법과 while로 근사치를 추정해나가는 방식이 있다. 두 방식 중 안전한 방법은 iteration한 방법이다. ..

재밌는 문제라 포스팅하고자 한다. 연속된 숫자 1,5,10 이라고 한다면 심어야할 나무는 1보다 작은 위치 또는 10을 넘어가는 위치에 심을 순 없다. 따라서 1-5 간격과 5-10 간격이 다르기 때문에 각 구간에 나무를 심어야되는데, 그 간격을 정해보는 것에 포커싱을 맞춰보자. 1-5 간격은 4, 5-10 간격은 5다. 따라서 2도 3도 4,5 모두 간격으로 둘 수 없다. 따라서 1간격으로 나무를 심을 수 밖에 없다. 반면 1,5,11 이라고 가정해보자. 1-5 간격은 4, 5-11 간격은 6이 된다. 따라서 2간격만큼 나무를 심어줄 수 있다. 모든 구간에 대해 같은 간격으로 나눠져야하기 때문에 최대공약수를 이용해 구한다. 모든 간격에 대해 최대공약수를 구하면 그것을 나눈 값 - 1로 답을 구할 수 있..

우선 ax+b꼴을 예측하기 위해선 적어도 세 개의 숫자가 필요하다. 따라서 N이 1일 때와 N이 2일 때를 따로 처리해주자. 1. N = 1 무조건 답은 'A'다. 다음 숫자를 예측할 (a,b) 짝이 너무 많다. 2. N = 2 만약 두 숫자가 같다면 다음 숫자도 같은 숫자가 된다. 만약 다르다면 (a,b) 짝이 너무 많아서 'A'가 답이 된다. 3. N > 2 ax+b 꼴을 예측하기 위해 첫 세 숫자에 대해 a와 b를 fix 시킨다. 그 다음 그 fixed a,b를 가지고 모든 연속된 두 숫자에 대해 만족하는지 알아보기만 하면 된다. 수열에서 첫 숫자가 x라면 두 번째 수가 y, 다시금 두 번째 수가 x로서 feedback되므로 이 구조를 눈여겨 보자. ax+b가 모든 연속된 두 숫자에 대해 만족하기 ..

i번째 엘리베이터를 수식으로 나타낸다면 첫 위치를 그리고 몇칸씩 이동할 수 있는지를 로 표현한다면 i번째 엘리베이터가 갈 수 있는 곳은 아래를 만족하는 모든 층에 갈 수 있다. 하지만 최고층이 N이기 때문에 y는 최대 N까지 밖에 갈 수 없다. 따라서 엘리베이터에 따라 k의 최대값이 달라진다. 모든 엘리베이터를 수식으로 두고, 서로 다른 두 엘리베이터에 대해 i에서 j로 갈 수 있는지를 판단한다. 만약 i 엘베에서 j 엘베로 갈 수 있다면 간선을 연결해준다. 이 때 간선을 연결해줄 알고리즘이 매우 까다롭다. 두 수식에 대해서 만족하는 해와 최대층 N에 대해서 처리를 해줘야하기 때문이다. 우선 두 수식을 아래처럼 나타낸다. 이제 꼴로 나타냈으니 수식의 해가 정수해이기 위해선(정수해인 이유는 엘베에 대해 한..