티스토리

초보프로그래밍

검색하기

블로그 홈

초보프로그래밍

lms0806.tistory.com/m

꾸준히 성장중인 개발자 입니다.

구독자: 18

방명록 방문하기

728x90

반응형

주요 글 목록

ShiftOr 알고리즘 이번 시간에는 ShiftOr이라는 근사 문자열 매칭 알고리즘에 대하여 이야기해보고자 합니다. unix 계열의 agreap이라는 명령어에서 사용하고 있습니다.https://en.wikipedia.org/wiki/Agrep agrep - WikipediaFrom Wikipedia, the free encyclopedia agrep (approximate grep) is an open-source approximate string matching program, developed by Udi Manber and Sun Wu between 1988 and 1991,[1] for use with the Unix operating system. It was later ported to OS/2, DOS, anden.. 공감수 1 댓글수 0 2024. 7. 28.
Two-Way String-Matching에 대하여 오늘은 KMP 방식과 Boyer-Moore의 방식을 조합하여 양방향으로 탐색하는 Two-Way String Matching Algorithm에 대하여 알아보도록 하겠습니다. python 3.10에서 적용한 이후 약 25배가량의 엄청난 효과를 보았다고 알려진 알고리즘 입니다.C의 strstr의 하위 문자열 함수를 구현하는데에도 사용되어져 있습니다. 찾고자 하는 문자열이 앞에 있는 경우개수 / 문자열 길이 / 패턴 길이kmp(s)boyer-moore (s)rabin-karp (s)two-way String Macthing (s)100,000 / 2,000 / 107.926154.06316.30524.87610,000 / 5,000 / 100.96616.5241.7982.69 찾고자 하는 문자열이 뒤에 있는 .. 공감수 0 댓글수 0 2024. 7. 21.
rabin-karp 이번에는 hashing을 활용한 문자열 매칭 알고리즘인 라빈-카프(rabin-karp)에 대해 알아보고자 합니다. 라빈-카프 알고리즘의 시간복잡도는 O(N)으로 지금까지 진행하였던 왠만한 문자열 매칭 알고리즘보다 빠르다는 장점이 있습니다.그치만, 여러 가지 다양한 부분에서 문제점이 있어 실제 서비스에서는 사용하기 어렵다는 단점이 있습니다. 장점 - 시간이 빠르다단점 - hashing 값이 충돌이 날 수 있다. - overflow가 발생할 수 있다. "abbaba"라는 문자열에 "aba"라는 문자가 포함되어 있는지 확인하는 방법을 예시로 들어보겠습니다.hashing을 사용하기 때문에, 자리수마다의 문자의 아스키 코드 넘버에 특정 값을 곱하여 하나의 숫자 단위로 표현합니다.2를 활용하여 예시를 들면 pat.. 공감수 0 댓글수 0 2024. 7. 11.
Boyer-Moore vs KMP https://lms0806.tistory.com/210 A Fast StringSearching Algorithm 리뷰해당 논문은 boyer–moore 알고리즘 이라고 불리는 kmp와 비슷한 알고리즘에 대하여 설명하고 있습니다. 보이어무어 알고리즘은 불필요한 것은 건너뛰고, 검색을 빠르게 하자는 것에서 KMP와 유사lms0806.tistory.com이전 포스팅에서 보이어-무어에 대해 설명중인 논문에 대해 설명을 했었습니다.https://lms0806.tistory.com/211 JAVA에서의 Boyer-Moore해당 글은 보이어 무어 알고리즘을 사용하고 있는 JAVA의 내부 코드에 대해 이야기하고자 합니다.Boyer-Moore에 대해서는 해당 글 참조 부탁드립니다.https://lms0806.tisto.. 공감수 1 댓글수 0 2024. 6. 25.
C++ 코드를 JAVA로 바꿔보자 오늘은 https://www.acmicpc.net/problem/2557 문제를 통과하는 코드인 cpp 코드를 java코드로 바꿔주는 소스를 작성해 봤습니다. 2557번: Hello World Hello World!를 출력하시오. www.acmicpc.net 코드 컨벤션을 준수한 코드를 기준으로 작성했습니다. 테스트 cpp 코드 #include using namespace std; int main(){ cout 1 && s[1].contains("main")) { sb.append("public class Main {").append("\n"); sb.append("public static void main(String[] args)").append(iostream ? "throws IOException.. 공감수 0 댓글수 1 2023. 10. 10.
트리를 활용한 문자열 비교 알고리즘 해당 알고리즘은 결정적 유한 오토마타를 학습하면서 떠오른 아이디어로 개발하였습니다. https://ko.wikipedia.org/wiki/%EA%B2%B0%EC%A0%95%EC%A0%81_%EC%9C%A0%ED%95%9C_%EC%83%81%ED%83%9C_%EA%B8%B0%EA%B3%84 결정적 유한 상태 기계 - 위키백과, 우리 모두의 백과사전 위키백과, 우리 모두의 백과사전. --> ko.wikipedia.org 기존 map을 활용하여 중복을 제거하고, containsKey로 해당 문자열을 포함하고 있는지 체크하는 방식이 아닌, 트리를 활용하여 중복도 제거하고, 부분 문자열이 아닌 특정 문자열이 있는지 체크하는 알고리즘 입니다. 기존의 트리를 생각한다면 이런방식의 무방향 트리나, 방향이 있는 트리를 .. 공감수 0 댓글수 0 2023. 8. 17.
배열 뒤집기 시간 측정 C++하시던 분이 JAVA를 시작하게 되면서 C++에 있는 reverse()에 대해 여쭤봤었습니다. 그러면서 갑자기 궁금한 내용이 있어서 포스팅을 하게 되었습니다. JAVA에는 뒤집기 함수가 없어 직접 배열을 만들어 뒤집거나 하는 방식으로 진행해야 합니다. (lower_bound, upper_bound도 없어..) JAVA의 배열 뒤집기 시간측정을 해보겠습니다. n은 10,000,000으로 측정해봤습니다. 배열 long beforeTime = System.currentTimeMillis(); int[] arr = new int[n]; for(int i = 0; i < n; i++) { arr[i] = i; } int[] arr1 = new int[n]; for(int i = 0; i < n; i++) {.. 공감수 0 댓글수 0 2023. 3. 14.
배열 vs ArrayList vs Set 무엇이 더 빠를까? https://www.acmicpc.net/problem/27622 27622번: Suspicious Event Input begins with a line containing an integer N (1 ≤ N ≤ 1000) representing the number of events in the given record. The next line contains N integers Ai (−1000 ≤ Ai ≤ 1000; Ai ≠ 0) each representing an event in chronological order. It is gua www.acmicpc.net 궁금증은 해당 문제로 해결하였습니다. 문제 지문을 번역해드리자면 0이상의 상수 = 로그인 0이하의 상수 = 로그아웃 로그인하지 않고 .. 공감수 0 댓글수 0 2023. 3. 1.
강한 연결 요소 (Strongly Connected Component) 강한 연결 요소 (Strongly Connected Component)는 SCC라고 불리는 알고리즘 입니다. 유향 그래프에서 특정 노드에서 다른 노드들을 걸쳐 다시 특정노드로 돌아올 수 있으면, 노드들이 강하게 연결되어 있다 라고 합니다. DFS를 배우셨다면, 조금 쉽게 이해하실 수 있을거 같습니다. ex) https://www.acmicpc.net/problem/26146 26146번: 즉흥 여행 (Easy) 1번 정점에서 출발하면 모든 정점을 방문할 수 있는 경로가 존재하지만, 2번 정점에서 출발하면 모든 정점을 방문할 수 있는 경로가 존재하지 않으므로, 답은 No가 된다. www.acmicpc.net 1에서 2를 걸쳐 3으로 갔다가 다시 1로 돌아올 수 있음, 1에서 4로 갔다가 다시 돌아올 수 있.. 공감수 0 댓글수 0 2023. 1. 26.
백트래킹(Backtracking) 백트래킹(Backtracking)은 답을 찾아가는 도중, 정답이 아닐거 같으면 뒤로 돌아가서 다시 답을 찾아가는 과정을 통해 해답을 구하는 방식의 알고리즘입니다. DFS을 알고 있다면, 이해하기 쉽습니다. DFS : 1번 방문한 곳은 다시 방문하지 못한다. 백트래킹 : 1군데를 여러번 방문할 수 있다. ex) https://www.acmicpc.net/problem/15649 15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net import java.io.BufferedReader; import java.io.IO.. 공감수 0 댓글수 0 2023. 1. 25.
SPFA(Shortest Path First Algorithm) SPFA(Shortest Path First Algorithm) 알고리즘은 "음수 간선을 포함한 데이크스트라 알고리즘"으로 이해하면 편한 "벨만 포드 알고리즘"을 개선한 알고리즘 입니다. BFS - 데이크스트라 - 벨만포드(SPFA)로 학습을 진행하시면 편합니다. 벨만 포드는 "모든 간선에 대해 업데이트를 진행"하지만, SPFA는 "바뀐 정점과 연결된 간선에 대해서만 업데이트를 진행"합니다. 벨만포드를 학습하지 않고, SPFA를 학습하셔도 태그로 벨만포드가 들어간 문제를 대부분 해결하실 수 있습니다. ex) https://www.acmicpc.net/problem/11657 11657번: 타임머신 첫째 줄에 도시의 개수 N (1 ≤ N ≤ 500), 버스 노선의 개수 M (1 ≤ M ≤ 6,000)이 주.. 공감수 0 댓글수 2 2023. 1. 24.
Dijkstra - 데이크스트라(다익스트라) 데이크스트라(Dijkstra)는 BFS 알고리즘을 알고 있다면 조금 더 쉽게 이해할 수 있다. 시작 지점 부터 가고자하는 도착지점까지 최소한의 시간으로 도착할 수 있는 거리를 구하는 알고리즘이다. ex)https://www.acmicpc.net/problem/1916 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 www.acmicpc.net 예제 입력은 1번에서 출발하여 5번까지 도착하는데 걸리는 최소 시간을 구하는 문제입니다. 1 -> 4 -> 5을 이동하게 된다면 1 + 3 = 4의 시간이 걸리게 .. 공감수 0 댓글수 1 2023. 1. 22.
BFS - 너비 우선 탐색 / DFS - 깊이 우선 탐색 너비 우선 탐색(Breadth First Search) / DFS(Depth First Search)은 시작지점부터 갈 수 있는 지점들을 들리면서, 더이상 갈 곳이 없을때까지 반복한 후 종료한다. ex) https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net 해당 문제는 이런 모양의 간선과 노드들로 이루어져 있습니다. 1번 컴퓨터에 바이러스가 걸리게 된다면, 1과 2, 3, 5, 6 총 4개의 컴퓨터가 1번 컴퓨터에 의해 바이러스에 감염되면서, 5개의 컴퓨.. 공감수 0 댓글수 0 2023. 1. 22.

728x90

반응형

문의안내

티스토리
로그인
고객센터

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