끈기 있는 개발 공간

소수소수는 약수가 1과 자기 자신 밖에 없는 수이다.소수와 관련된 알고리즘은 두 가지가 있다.어떤 수 $N$이 소수인지 아닌지 판별하는 방법$N$보다 작거나 같은 모든 자연수 중에서 소수를 찾아내는 방법$N$이 소수가 되려면 2보다 크거나 같고, $N-1$보다 작거나 같은 자연수로 나누어 떨어지면 안된다.$N-2$번 연산하므로 $O(N)$의 시간 복잡도를 가진다.소수 판별 구현 - $O(N)$bool prime(int n) { if(n $N$이 소수가 되려면 2보다 크거나 같고, $\frac{N}{2}$보다 작거나 같은 자연수로 나누어 떨어지면 안된다.$N=a\times{b}$로 나타낼 수 있는데, $a$가 작을수록 $b$는 크다. 가능한 $a$ 중에서 가장 작은 값은 2이기 때문에, $b$는 $\..

최대공약수최대공약수(Greatest Common Divisor)는 줄여서 GCD라고 쓴다.두 수 $A$와 $B$의 최대공약수 $G$는 $A$와 $B$의 공통된 약수 중에서 가장 큰 정수이다.최대공약수가 1인 두 수를 서로소(Coprime)라고 한다.최대공약수를 구하는 가장 쉬운 방법은 2부터 min(A, B)까지 모든 정수로 나누어 보는 것이다.기본 구현int g = 1;for(int i = 2; i 앞의 방법보다 빠른 방법은 유클리드 호제법(Euclidean algorithm)이다.유클리드 호제법은 $a$를 $b$로 나눈 나머지를 $r$이라고 했을 때 $GCD(a, b) = GCD(b, r)$이고, $r$이 0이면 그 때 $b$가 최대공약수임을 이용하는 것이다.예를 들어, $GCD(24, 16) = G..

나머지 연산컴퓨터의 정수는 저장할 수 있는 범위가 저장되어 있기 때문에, 답을 $M$으로 나눈 나머지를 출력하라는 문제가 등장한다.Overflow 문제와 덧셈$(A+B)\mod{B}$하지만, 위 식에서 만약 $A+B$의 연산 결과가 자료형의 범위를 넘어서게 되면 overflow가 발생한다.이 때, $A$와 $B$ 각각에 나머지 연산을 적용하여 overflow를 막을 수 있다.$(A+B)\mod{M}=((A\mod{M})+(B\mod{M}))\mod{M}$곱셈곱셈은 덧셈의 연속이기 때문에 곱셈에서는 다음의 식이 성립한다.$(A\times{B})\mod{M}=((A\mod{M})\times{(B\mod{M})})\mod{M}$나눗셈나눗셈에서는 성립하지 않고 모듈러 역수(Modular Inverse)를 구하여..

https://school.programmers.co.kr/learn/courses/30/lessons/49995접근N개의 바구니에 과자 수가 차례대로 들은 배열 cookie가 입력으로 주어진다.문제에서 요구하는 바는 l ~ m 바구니의 과자 수의 합과 m+1 ~ r 바구니의 과자 수의 합이 같으면서 그 합이 최대로 되는 값이다.제한사항을 확인해보면, cookie의 길이는 1 이상 2,000 이하이기 때문에 이중 for문까지는 괜찮아 보인다.따라서, $O(n^2)$의 성능을 보이는 알고리즘을 택해서 문제를 풀어보겠다.(l부터 m까지의 합) = (m+1부터 r까지의 합) 에서 1부터 n까지의 합을 정의하는 배열 d를 대입해보자.$d[m] - d[l-1] = d[r] - d[m]$$2 * d[m] = d[r..

https://school.programmers.co.kr/learn/courses/30/lessons/17685접근오늘날 어느 서비스를 사용하더라도 기본적으로 검색에 탑재되어 있는 자동완성을 직접 구현하는 문제이다.자동완성을 구현할 때 기본적으로 사용하는 자료구조가 따로 있다고 한다. Trie이다.Trie는 입력된 문자열의 한 문자를 가리키는 노드를 트리 구조의 형태로 가진다.TrieNode는 key, cnt, child 세 가지 멤버변수를 가진다.key문자를 가리킨다.cnt해당 문자의 수를 가리킨다.child자식 TrieNode를 가리킨다.이 문제에서 요구하는 바는 단어를 찾을 때 입력해야 할 총 문자수이다.따라서, cnt의 값이 1이면 한 문자열에서 그 노드까지 방문한 문자의 수만큼이 입력해야 할 ..