The Way

자연수 n이 주어질 때, n을 서로 다른 피보나치 수의 합으로 나타내는 문제이다. 이 때 사용하는 피보나치 수의 갯수는 최소가 되어야 한다. 풀이는 생각보다 간단하다. n보다 같거나 작은 피보나치 수 중 가장 큰 피보나치 수를 사용하고, 이를 반복하면 된다. 가령 n=100이면 89를 사용하고, 남은 11에 대해서 8을 사용하고, 또 남은 3에 대해 3을 사용하면 된다. 답을 때려맞추기는 상당히 쉬운 문제이지만, 왜 그게 성립하는지 증명하기는 상당히 까다롭다. 과연 이 방법이 왜 최적의 해를 가져올까? 예시와 함께 증명을 해보자. 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ... 89~143까지의 숫자에 대해 생각을 해보자. i) 임의의 수에 대해, n보다 같거나 작은 피보나..

둘이서 베스킨라빈스 31 게임을 해본 사람이 있는가?다들 알다시피, 베스킨라빈스 31은 1부터 시작해 숫자를 최대 3개씩 부를 수 있고, 31을 먼저 외치는 사람이 지며, 먼저 시작한 사람에게 필승 전략이 존재한다. 왜 그런지 게임이 끝나는 상황부터 거꾸로 되돌아가보자.베스킨라빈스 31 게임은 30을 말하는 사람이 무조건 이기게 된다.30을 말하려면, 26을 외쳐야 한다. 26을 외치면, 다음사람이 어떤 수를 외치든 (4 - 외친수)만큼의 수를 말하면, 30을 만들 수 있기 때문이다. 즉, 26을 외치는 사람이 필승한다.반복적으로 26을 외치려면 22를 외쳐야 하고, 18, 14, 10, 6, 2...까지 간다. 따라서, 먼저 시작한 사람이 1, 2를 외치기만 하면 이미 게임은 끝난 상태인 것이다. 이러..

자기 전에 한 문제만 풀고 자려고 했는데, 이 문제 때문에 잠을 못잤다. 케이스가 상당히 극악인 문제이다. 문제는 아주 심플하다. 방정식 Ax + By + C = 0의 정수해의 개수 구하기이다. x와 y는 x1 ≤ x ≤ x2, y1 ≤ y ≤ y2를 만족해야 한다. 각 수의 범위는 -10^8 ~ 10^8이다. 일단 수의 범위가 상당히 크기 때문에 직접 다 해보는 알고리즘은 시간초과가 뜰 가능성이 농후하다. 케이스를 나누어가며 접근해보자. i) A와 B 둘 다 0인 경우 가장 쉬운 경우이다. C = 0이면 모든 해가 정답이고, C ≠ 0이면 해가 없다. ii) A와 B 둘 중 하나만 0인 경우 편의상 A = 0, B ≠ 0이라 해보자. 그럴 경우 방정식은 By + C = 0이 된다. C가 B로 나누어 떨..

요약: 몫은 양수 나눗셈 기준으로 부호만 맞추어주면 되고, (나누는 두 수의 부호가 같으면 몫이 양수, 다르면 몫이 음수) 나머지는 위에서 구한 몫으로, $a = bq + r$를 만족하는 값이 된다. -------------------------------------------------- 나눗셈의 몫과 나머지는 무엇일까? 일반적으로 통용되는 정의를 따져보면, 정수 a를 0이 아닌 정수 b로 나누었을때, $a = bq + r\;(0 \le r < |b|)$를 만족하는 수 q가 몫이고, r이 나머지이다. 이는 명백해보이지만, 음수가 들어가면 약간 애매해진다. 예를 들어서 -7을 3으로 나누면 몫과 나머지는 무엇일까? 정의에 따르면, $-7 = 3\times(-3) + 2\;(0 \le 2 < |3|)$이므..

소수 컬렉션을 풀어보았다. 백준 1456: 거의 소수범위가 10^14이다. 다행히 N제곱 꼴인 경우를 물어봤으므로, 10^7까지의 소수를 미리 구해놓고, 2제곱/3제곱/...을 잘 세어보면 된다.코드의 생명은 오버플로우 관리. 예를 들어서, 소수 p를 곱해가면서 b보다 커질 때까지 한다고 하면, b가 10^14라고 하면 10^7보다 약간 작은 소수에 대해서는 10^21 정도까지 가게 되는데, 이는 long long 범위도 넘어선다. 적당히 max값을 잡는 것이 이롭다. #include #define N 10000005 using namespace std; bool notprime[N]; int main() { for (int i = 2; i * i < N; ++i) { if (!notprime[i]) {..

