개념 설명 중국인의 나머지 정리 (CRT) 중국인의 나머지 정리는 모듈리(mod p에서 p)가 서로소(coprime)일 경우 선형 합동 집합에 대한 특수한 해를 제공한다. 즉, 임의의 정수 집합 $a_i$와 pairwise(쌍) 서로소(paiwise coprime integers) $n_i$가 주어졌을 때 다음과 같은 선형 합동식이 성립한다. ! 참고로, "pairwise coprime integers"는 우리가 정수 집합 ${n_1, n_2, ..., n_i}$를 가지고 있을 때, 집합에서 선택된 모든 정수 쌍은: $\gcd(n_i, n_j) = 1$임을 의미한다. $ x \equiv a_1 \mod n_1$ $ x \equiv a_2 \mod n_2$ . . . $x \equiv a_n \mod n_..
개념 설명 모듈러 제곱근 르장드르 기호(Legendre Symbol)에서 우리는 숫자가 소수(prime) 모듈러의 제곱근인지를 결정할 수 있는 빠른 방법을 소개했다. 우리는 더 나아갈 수 있다: 그러한 제곱근을 효율적으로 계산하기 위한 알고리즘이 있다. Tonelli-Shanks라고 불리는 것이 있는데, 이것은 19세기에 이탈리아 인에ㅕ의해 처음 묘사되었고 1970년대에 Daniel Shanke에 의해 독립적으로 재발견 되었다는 사실에서 재미있는 이름을 얻었다. 2가 아닌 모든 소수는 모든 홀수가 다음과 같은 합동성을 띄기 때문에 $p \equiv 1 \mod 4$ 또는 $p \equiv 3 \mod 4$ 형식이다. 앞선 문제의 힌트처럼 $p \equiv 3 \mod 4$의 경우, 제곱근을 계산하기 위한..
개념 설명 르장드르 기호 2차 잉여에서 우리는 제곱근 정수 모듈러를 취하는 것이 무슨 의미인지 배웠다... 우리는 또한 제곱근을 가지는 것이 항상 가능한 것은 아니라는 것을 알았다. 이전의 경우 $p = 29$일때 간단한 루트 계산으로도? 충분히 빨랐지만 p가 커질수록 이 방법은 엄청나게 불합리해진다. 다행히도 르장드르 덕분에 정수가 한 번의 계산으로 2차 잉여인지 확인할 수 있는 방법이 있다. 다음에서 우리는 소수 p에 대한 모듈러 작업을 한다고 가정할 것이다. 르장드르 기호를 살펴보기 전에 2차 잉여의 흥미로운 성질을 보기 위해 잠시 돌아가보자. 이차 잉여 * 이차 잉여 = 이차 잉여 이차 잉여 * 이차 비잉여 = 이차 비잉여 이차 비잉여 * 이차 비잉여 = 이차 잉여 ! 이것을 쉽게 기억하는 방법은..
개념 설명 제곱 잉여 우리는 모듈러 연산에서 곱셈과 나눗셈에 대해서 살펴보았다. 그러나 제곱근 모듈러를 정수로 취하는 것은 뭘 의미할까? 해당 논의를 위해 모듈러 $p = 29$를 사용해보자. 우리는 정수 $a = 11$을 취하여 $a^2 = 5 \mod 29$ 임을 계산할 수 있다. $a = 11, a^2 = 5$로서 우리는 5의 제곱근이 11이라고 말한다.(?) 기분은 좋지만, 이제 18의 제곱근에 대해서 생각해보자. 위에서, 우리는 $a^2 = 18$인 정수 a를 찾을 필요가 있다는 것을 안다. 첫번째 아이디어는 $a=1$부터 시작하여 $a=p-1$까지 루프를 도는 것이다. 이 논의에서 p가 너무 크지 않으면 우리는 빨리 찾아낼 수 있을 것이다. 시도해보자. 이것을 코딩해보고 무엇을 찾는지 보자. ..
나이트의 이동 문제는 BFS로 최소 이동 수를 찾는 문제이고 이동하는데 걸리는 횟수를 dist에 저장하면서 bfs를 돌리면 간단하게 풀립니다. 풀이 #include using namespace std; int dx[8] = {-1, -1, -2, -2, 1, 1, 2, 2}; int dy[8] = {-2, 2, -1, 1, -2, 2, -1, 1}; // 나이트의 이동 경로 int main(void) { ios::sync_with_stdio(0); cin.tie(0); int n, l; cin >> n; //테스트 케이스 입력 while (n--) { cin >> l; queue q; //bfs를 위한 queue int dist[301][301]; //distance를 저장하는 이차원 배열 for (in..
토마토 문제는 대표적인 bfs 거리 구하기 문제의 응용인데 저번 문제로 2차원에서 토마토를 다루었지만 이번에는 3차원에서 토마토로 다루도록 해보겠습니다. 해당 문제를 푸는 데에 핵심적인 개념은 bfs에서 dict라는 array를 통해 거리를 구하는 것에서 단순히 일 수로 바꾸면 되는건데 시작점이 한 개가 아니라 여러개라는 점입니다. 시작점이 여러개라는걸 해결하는 방법도 간단합니다. 시작점들을 미리 큐에 두고 bfs를 돌리면 됩니다. 어차피 최소 일수를 구하는 것이기 때문에 어떠한 시작점에서 방문했다면 다른 시작점에서 방문하지 않을 것이고 큐에서 bfs를 진행하는 과정은 일 수에 따라서 큐에 들어갑니다. 풀이 #include using namespace std; int box[101][101][101]; ..
차마 뭘 해야할지 모르겠어서.. 웹을 하게 되었습니다. 이것저것 다 잘하고싶은데 골고루 못하는게 아쉽네여 xss-1번 문제는 드림핵에 나와있는 설명대로 함께 풀어보면 되는데 xss-1을 풀고 바로 xss-2를 풀자니 갑자기 난이도가 급상승 하는 것 같았습니다. 분석 다운로드 한 소스코드에서 필요한 부분만을 봅시다. def read_url(url, cookie={"name": "name", "value": "value"}): cookie.update({"domain": "127.0.0.1"}) try: options = webdriver.ChromeOptions() for _ in [ "headless", "window-size=1920x1080", "disable-gpu", "no-sandbox", "d..
저는 평소에 vm에 우분투를 설치하고 그걸 또 docker 컨테이너랑 포트포워딩을 해서 사용합니다.. 근데 vm이 계속 꺼지고 그로 인해 docker가 종료되어버리는 문제가 있는데 이를 위해서 일단 항상 켜두던 docker가 꺼졌을 때 제가 해결하는 법을 그냥 메모해두려고 합니다. sudo docker ps -a 일단 docker에 어떤 컨테이너가 있는지 확인합니다. sudo docker start [container name] 해당 컨테이너를 실행시키고 (ex. sudo docker start pwn16) run으로 하면 안될 듯 포트포워딩, 폴더 마운트로 인해 각각을 실행시키고 나면 각 우분투 내에서 attach 하여 ssh를 실행시켜줍니다. sudo docker attach [container na..
