반응형 알고리즘58 [문자열] KMP 알고리즘 KMP 알고리즘이란? 『KMP 알고리즘』 문자열을 검색할 때, 불필요한 반복을 줄이기 위해 검색 문자열의 접두사와 접미사의 중복 길이를 이용한 알고리즘 입니다. (※ Knuth–Morris–Pratt algorithm, KMP) [Case] 문자열을 검색할 때 비효율적인 알고리즘 A = aab, B = aaaaaaaaaa 비교 문자열 (A)를 대상 (B)와 일일이 비교하는 경우입니다. 결과적으로 위의 경우에는 문자열 A, B는 같은 구간이 없지만, (A) 문자열 『aab』 에서 『b』를 제외하고는 B문자열과 일치하기에 (A) 문자열 전체로 불필요한 비교를 하게 됩니다. 문자열 A의 길이가 N / 문자열 B의 길이가 M일 때, 결과적으로 O(NM)의 시간을 가집니다. ※ 관련 문제: [BOJ] 1120 문.. 2021. 2. 22. LCS(Longest Common Subsequence) 알고리즘 LCS(Longest Common Subsequence) '최장 공통 부분 수열'로 연속된 부분 문자열 Substring과는 다른 개념이다. ▶ [BOJ] 5582 공통 부분 문자열 가령, 아래 두 문자열이 주어졌을 때, - A B C D H E F - B C D E F → 최장 공통 Substring 'BCD' → 최장 공통 Subsequence는 'BCDEF' LCS를 DP를 통해 해결할 수 있다. 도표를 통해 해석해보겠다. ACAYKP CAPCAK A[i] == B[j] 인 경우, LCS[i][j] = LCS[i][j] + 1; A[i] != B[j] 인 경우, Math.max(LCS[i-1][j], LCS[i][j-1]) LCS의 길이는 마지막 값을 출력하면 된다. LCS의 길이(크기) 출력하는 .. 2021. 2. 21. 소수 (Prime Number) 찾기 - 3 해당 게시글은 에라토스테네스의 체를 이용해서 소수 찾기를 구현한 게시글입니다. - 소수 (Prime Number) 찾기 - 1 - 소수 (Prime Number) 찾기 - 2 ★ 에라토스테네스의 체의 핵심은 소수의 배수를 제외 시키는 것이다. 출처: WIKI ▶ 다음과 같이 2~50까지의 숫자가 존재한다. (1은 소수가 아니므로 제외) ▶ 먼저, 『2』의 소수 여부를 판단한다. 소수라면 『2』의 배수를 모두 제외시킨다. (『2』로 나누어지는 합성수들이기 때문.) ▶ 마찬가지로 『3』에 대해서도 동일하게 처리하면 다음과 같다. ▶ 『4』는 앞서 『2』의 배수에서 처리되었으므로 넘어간다. ▶ 이러한 방법으로 소수의 배수를 제외 시키면 소수 여부를 판단하는 대상이 좁혀지기 때문에 효율적이다. 결과적으로 아래 .. 2021. 2. 21. 소수 (Prime Number) 찾기 - 2 해당 게시글은 제곱근 범위를 이용해 소수 찾기를 구현한 내용입니다. - 소수 (Prime Number) 찾기 - 1 - 소수 (Prime Number) 찾기 - 3 해당 숫자의 소수 여부를 판단할 때 해당 숫자의 루트값까지만 계산한다. 이때 나누어 떨어지지 않으면 소수가 아니다! Q) 왜 소수 검사할 때 N의 제곱근까지만 할까? A) N은 소수가 아닌 합성수로 A * B = N 이 가능하다. (A > B) N의 제곱근을 X라고 두면, N = A * B = X * X 성립한다. A > X 라고 하면, B ≤ X가 되어야 하므로 B ≤ X < A 가 되므로 소수를 찾을 때, 제곱근 X (≥ B)까지만 찾으면 확인할 수 있다. 소수 (Prime Number) 찾기 - 1방식과 비교하면 연산 범위를 [2, N].. 2021. 2. 21. 소수(Prime Number) 찾기 - 1 소수(Prime Number)란? 1과 자기자신으로만 나누어지는 숫자 ex) 2, 3, 5, 7, ... ★ 소수를 구하는 방법은 크게 3가지 방식이 존재한다. ① 2 ~ N-1 까지 나누어지는지 확인 ② 2 ~ √N 까지 나누어지는지 확인 ③ 에라토스테네스의 체 각 방식을 통해서 효율적인 알고리즘에 대해 알 수 있습니다. 해당 게시글에서는 첫번째 방법에 대해서만 먼저 작성합니다. - 소수 (Prime Number) 찾기 - 2 - 소수 (Prime Number) 찾기 - 3 소수 여부 확인할 때, 가장 먼저 떠오르는 구현 방법은 정의(Definition)를 이용하는 것이다. 즉, 특정 숫자 「X」 에 대해서 2 ~ X - 1 까지 나누어 떨어지는 경우가 있는지 확인하는 방법이다. 직관적인 방법이지만 여.. 2021. 2. 20. 연속된 부분 합(연속합) - 1 (완전 탐색) ※ 구간합을 구하는 효율적인 방법 연속된 부분 합(연속합) - 1 (완전 탐색) 연속된 부분 합(연속합) - 2 (Prefix Sum) 연속된 부분 합(연속합) - 3 (DP) [구간합] Sum of sub-matrix (2D Array) 완전 탐색 Q) 아래와 같이 배열이 주어질 때 특정 연속 구간의 합 중 최대값을 구하시오. if) 구간의 길이가 5 일 때, 구간의 최대합은? 길이 6을 가지는 시작 지점(start) ~ 끝 지점(end)까지 합을 매번 더해서 구할 수 있습니다. (Sliding Window 혹은 Inchworm Algorithm) 직관적이지만 시간복잡도가 좋다고 할 수는 없습니다. [O(N3) 코드] int ans = 0; int N, A[LM]; void findPartialSum(.. 2021. 2. 20. 세그먼트 트리(Segment Tree) 세그먼트 트리 구간에 대한 정보를 저장하기 위한 트리 자료구조 O(N logN) N == 8일 때 Segment Tree 특정 구간의 최적화된 답을 구하는 문제인 경우 빠른 시간안에 답을 얻을 수 있음 (ex. 구간의 합, 최대값, 최소값, 곱) N == 5일 때 Segment Tree - 완전 이진트리 형태 (Root Node의 인덱스가 1번인경우 보다 쉽게 자식노드에 접근 가능) : 재귀적인 구조로 구현을 많이 합니다. - 전체 구간이 [0, N-1]일 때, 단말 노드는 구간 길이 1인 구간을 갖습니다. → 배열 = [a, b, c, d, e]가 있을 때 단말노드(Leaf Node)에 배치된다고 보면 됩니다. * 트리에서 실제 노드번호는 N의 크기에 따라 좌우되기 때문에 단말노드 번호를 쉽게 알 수 .. 2021. 2. 20. [수학] 피보나치 수열 구현 (재귀, DP) 피보나치 수열(Fibonacci Numbers)이란? 1 → 1 → 2 → 3 → 5 → 8 → 13 → 21 → 34 → 55 → 89 → 144 → 233 점화식으로 표현하면 다음과 같다. 이를 구현하는 방법은 크게 다음과 같다. - 재귀 방식 (Recursion) - 동적 계획 (Dynamic) 재귀 방식(Recursion) Top-down 방식으로 f(0), f(1)과 같이 작은 부분의 값들이 여러번 호출된다. public class Main { public static void main(String[] args) { int n = 40; long start = System.currentTimeMillis(); System.out.println( fibonacci(n) ); long end = S.. 2021. 2. 18. 이전 1 ··· 3 4 5 6 다음 반응형