추상대수학 시간에 배운 소수판정법인데, 아주 유용하여 기록해놓는다. Miller-Rabin 소수 판별법은 확률에 의존하는 소수판정법인데, 라그랑주 정리를 이용한다. 라그랑주 정리는 p가 소수이면, $f(x) \equiv 0 ( \text{mod}\:p)$는 최대 $deg(f(x))$개의 incongruent solution을 가진다는 정리이다. 라그랑주 정리에 따르면, $x^2 \equiv 1 ( \text{mod}\: p)$는 최대 두 개의 해를 가진다. 그런데 우리는 두 가지의 자명해를 알고있다. 바로 $\pm1$이다. (단, p > 2라 하자) 따라서, 만약 자명해가 아닌 $x^2 \equiv 1 ( \text{mod}\: p)$를 만족하는 해를 발견한다면, p는 소수가 아니라는 것을 알 수 있다...

운영체제 프로젝트 1은 스도쿠 푸는 프로그램을 작성하는 과제였다. 운영체제 수업에서 왜 스도쿠를 푸는지는 잘 모르겠으나.. 프로젝트를 하면서 많은 것을 배우게 되었으니 정리해본다. 스도쿠는 단 한 가지의 정답만 가져야 한다는 있다는 말도 있는데, 꼭 필요한 조건은 아니라고 생각한다. 물론 손으로 풀 때 답이 여러가지이면 굉장히 열받겠지만, 진정한 프로그램이면 어떠한 경우에서도 해답을 찾아낼 수 있어야 한다고 생각한다. https://www.acmicpc.net/problem/2580 참고로 백준 스도쿠 문제의 테스트 케이스 중에도 스도쿠 판을 채우는 방법이 여럿인 경우가 있다고 명시되어 있다. 답이 유일한 스도쿠를 찾는다면, http://staffhome.ecm.uwa.edu.au/~00013890/su..

DGIST 정보통신융합전공 대학원 면접을 봤다. 면접 방식은 학부 때 배운 것을 5분간 영어로 발표하고, 그 후 약간의 학과 지식 질문과 평범한 질문들을 대답하면 된다. 나는 네트워크 플로우 알고리즘을 발표했다. 뭐.. 컴퓨터 알고리즘 시간에 배운 것 중 흥미로운 부분도 많고, 생각보다 내용도 간단해서 발표하기 적합하다고 생각했다. 사실 영어로 5분이나 발표하는 것은 무슨 주제이던지 간에 상당히 힘들다. 토익 800점이 넘는데도 말하기는 참 버겁다. 내가 유독 영어 말하기를 못하는 것일지도 모르겠다. 아무쪼록 전날 스크립트를 열심히 외우고, 열심히 연습을 해서 그런지 다행히 영어 발표는 예상외로 순조롭게 진행하였다. 이어서 질문들이 들어왔다. 왜 이 주제를 골랐냐고 물으시길래, 간단하지만 유용하면서 아름..

꽤 쉬운 것 같길래 공부를 시작하기 전 가볍게 워밍업으로 풀어보았다. 백준 17173번: 배수들의 합N이 작아서 그냥 다 더해주면 된다. 생략. #include #include using namespace std; int main() { ios::sync_with_stdio(0); cin.tie(0); int n, m, t; cin >> n >> m; vector arr(n + 1, 0); while (m--) { cin >> t; for (int i = t; i > m; int ans = 0; while (n) { ans += n; n /= m; } cout n; cout = 'A' && c = 'a' && c > a >> b >> c; int p, q, r; p = a; q = 2 * b * c; r..

백준에는 가끔 경이로운 문제들이 있다.재능이 많은 사람들이 그 재능을 발산할 곳을 찾다 못해 백준 문제에 그 정수를 담아놓는 듯한 기분이다.구데기컵의 이 문제도 그러하다. 본격적인 채굴 문제... 문제의 기본적인 원리는 비트코인의 그것을 이용한다.비트코인에 조금이나마 관심이 있는 사람이라면 비트코인이 hash를 쓴다는 것 정도는 알고있을 것이다. 하지만 사실 hash를 직접 써 볼 기회가 그리 많지는 않다. 이 문제는 그런 의미에서 요즘 각광받는 블록체인 기술의 맛보기라도 볼 수 있다는 점에서도 아주 좋은 문제이다. 배경 지식을 아주 간단하게만 설명하면, 비트코인은 블록 전체를 sha-256이라는 해시 알고리즘을 통해 hash를 돌려서 hash값이 특정 숫자 이하가 나오도록 하며,블록에는 거래정보 / 직..