풀캠정글러

밀러-라빈 알고리즘(https://uneducatedjungler.tistory.com/121)에서 이어지는 글 폴라드 로 알고리즘은 입력된 정수 n의 랜덤한 인수를 뽑아내는 알고리즘이다. 정리에 앞서 거칠게 폴라드 로를 요약하자면 아래와 같다. "n과 d의 공약수를 발견할 때까지 d에 유사난수를 대입한다" 얼핏 보면 n에 1부터 차례대로 나눠보는 것과 다름없는 굉장히 무식해보이는 방법같아 보이지만, 실제로는 의외로 빠르다. 그 이유는 생일 역설을 보면 알 수 있다. 생일 역설 (https://ko.wikipedia.org/wiki/%EC%83%9D%EC%9D%BC_%EB%AC%B8%EC%A0%9C) 생일은 366일이라는 한정된 range를 갖고 있다. 따라서 367명 이상이 있으면 반드시 생일이 같은 ..

페르마의 소정리(https://uneducatedjungler.tistory.com/120)에서 이어지는 글 n이 소수라면 (n의 배수가 아닌) 모든 a에 대해 위 식을 만족한다는 것이 페르마의 소정리이다. 즉, 어떤 단 하나의 a에 대해서라도 위 식을 만족하지 못함이 발견된다면, p는 100% 소수가 아니게 된다. 이에 확률론적으로 접근하면, p가 많은 수의 a에 대해 위 식을 만족할수록 p가 소수일 확률이 높아진다. 페르마 계열의 소수판별법은 여럿이 있는데, 요약하면 다음과 같다. n이 소수라면 위 식을 만족할테니, 충분히 많은 아무 a나 넣어보며 위 식을 만족하는지 확인하자. 한번이라도 만족을 안함이 발견되면 n은 소수가 아니다. break and return False 테스트를 다 통과하면 p는 ..

p가 소수라면, (p의 배수가 아닌) 모든 a에 대해 a^(p-1)은 mod p에서 1과 합동이다. 증명은 수학적귀납법으로 간단히 가능하니 패스 (위키에 있다) 정수론에서 C뿌리기를 당한 나도 다시보니 바로 기억날 만큼 유명한 정리인데, PS에서는 조합론적 문제에 이용할 수 있고 이 테크닉이 매우 흥미롭다. 팩토리얼이나 지수승을 주로 다루는 조합론은 자연스럽게 매우 큰 수들을 다루게 되는데, 컴퓨터를 이용한 계산에서는 보통 적당히 큰 수로 나눈 나머지를 다루는 모듈러 연산으로 합의를 본다. 이때 문제가 되는 것이 Combination, Permutation 등인데, 팩토리얼이 분모에 오는 위의 개념들은 팩토리얼의 실제 값 대신 모듈러 연산의 나머지를 쓰니 계산 결과가 실제 값과 틀리게 된다. 그런데 이때..

문자열 알고리즘에서 유용하게 쓰이는 suffix array. 사전순으로 정렬된 suffix array를 구하기만 한다면, 그로부터 LCP를 구하여 중복 부분문자열을 쉽게 구할 수 있다. 하지만 접미사들을 사전순으로 정렬하여 suffix array로 만드는 그 시간이, 문자열이 길어질수록 끔찍하게 길어진다. 길이 n자리의 문자열들을 사전순으로 정렬하려면 자리수마다 sort하여 총 n번의 sort가 필요한데, 이걸 길이가 수만 수십만인 문자열에 적용할 수 있을 리가 없다. 때문에 접미사의 특징을 이용하여 n번의 sort 대신, logn번의 sort만으로 사전순 정렬이 가능하게 할 필요가 있다. 맨버 마이어스 알고리즘을 한줄로 요약하면 아래와 같다. '접미사의 정렬에 한해서는 n번의 sort를 하지 않고, 0..

DAC는 작은 문제로 쪼갰을 때 그것들이 서로 관계가 없을 때 쉽게 쓸 수 있다. 위상적으로(그래프) 접근하자면, 작은 문제라는 점들 사이에 연결 관계가 없고, 작은 문제와 큰 문제 사이의 연결 관계(규칙)가 한눈에 보일 때 쓸 수 있다. 2630 색종이 만들기(https://www.acmicpc.net/problem/2630)를 예로 들자면 전체 색종이를 넷으로 잘랐을 때, 1사분면이 덩어리든 섞였든 2사분면의 결과와는 전혀 상관이 없다. 그리고 큰 문제가 안풀릴때 작은 문제 넷으로 나눈다는 명확한 규칙이 보인다. 이렇게 문제를 서로 독립적인 부분 문제들로 쉽게 분리가 가능할 때 DAC를 사용한다. 반면 DP는 작은 문제로 쪼갰을 때에도 그것들이 서로 관계가 있을 때 쓴다. 위상적으로 접근하자면, 작은..

Selection sort 리스트의 i번째까지 정렬된 상태에서 나머지 n-i개의 리스트를 훑는다 그중 가장 작은 원소를 찾아 i+1번째에 놓는다 나머지가 없어질 때까지 반복 Insertion sort 리스트의 i번째까지는 정렬된 상태에서 리스트의 i+1번째 원소를 본다 이미 정렬된 길이 i의 리스트를 훑으면서 i+1원소가 들어갈 위치를 찾아 넣는다 n번째 원소까지 반복 Bubble sort 이웃한 두 원소를 비교해서 정렬한다 한칸씩 이동하며 n-1번 반복하면 가장 큰 원소 하나가 리스트 끝에 온다. n개의 원소가 모두 정렬될 때까지 위를 반복 단순히 (n-1)C2번의 모든 비교를 수행하는 selection, insertion, bubble의 시간복잡도는 n^2이다 리스트의 처음부터 끝까지 훑는 작업을 n..

저는 DFS랑 BFS를 쓰는 문제를 딱 하나씩만 풀어봤고 이사람이 하는 말은 아무 공신력이 없습니다. DFS BFS를 이제 다음주차에 배울텐데, 느낌이 휘발되지 않도록 다음 주차를 위해 기록해둡니다. DFS의 재귀가 for와 if의 합성으로 자기 자신을 다시 명령하는 방법으로 이루어진다면, BFS는 queue라는 list의 원소를 태우며 작동하는 while문의 끝에 새 땔감을 추가하는 방식으로 이루어진다. DFS는 재귀 사이클보다 우선적으로 주어진 if문에 의해 주어진 목표를 만족함을 감지하면 반복을 마치고, BFS는 while queue문이 할일을 다 끝내서 결과적으로 헛돌면서 재료만 태우다가 queue가 빈 리스트가 되면 반복을 마친다. DFS는 컴퓨터가 코드를 위에서부터 차례대로 실행하는 특성상 하..