예민한 블로그

윌슨의 이론은 무엇인가?" p 가 소수일 때, (p-1) ! ≡ -1 (mod p) 이다."가 물음에 대한 답이다. (p-1)! ≡ -1 (mod p)가 무슨 뜻일까?(p-1)! 과 -1을 p로 나누었을 때의 나머지가 서로 같다는 뜻이다.(p-1)! = pq + r  (0 -1 = ps + r(0 두 식에서의 r이 같다는 표현이 저 위의 식과 동치이다. 정말 그럴까? 증명해보자. 먼저 정의를 알아보고 가자.소수란 무엇인가?소수란, 양의 약수가 1과 자기 자신 뿐인 수를 말한다. 2, 3, 5, 7, 11, 13, ... 이런 수들이 소수다. 우선, p가 가장 작은 소수인 2일 때 윌슨의 이론에 부합하는지 확인해보자. 1 ≡ -1 (mod 2) 이니까, 참이다. (1과 -1 모두 2로 나눈 나머지가 1이니..

정수론 강의 2주차 쯤에 배운 내용이다.교수님께서 이 증명에 대한 힌트를 주셨는데, 그 힌트를 써먹을 방법을 몰라서 질문드렸지만 그 질문에 답하는 것은 형평성에 어긋난다는 답변을 받았다.그래서 내 나름대로 증명해봤다.중간중간 생략해 마땅한 과정이 있지만 과정을 생략하면 이해가 안되는 독자가 있을 수 있으니 최대한 모든 과정을 담아서 증명했다. 정수론 입문자로서 형편 없는 증명이라고 생각한다. 미진한 부분에 대한 자비 없는 수정 요청을 기다리고 있다. Proposition: if $a,n$ are positive integers and $\sqrt[n]{a}$ is rational, then $\sqrt[n]{a}$ is an integer. Given that $\sqrt[n]{a}$ is rationa..

우선순위 큐란 O(log n)의 시간복잡도로 특정 조건을 만족하는 최적값을 출력하고, O(log n)의 시간복잡도로 원소를 입력하는 자료구조를 의미한다. 우선순위 큐는 완전 이진 트리를 사용한다. 완전 이진 트리는 배열을 통해 표현할 수 있다. 부모 노드가 i번째 배열일 때, 왼쪽 자식 노드는 (i * 2)번째 배열, 오른쪽 자식 노드는 (i * 2 + 1)번째 배열이고, 자식 노드가 j번째 배열일 때, 부모 노드는 (j / 2)번째 배열이다. 이와 같은 간단하고 직관적인 연산으로 완전 이진 트리를 배열로 표현할 수 있는 것이다. 데이터의 입력은 완전 이진 트리의 그 다음 빈 위치에 입력하고, 데이터의 출력은 완전 이진 트리의 root 위치의 값을 제거한 뒤, 완전 이진 트리의 끝 값을 root 위치로 ..

문제 링크https://www.acmicpc.net/problem/3711서론t개의 테스트 케이스가 제공된다. (t에 대한 조건 없음)각 테스트 케이스에서는 G개의 정수를 입력받는다. (1 ≤ G ≤ 300)입력받는 G개의 정수 A1, A2, ... Ag-1, Ag에 대한 조건은 0 ≤ A{i}  G개의 정수들을 k로 나눈 나머지가 모두 다르게 만드는, 가장 작은 k를 찾는 문제였다.먼저 떠올린 풀이는 for(int k = 1;is_equal_exist(k); k++)을 따르는 풀이다. 이러한 풀이를 적용한 예시를 들어보면 다음과 같다.G = 3, A = {2, 5, 7}일 경우 정답이 어떻게 될까?k = 1일 때 나머지는 0, 0, 0이므로 성립하지 않는다.k = 2일 때 나머지는 0, 1, 1이므로 ..

문제 링크https://www.acmicpc.net/problem/2056문제수행해야 할 작업 N개 (3 ≤ N ≤ 10000)가 있다. 각각의 작업마다 걸리는 시간(1 ≤ 시간 ≤ 100)이 정수로 주어진다.몇몇 작업들 사이에는 선행 관계라는 게 있어서, 어떤 작업을 수행하기 위해 반드시 먼저 완료되어야 할 작업들이 있다. 이 작업들은 번호가 아주 예쁘게 매겨져 있어서, K번 작업에 대해 선행 관계에 있는(즉, K번 작업을 시작하기 전에 반드시 먼저 완료되어야 하는) 작업들의 번호는 모두 1 이상 (K-1) 이하이다. 작업들 중에는, 그것에 대해 선행 관계에 있는 작업이 하나도 없는 작업이 반드시 하나 이상 존재한다. (1번 작업이 항상 그러하다)모든 작업을 완료하기 위해 필요한 최소 시간을 구하여라...

문제 링크https://www.acmicpc.net/problem/31813문제양의 정수 x의 모든 자릿수가 같은 숫자로 이루어져 있다면, 그런 x를 RUN 수라고 한다. 예를 들어, 4, 111, 888, 888은 RUN 수이지만, 27, 334, 100,000은 아니다. N자리 수 K가 주어지면, K를 최대 (N+1)개의 RUN 수의 합으로 표현하라. 이는 항상 가능함을 증명할 수 있다.입력첫 번째 줄에는 테스트 케이스의 개수 T가 주어진다.각 테스트 케이스는 두 정수 N과 K가 한 줄에 공백으로 구분되어 주어진다.출력각 테스트 케이스에 대해서,첫 번째 줄에는 더해서 K를 만들 RUN 수의 개수 M을 출력한다. (1 두 번째 줄에는 해당하는 M개의 RUN 수를 공백으로 구분해서 출력한다. 만약 답이 ..

문제 링크https://www.acmicpc.net/problem/15683 문제정수로 구성된 2차원 맵을 준다.맵의 오브젝트는 다음과 같다.0: 빈 칸1~5: cctv 종류6: 벽 cctv의 종류별 감시 유형은 다음과 같다. cctv는 각 방향에 대하여 벽을 만나거나 맵의 끝에 다다르기 전까지 일직선으로 감시할 수 있다.cctv의 감시망은 벽(6)을 뚫지 못한다.또한 cctv는 90도씩 회전할 수 있다.cctv의 최대 개수는 8개다.자세한 설명은 링크를 보는 게 좋다. 예시도 친절하게 제시한다. cctv가 맵에서 감시하지 못하는 부분을 사각지대라고 하는데, cctv를 적절히 회전하여 최소 사각지대의 개수를 찾아 출력하는 문제다.  설계어차피 cctv의 최대 개수는 8개이고, 회전 각도는 90도씩 4번이..

문제 링크https://www.acmicpc.net/problem/31835  문제T | F | T & F | T & F위 식과 같이 값은 T와 F, 연산자는 |과 &로만 구성된 수식이 주어진다. | 연산은 양쪽에 있는 두 피연산자 중 하나 이상이 T이면 결괏값이 T이고, 그렇지 않으면 F이다. & 연산은 양쪽에 있는 두 피연산자가 모두 T이면 결괏값이 T이고, 그렇지 않으면 F이다. | 연산과 & 연산의 우선순위는 같고, 왼쪽부터 오른쪽으로 차례로 계산한다고 가정한다.여러분은 연산자와 값을 적절히 바꾸어 원하는 계산 결과가 나오도록 해야 한다. 이때, 연산자와 값을 바꾸는 횟수를 최소화해야 한다. 식과 원하는 계산 결과가 주어졌을 때, 원하는 계산 결과가 나오도록 연산자와 값을 고치는 최소 횟수를 구하..