A collection of 92 articles on programming, technology and life.
Concept 문자열에서 부분 문자열을 찾아내는 알고리즘이다. 실제 여러 프로그램에서 Ctrl + F의 찾기 기능은 이 알고리즘을 사용한 것이다. Knuth, Morris, Pratt가 만들어 만든 사람의 앞 글자를 따 KMP 알고리즘이라고 한다. 브루트포스 알고리즘으로 부분 문자열을 찾는다고 했을 때, 시간복잡도는 $O(NM)$ : 문자열 길이 $N$, 부분 문자열 길이 $M$ 접두사(prefix)와 접미사(suffix)을 이용해 중복 탐색을 최소화하여 문자열을 탐색한다. KMP의 시간
Concept 쿼리를 순서대로 해결하는 것이 아닌 문제를 빠르게 해결하기 위해 쿼리 순서를 바꾸는 알고리즘이다. [[DP(Dynamic Programming)]]처럼 정형화 되어 있는 코드는 존재하지 않고 쿼리 문제를 풀 떄 아이디어의 개념으로써 활용된다. 쿼리의 순서를 조정해야 하기 때문에 모든 쿼리의 정보를 다 받은 다음에 처리한다. Offline Query 원리 쿼리는 총 2종류(,
Concept 업데이트가 없는 구간 쿼리를 처리하는 알고리즘이다. 대게 어떤 구간$[s, e]$에 속하는 원소들을 이용해 계산하는 쿼리를 여러 개 처리할 때 사용한다. 처음 쿼리 구간을 $[s1, e1]$이라 하고 다음 쿼리 구간을 $[s2, e2]$라고 하면 $s1$에서 $s2$까지 이동, $e1$에서 $e2$까지의 이동을 최소화하는게 중요하다. 구간의 이동을 최소하기 위해선 쿼리를 순선대로 처리하는 것이 아니라 정렬을 해야하기 때문에 Mo's Algorithm은 [[Offline Query]]에 포함된다.
Concept 소수를 구하는 대표적인 알고리즘이다. 2부터 원하는 수까지 배열로 나열하여 그 중 소수가 아닌 수들을 걸러내는 방법이다. 이 과정을 돌과 쌀을 나누는 '체'와 비슷하다고 하여 라고 한다. 특정 수($N$)가 소수인지 아닌지를 판별하는 것이 아닌 $2$부터 $N$까지 소수가 무엇인지 구하는 알고리즘이다. N이 소수인지 아닌지 판별하는 알고리즘의 시간 복잡도는 $O(N 0.5)$이다. 시간 복잡도는 $O(N log{N} * log{N})$이다. Sieve O
Concept 배낭의 용량(Capacity)가 정해져 있을 때 물건의 무개($W$)와 가치($V$)을 고려해 최대 이윤이 나도록 물건을 가져가는 문제를 일컫는다. 물건을 쪼갤 수 있는 Fraction Knaspack Problem과 물건을 쪼갤 수 없는 0-1 knapSack Problem으로 나뉜다. Fraction Knaspack Problem에 경우 단위 무게 당 이윤의 내림차순된 값을 통해 으로 문제를 해결할 수 있다. 0-1 knapSack Problem은 [[DP(Dy