[Algorithm] 문자열 검색 - KMP 알고리즘
* Python을 기준으로 합니다문자열 검색 - KMP 알고리즘 (Knuth-Morris-Pratt Algorithm)- 개념KMP (Knuth-Morris-Pratt) 알고리즘 : 불일치가 감지되기 이전까지의 문자열은 다시 비교할 필요가 없다는 점을 활용함이를 통해 $O(NM)$의 time complexity를 가지는 Naive approach에 비해 KMP 알고리즘은 $O(N+M)$의 time complexity로 줄일 수 있음KMP를 위한 문자열 전처리 : 불일치가 발생했을 때 건너뛸 문자 수를 결정하기 위함먼저 건너뛸 문자 수를 결정하기 위해, 패턴 크기 `M`과 동일한 크기의 배열 `lps[]`를 선언함- `lps[]`는 길이가 최대인 접두사(prefix)-접미사(suffix) 배열을 의미이후 ..
[Algorithm] 문자열 검색 - 라빈-카프 알고리즘
* Python을 기준으로 합니다문자열 검색 - 라빈-카프 알고리즘 (Rabin-Karp Algorithm)- 개념문자열 검색 (String Matching) : 주어진 문자열 내에서 특정한 패턴을 가진 문자열을 탐색하는 것e.g.) `This is Rabin Karp Algorithm`라는 문자열이 주어졌을 때, 패턴 `Karp`는 14번째 index에 있음이때 naive 한 문자열 검색 방법으로써 전체 문자열을 순회하면서 주어진 패턴과 일치하는지 여부를 판단하는 방식을 고려할 수 있음- BUT, 해당 방식은 $N$ 길이의 문자열과 $M$ 길이의 패턴에 대해 $O(NM)$의 time complexity가 소모되므로 길이가 긴 문자열에 적용하기 어려움라빈-카프 알고리즘해시를 사용하여 일치하는 패턴을 탐색..
[Algorithm] 구현 - 시뮬레이션
* Python을 기준으로 합니다구현 - 시뮬레이션 (Simulation)- 개념시뮬레이션 : 문제에서 주어진 과정을 하나씩 차례대로 직접 수행해 나가는 유형 시뮬레이션 문제 접근하기- 주어진 문제를 최대한으로 분리하기- 예외 처리는 독립적인 함수로 구분하기특히 시뮬레이션 문제는 2차원 배열을 활용하는 경우가 많으므로 행렬 연산을 응용해서 사용할 수도 있음- 문제가 길기 때문에 잘 분석해야함- 구현1. 행렬 연산행렬 덧셈, 뺄셈, 곱셈#행렬 덧셈def matrix_sum(a,b): result = [] for arow ,brow in zip(a, b): row = [] for aele, bele in zip(arow, brow): row.append..
[Algorithm] 소수 판별 - 밀러-라빈 판정법
* Python을 기준으로 합니다소수 판별 - 밀러-라빈 판정법 (Miller-Rabin Primality Test)- 개념밀러-라빈 소수 판정법간단한 소수 판별은 $O(\sqrt{n})$의 time complexity를 가지고, 에라토스테네스의 체를 사용하면 $O(n \log \log n)$으로 개선 가능 하지만, 여전히 상당히 큰 수에 대해서는 소수 판별을 적용하기 어려움밀러-라빈 판정법은 기존 소수 판별법들과 달리 결정론적으로 동작하지 않고 확률적으로 동작하지만, 상당히 빠른 time complexity를 달성할 수 있음- 이때 $n 이론적 유도먼저 모든 짝수는 2를 제외하면 소수가 아니므로 $n$을 홀수인 소수라고 가정하자그러면 $n-1$을 정수 $s$에 대해 짝수 $2^{s}$와 홀수 $d$의 ..
[Algorithm] 최대공약수, 최소공배수
* Python을 기준으로 합니다최대공약수 (Greatest Common Divisor, GCD) & 최소공배수 (Least Common Multiple, LCM)- 개념최대공약수 : 두 수의 약수들 중에서 공통되면서 가장 큰 약수최소공배수 : 두 수의 배수들 중에서 공통되면서 가장 작은 배수기본적으로 최대공약수, 최소공배수 모두 완전 탐색으로 찾을 수 있음- 최대공약수의 경우 $O(N)$의 time complexity, 최소공배수는 $O(NM)$의 time complexity가 소모됨이때 유클리드 호제법을 활용하면 최대공약수 계산을 $O(\log n)$으로 해결 가능함유클리드 호제법두 수 $a, b$ ($a>b$)에 대해, $a$를 $b$로 나눈 나머지를 $r$이라 하면, $a$와 $b$의 최대공약수는..
[Algorithm] 소수 판별 - 에라토스테네스의 체
* Python을 기준으로 합니다소수 판별 - 에라토스테네스의 체 (Sieve of Eratosthenes)- 개념소수 : 2보다 큰 자연수 중 1과 자기 자신 만을 약수로 가지는 수기본적으로 완전 탐색을 사용할 수 있지만, $O(n)$의 time complexity가 소모되므로 큰 수에 대해서는 비효율적임- 이때 자연수의 약수는 대칭적으로 구해진다는 것을 고려하면, $O(\sqrt{n})$의 time complexity로 줄일 수 있음에라토스테네스의 체 : $N$ 보다 작거나 같은 모든 소수를 찾을 때 사용할 수 있고, $O(n \log \log n)$의 time complexity를 가짐에라토스테네스의 체 동작과정2부터 $N$까지의 모든 자연수를 나열남은 수 중에서 처리되지 않은 가장 작은 자연수 $..