The Way

요약: 몫은 양수 나눗셈 기준으로 부호만 맞추어주면 되고, (나누는 두 수의 부호가 같으면 몫이 양수, 다르면 몫이 음수) 나머지는 위에서 구한 몫으로, $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값이 특정 숫자 이하가 나오도록 하며,블록에는 거래정보 / 직..

인기 문제에 있는 꿀문제만 조져보았다. 백준 15637번: Lotto구데기컵스럽게 이상한 문제인데 쉬운 편.https://dhlottery.co.kr/gameResult.do?method=byWin링크 아래쪽에서 친절하게 ~회부터 ~회까지 당첨번호를 엑셀로 다운받을 수 있다.코드는 굳이 첨부하지 않는다. 백준 17202번: 핸드폰 번호 궁합어릴 적에 한번쯤은 해보았을 듯한 이름 궁합과 비슷하다.틀리기가 더 힘든 문제. #include using namespace std; int main() { char num1[9], num2[9]; int arr[16]; cin >> num1 >> num2; for (int i = 0; i < 8; ++i) { arr[i * 2] = num1[i] - '0'; arr[..

라면의 연속 26회차 오늘의 라면: 오뚜기 김치라면 구성: 네모면 + 분말스프 용량: 120g 조리법: 물 550ml, 4분 영양 성분: 열량505kcal- 나트륨1,650mg83% 탄수화물79g24% 당류4g4% 지방16g30% 트랜스지방0g- 포화지방8g53% 콜레스테롤0mg0% 단백질11g20% 한줄평:보통 스프가 하나만 있는 라면, 쇠고기면이나 안성탕면과 같은 라면은 무언가 저렴한 보급형의 느낌이 강하게 들곤 한다. 하지만 그 중 가장 큰 반례를 뽑자면, 바로 이 김치라면을 뽑고 싶다. 때는 친구과 인당 소주 한 병을 5분컷하던 작년 10월. 안주로 김치라면을 딱 끓여먹었는데, 세상에나 라면국물에서 느껴지는 김치의 향이 그렇게 반가울 수가 없었다. 마치 김치찌개를 먹는 기분.. 물론 술기운에 약간..

C에는 온갖 입출력 함수들이 많다. 당장 출력만 해도 putchar, putc, fputc, puts, fputs, fwrite, printf, fprintf의 8개 정도 함수를 손에 꼽을 수 있을 것 같다. 함수들의 출력속도에는 상당한 차이가 있다. 그것도 꽤 많은 차이가 난다. https://www.acmicpc.net/blog/view/57 백준 블로그인데, 여기에 함수들의 출력 속도 차이가 적혀있다. fwrite가 가장 빠르다고 나온다. 저 함수들 중 몇 개가 비어있기 때문에, 마저 채우는 느낌에서 속도를 측정해보았다. 백준에서는 숫자를 1부터 1000만까지 출력하였지만, 약간 특수한 상황이므로 이번 테스트에서는 더 본질적인 메모리에 있는 문자열을 그대로 출력하기를 해 보았다. 구체적인 테스트 방..