그냥 하는 노트와 메모장

우선 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가 모든 연속된 두 숫자에 대해 만족하기 ..

BOJ 2624 문제를 먼저 푸는 것을 추천합니다. ============================================================ 이 문제 역시 동전 바꿔주기 문제와 완전 동일하다. 단, 소수가 추가됐긴 했지만, 이는 에라스토테네스의 체로 구할 수 있다. 각 사탕에 대해서 hashing을 해줘야하며(몇 번째 사탕인지 등), 이는 map또는 vector, array 해싱으로 처리할 수 있다. 기본적인 아이디어는 캔디 종류 하나씩 처리를 해나가며 처리한다. 현재 처리해야 하는 캔디가 k번째 캔디라면 이전에 처리된 0부터 500000까지(50*10000) 가능한 가격에 대해 k번째 캔디의 가격을 더한다. 더할 때도, 같은 캔디가 여러개 있을 수 있으므로, k번째 캔디의 수가 cn..

A. Garden 바닥에 물을 흘리지 않는 -> 약수인, 최대값을 찾으면 된다. #include int main() { int n, k,d,ans=1; scanf("%d%d", &n, &k); while (n--) { scanf("%d", &d); if (!(k%d)) ans = ans > d ? ans : d; } printf("%d", k / ans); return 0; } B. Browser left, right가 존재하는 구간이 전체에 대해서 3가지 밖에 없다. 왼쪽에 몰린 경우, 오른쪽에 몰린 경우, 가운데에 있는 경우. 이 세가지 경우를 고려하여 범위 및 Greedy 접근을 하여 해결한다. #include int abs_v(int a) { return a < 0 ? -a : a; } int m..

A. Hawk eyes 모든 경우에 대해 switch~case 문으로 값을 변경해주는 것으로 구성하면 된다. 마지막엔 순회하여 위치값을 출력해준다. #include #include int main() { char S[201]; int cup[4] = { 1,0,0,2 },i; scanf("%s", S); for (i = 0; S[i]; i++) { switch (S[i]) { case 'A': std::swap(cup[0], cup[1]); break; case 'B': std::swap(cup[0], cup[2]); break; case 'C': std::swap(cup[0], cup[3]); break; case 'D': std::swap(cup[1], cup[2]); break; case 'E': ..

* Modular 모듈러 연산은 덧셈, 뺄셈, 곱셈에 대해 닫혀있다. 즉, (a+b)%m = (a%m+b%m)%m과 동일하다. 나눗셈에 대해선 닫혀있지 않으므로 유의한다. ※ 페르마의 소정리를 참고.

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

A에서 B로 갈 수 있는 모든 경로의 차의 수 최대값은 최대 유량으로 충분히 가능하다. 하지만 또 하나가 있는게 이 중에서도 한 경로만 사용했을 때, 최대값을 구해서 앞서 구한 모든 경로의 차의 최대값과 한 경로의 차의 수 최대값의 비율을 계산하라고 한다. 단순 최대유량 문제만 내기엔 부족했나보다. 편의상 A에서 B로 가는 모든 경로의 차의 수 최대값을 X라고 하고, 한 경로의 차의 수 최대값을 Y라고하면 구하고자 하는 값은 Y/X가 된다. X는 단순 최대 유량으로 구해서 계산하며 Y는 backtracking으로 정의하여 계산한다. Y를 구할 때, 기저 사례는 B를 만날 때까지고, 재귀를 돌며 방문했던 정점은 다시 방문하지 않도록 한다. 재귀의 반환값은 현재 정점에서 방문 가능한 정점 중에서 차를 최대한..

완전 그래프에 관한 문제다. 크기가 K인 그래프 내의 clique(클릭) 중에서 구성된 정점의 번호가 제일 작은 것을 찾으려고 한다. 입력 데이터의 규모가 작으니 하나하나 접근해나가며 완전 그래프를 만들 수 있는지 없는지 판단하는 백트래킹 재귀 함수를 만들었다. 재귀 호출하기 전에, for문으로 번호가 작은 친구부터 탐색하도록 한다. 마찬가지로 재귀 내에서도 번호가 작은 친구를 찾도록 유도하여 구성된 정점의 번호가 작은 클릭을 찾을 수 있다. 재귀 함수의 기저 사례는 현재 구성된 완전 그래프의 크기 p와 찾아야 하는 완전 그래프의 크기 k와 같으면 true를 반환..

* syntaxHighlighter 3.0.83- Language views : http://alexgorbatchev.com/SyntaxHighlighter/manual/brushes/- Usage : // source code- Changing skin : http://alexgorbatchev.com/SyntaxHighlighter/manual/themes/

다소 까다로운 문제다. 문제 내용을 읽으면 우선 트리를 떠올리게 되는데, 문제에 맞는 트리의 속성을 적자면 아래와 같다. 1. 이진 트리다. 2. 자식이 하나만 있는 노드는 없으며, 자식이 있다면 무조건 2개의 자식을 갖는다. 하지만, 트리는 아니다. 이는 훼이크고, 그냥 단순 그래프이나, 노드에 순서성에 대해 트리형태처럼 보일 뿐이다. 정확히는 DAG(Directed acyclic graph)를 나타낸다. 따라서 나는 세 단계를 거쳐 AC를 받게 됐다. 1. MLE 2. TLE 3. AC (만약 단순 솔루션만 보고 싶다면 기본 아이디어 이후, 3.으로 바로 넘어가길 바란다.) * 기본 아이디어 그래프를 배열로 구현하고, 문자열에 대한 것은 string, map을 사용하여 배열에 대한 위치값(또는 포인터..

- Base case기저 사례라고도 한다.Recursive call에서 Terminal condition을 지정하는 경우를 말한다. - Referential transparency/ Referential transparent function참조적 투명성/ 참조적 투명 함수Argument로 넘긴 입력에 대해 항상 같은 값만을 반환할 때 참조적 투명성이 있다고 한다. 함수가 이런 특징을 띄면 참조적 투명함수라고 한다. - Mathematical exclusion(수학적 배제)수학적 증명을 통한 탐색 공간을 배제하는 방법 - Branch & bound(가지치기, 경험적 배제라고도 함)경험적으로 더 이상 해를 구할 수 없는 조건을 만났을 때, 탐색을 그만 두는 것.탐색을 처음 시작할 때는 조건을 정할 수 없으나..