티스토리

tkxx_ls Story

검색하기

블로그 홈

tkxx_ls Story

tkxxls.tistory.com/m

tkxx_ls 님의 블로그입니다.

구독자: 0

방명록 방문하기

주요 글 목록

[알고리즘] KMP 알고리즘 KMP 알고리즘은 Knuth-Morris-Pratt라는 세 명의 컴퓨터 과학자가 1977년에 개발한 문자열 검색 알고리즘입니다. 이 알고리즘은 주어진 텍스트 문자열에서 특정 패턴(부분 문자열)이 존재하는 위치를 찾는 문제를 효율적으로 해결합니다. 기본적인 아이디어는 이미 비교한 부분을 재사용하여 중복된 작업을 피하는 것입니다. KMP 알고리즘은 문자열 검색 시 불필요한 비교를 최소화하는 방식으로 작동합니다. 기존의 방법처럼 단순히 한 글자씩 이동하면서 다시 처음부터 비교하는 것이 아니라, 접두사와 접미사 정보를 활용해 효율적으로 패턴을 이동시킵니다. KMP 알고리즘의 특징시간 복잡도: KMP 알고리즘은 패턴과 텍스트의 길이에 비례하는 선형 시간 복잡도인 O(n + m)를 가집니다. 여기서 n은 텍스트 길.. 공감수 0 댓글수 0 2024. 9. 1.
[알고리즘] 라빈-카프 알고리즘 라빈-카프(Rabin-Karp) 알고리즘은 1987년 리처드 M. 카프와 마이클 O. 라빈에 의해 개발된 문자열 검색 알고리즘입니다.이 알고리즘은 주어진 텍스트에서 특정 패턴 문자열을 효율적으로 찾기 위해 해싱(Hashing) 기법을 활용합니다.특히, 롤링 해시(rolling hash)라는 기법을 사용하여 텍스트의 각 위치에서 패턴과의 일치 여부를 빠르게 확인할 수 있습니다. 라빈-카프 알고리즘의 기본 개념은 텍스트와 패턴을 비교할 때, 각 문자를 일일이 대조하는 대신,텍스트의 부분 문자열과 패턴의 해시 값을 비교함으로써 비교 과정을 단순화하는 것입니다.해시 값이 일치하는 경우에만 실제 문자열 비교를 수행하여, 불필요한 비교를 줄이고 속도를 높입니다.이 과정에서 롤링 해시를 사용하여 이전에 계산된 해시 .. 공감수 0 댓글수 0 2024. 8. 29.
[알고리즘] 다익스트라 다익스트라 알고리즘(Dijkstra's algorithm)은 가중치가 있는 그래프에서 시작 노드로부터 다른 모든 노드까지의 최단 경로를 찾기 위한 알고리즘입니다.다익스트라의 특징가중치 그래프: 다익스트라 알고리즘은 가중치가 양수인 그래프에서만 성립합니다. 음수 가중치를 가진 간선이 있는 그래프에서는 다익스트라 알고리즘이 올바른 결과를 보장하지 않습니다. 이는 알고리즘의 근본적인 동작 방식이 간선의 가중치가 양수일 때만 성립하기 때문입니다.단일 출발점: 다익스트라 알고리즘은 특정 출발점에서 시작하여 다른 모든 노드까지의 최단 경로를 찾습니다. 다수의 출발점에서의 최단 경로 탐색은 여러 번의 다익스트라 알고리즘을 실행하거나 다른 알고리즘을 사용해야 합니다.그리디 알고리즘: 이 알고리즘은 기본적으로 그리디 알.. 공감수 0 댓글수 0 2024. 7. 31.
[알고리즘] 오일러 피 오일러 피오일러의 피 함수는 𝜙(𝑁) 또는 P[N] 으로 표시되며, 자연수 N 이하의 양의 정수 중에서 N과 서로소인 수의 개수를 나타내는 함수입니다. 두 수가 서로소라는 것은 공약수가 1 뿐인 경우를 말합니다. 오일러 피 알고리즘'2' 부터 구하고자 하는 값의 제곱근까지의 소인수를 구합니다.결괏값을 갱신합니다.N값에서 소인수를 나눠줍니다.N이 1보다 크면 결괏값을 최종 조정합니다.오일러 피 구현int N; // 구하고자 하는 수int result = N;for (int k = 2; k 1) { // 소인수가 남아있을 때 result -= result / N;}오일러 피 시간복잡도오일러 피의 시간복잡도는 O(Φn logn)입니다. 여기서 Φn 은 서로소 개수 입니다. 증명은 생략하겠.. 공감수 0 댓글수 0 2024. 6. 26.
[알고리즘] 소수 구하기 소수소수는 1보다 큰 자연수 중 1과 자기 자신만을 약수로 가지는 수입니다. 예를 들어, 5는 1 ×5 또는 5 ×1로 수를 곱한 결과를 적는 유일한 방법이 그 수 자신을 포함하기 때문에 5는 소수입니다. 그러나 6은 자신보다 작은 두 숫자의 곱(2 ×3)이므로 소수가 아닌데, 이렇듯 1보다 큰 자연수 중 소수가 아닌 것은 합성수나 비소수라고 합니다. 에라토스테네스의 체소수를 구하는 대표적인 방법으로 에라토스테네스의 체가 있습니다.에라토스테네스의 체 알고리즘은 다음과 같습니다.구하고자 하는 소수의 범위만큼 1차원 배열을 생성합니다.'2'부터 시작해 특정 수의 배수에 해당하는 수를 모두 지웁니다. 이때 특정 수 자신은 지우지 않습니다.배열의 끝까지 2를 반복합니다. 에라토스테네스의 체 구현boolean[].. 공감수 0 댓글수 0 2024. 6. 18.
[알고리즘] LCM LCM최소공배수(LCM, Least Common Multiple)는 두 개 이상의 정수의 공통 배수 중 가장 작은 수를 의미합니다.LCM을 구하는 방법에는 여러 방법이 있지만, 가장 흔히 알려진 방법은 GCD를 이용하는 방법입니다. GCD [알고리즘] GCD - 유클리드 호제법유클리드 호제법이란유클리드 호제법 또는 유클리드 알고리즘은 2개의 자연수 또는 정식의 최대공약수(Greatest Common Divisor, GCD)를 구하는 알고리즘입니다. 호제법이란 말은 두 수가 서로 상대방tkxxls.tistory.com LCM 알고리즘두 수 a와 b의 최소 공배수 lcm(a, b)는 다음과 같이 계산됩니다lcm(a, b) = a × b / gcd(a, b)LCM 구현int gcd(int a, int b).. 공감수 0 댓글수 0 2024. 6. 13.
[알고리즘] GCD - 유클리드 호제법 유클리드 호제법이란유클리드 호제법 또는 유클리드 알고리즘은 2개의 자연수 또는 정식의 최대공약수(Greatest Common Divisor, GCD)를 구하는 알고리즘입니다. 호제법이란 말은 두 수가 서로 상대방 수를 나누어서 결국 원하는 수를 얻는 알고리즘이라는 뜻입니다. GCD 알고리즘 두 개의 정수 a와 b (단, a ≥ b)가 주어집니다.a를 b로 나눈 나머지를 구합니다. 즉, r = a mod b.r이 0이라면, b가 a와 b의 최대 공약수이며, 알고리즘을 종료합니다.r이 0이 아니라면, a는 이전의 b가 되고, b는 이전의 r이 되어 위 과정을 반복합니다.GCD 구현int gcd(int a, int b) { if (b == 0) return a; retu.. 공감수 0 댓글수 0 2024. 6. 12.

문의안내

티스토리
로그인
고객센터

티스토리는 카카오에서 사랑을 담아 만듭니다.